edited by
560 views
1 votes
1 votes
Assume WHITE vertices that are yet to be discovered, BLACK vertices are finished vertices and GRAY vertices are frontier betweeen WHITE and BLACK in Depth First Search.

Now, What are the various edge types like TREE-EDGE and BACK-EDGE possible between any pair of vertices during a Depth First Search in an Undirected graph.

Confused about the edge type between WHITE and GRAY type vertices.

[ CLRS (3rd Edition) : 22-3:1; Page # 610 ]
edited by

1 Answer

0 votes
0 votes

An edge (u,v) is said to be TREE-EDGE if either u is ancestor of v or v is ancestor of u.
An edge (u,v) is said to be BACK-EGE if the edge between u and v discovered during the traversal from v to u.

If we can have a TREE-EDGE between any pair of types of vertices in an undirected graph, we can also have BACK-EDGE in that same pair of  types of vertices.

Possible types of edges in undirected graph during DFS at any stage
  WHITE GRAY BLACK
WHITE Tree, Back Tree, Back None
GRAY Tree, Back Tree, Back Tree, Back
BLACK None Tree, Back Tree, Back

Related questions

0 votes
0 votes
0 answers
1
saumya mishra asked Sep 25, 2017
279 views
What is the correct answer please provide with reason?
0 votes
0 votes
1 answer
2
Xylene asked Aug 20, 2017
2,440 views
If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge. True or false ?
0 votes
0 votes
2 answers
4
radha gogia asked Jun 30, 2015
1,759 views
Does a DFS for an undirected graph always produce the same number of tree edges irrespective of the order in which we visit the vertices ?