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
A
k
B
k + 1
C
n - k - 1
D
n - k
       Algorithms       Graph-Traversal       Gate 2005-IT
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
There is 1 question to complete.
PHP Code Snippets Powered By : XYZScripts.com