409 views

1 Answer

1 votes
1 votes

All types of edges appear in this picture. Trace out DFS on this graph (the nodes are explored in numerical order), and see where your intuition fails.


This will explain the diagram:-

Forward edge: (u, v), where v is a descendant of u, but not a tree edge.It is a non-tree edge that connects a vertex to a descendent in a DFS-tree.

Cross edge: any other edge. Can go between vertices in same depth-first tree or in different depth-first trees. (layman)
It 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.(formal)

src:- https://cs.stackexchange.com/questions/11116/difference-between-cross-edges-and-forward-edges-in-a-dft

Related questions

0 votes
0 votes
2 answers
1
viral8702 asked Sep 21, 2023
288 views
The Total Combinations Possible of Min heap with 8 Distinct elements are ?
0 votes
0 votes
1 answer
2
iamdeepakji asked Jan 27, 2019
278 views
If there is negative edge cycle then dijkstra algorithm will give correct path or not same thing about bellman ford also?Bellman ford always halts or not?
0 votes
0 votes
1 answer
3
vijju532 asked Jun 29, 2018
421 views