in Algorithms retagged by
6,782 views
5 votes
5 votes

Please explain....why answer is d)

in Algorithms retagged by
6.8k views

2 Answers

10 votes
10 votes
Best answer

tree edge is an edge in a DFS-tree.

 A back edge connects a vertex to an ancestor in a DFS-tree. Note that a self-loop is a back edge.

cross edge is any other edge in graph G. It connects vertices in two different DFS-tree or two vertices in the same DFS-tree neither of which is the ancestor of the other.

Tree edges $\left \{ (a,b),(b,e),(e,c) \right \}$ Cross edges $\left \{ (d,a),(d,b) \right \}$ Back edges $\left \{ (c,b) \right \}$.

edited by

4 Comments

but how can we pick randomly in the middle if there is no directed edge...since we use stack and push the vertices....is it compulsory to visit all the vertex in DFS traversal??
0
0
Yes in both BFS and DFS  it compulsory to visit all the vertex.

You just have scan array ones to find those vertices which are not visited (just traverse the visited array find the first vertex which is still at 0) then pic that vertex and do DFS again no need to visit those vertex which are already visited.
0
0
@cse23 Yes. I have the same question. But then I guess as it is mentioned whenever there comes a question of choosing, alphabetical order should be followed. So maybe for choosing the starting vertex also we should follow the same.
0
0
1 vote
1 vote

 

watch this video to understand all types of edges

edited by

Related questions