Programming & DS [BFS Cross Edges]

Question

Please tell what is difference between Back edge and cross edge?

Answer 1

I am posting answer myself.Please correct if wrong.I am also sharing some points i read about these edges.

• Back edges point from a node to one of its ancestors in the DFS tree.

• Forward edges point from a node to one of its descendants.

• Cross edges point from a node to a previously visited node that is neither an ancestor nor a descendant.

So for above question

We can see if BFS graph of the tree in above image,all the edges drawn with RED are Cross edges because there is no parent child relation between these edges.These are edges which are dropped while BFS traversal.But d-b is a tree edge and not cross edge.

More information:-

https://courses.csail.mit.edu/6.006/fall11/rec/rec14.pdf