946 views

1 Answer

1 1 vote

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

Position:
Show:

Related questions

0 0 votes
2 2 answers
667
667 views
viral8702 asked Sep 21, 2023
667 views
The Total Combinations Possible of Min heap with 8 Distinct elements are ?
0 0 votes
1 1 answer
565
565 views
iamdeepakji asked Jan 27, 2019
565 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 0 votes
1 1 answer
701
701 views
vijju532 asked Jun 29, 2018
701 views
0 0 votes
1 1 answer
1.0k
1.0k views
air1ankit asked Jul 12, 2018
1,042 views
anyone please explain me how to find loc in lower triangular matrix , i am getting little bit confuse suppose matrix is ...