I know how Depth First Search works and how to implement it, but I keep seeing DFS-Forest Component being referenced in my textbook, and I'm not entirely sure what it means. I know that a component of a graph is a subgraph disconnected from the other components. So what is a DFS-Forest Component?
2 Answers
According to this University of Edinburgh's paper:
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.
I was overthinking it:
A DFS-Forest Component is any set of nodes within the DFS-Forest that are strongly connected (a path between all pairs of vertices in the component exists). In an undirected graph, I'd imagine this means that every node is a part of the same component, but in a directed graph this isn't necessarily the case.
Related