Menu
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?
538
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
Depth First Search Example We use an undirected graph with 5 vertices. Undirected graph with 5 vertices. We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the stack. Visit the element and put it in the visited list.
Depth-first search (DFS) is an algorithm for searching a graph or tree data structure. The algorithm starts at the root (top) node of a tree and goes as far as it can down a given branch (path), then backtracks until it finds an unexplored path, and then explores it.
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.
142
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.
34
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
