algorithmgraph-theorydepth-first-searchgraph-traversal

how to take tree roots in a DFS forest?


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?


Solution

  • 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:

    enter image description here