Graph-Traversal
Question 1 |
In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is
k | |
k + 1 | |
n - k - 1 | |
n - k |
Question 1 Explanation:
In a graph G with n vertices and p component then G has n - p edges(k).
In this question, we are going to applying the depth first search traversal on each component of graph where G is conected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k
In this question, we are going to applying the depth first search traversal on each component of graph where G is conected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k
There is 1 question to complete.