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??

Dark Mode

6,782 views

10 votes

Best answer

A **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.

A **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 \}$.

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.

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