A DFS starting at some vertex v explores the graph by building up a tree that contains all vertices that are reachable from v and all edges that are used to reach these vertices. We call this tree a DFS tree. A complete DFS exploring the full graph (and not only the part reachable from a given vertex v) builds up a collection of trees, or forest, called a DFS forest.

If I have a directed graph and I need to find the roots of these trees that are part of the dfs forest, do I have to modify the dfs algorithm to do this?

CodePudding user response：

To find the roots of the trees in a directed graph, loop over the nodes and list any that have out edges but no in edges

Like this: