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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.