Hacker News new | ask | show | jobs
by Karliss 1315 days ago
If you form a spanning tree by noting which edges where used during DFS traversal of undirected graph, then all of the edges not used will connect a node with it's ancestor and there will be no cross edges. It doesn't matter if all you care is traversing the graph in any order and maybe checking which parts are connected, but it is important for some of the more complex graph algorithms built on top of DFS.