topological sort via depth first search: more than one source

1k Views Asked by At

If the first node in a Depth First Search is chosen as one of say 2 sources in a directed, acyclic Graph G(V,E), how can a depth-first search ever find the 2nd source since with each iteration it is pushing the set of successors of each node onto the stack? And if it cannot find all nodes, it cannot be a total ordering and so cannot generate a topological sort.

Graph I am looking at image from wikipedia

1

There are 1 best solutions below

0
On

Depth-First search is sometimes stated as an algorithm which takes a graph $G$, and a vertex $v \in G$, and outputs everything reachable from that starting vertex. Call this "single-component" DFS.

Depth-First search is also sometimes stated as an algorithm which takes only the graph $G$ as input, and runs single-component DFS in a loop. On each iteration of the outer loop, an unvisited $v$ is selected, and single-component DFS is run from that $v$. Once every vertex has been visited, the loop terminates: this DFS will clearly traverse the whole graph $G$.

I think this second version of DFS is what is being used in that topological sort.