|
|
|
|
depth first search
|
(Algorithm)
|
|
|
The depth-first search (DFS) algorithm is a method for finding a spanning forest of a connected graph (specifically, a spanning tree in the case of an undirected connected graph), and is a useful basis for other algorithms. In particular, the DFS is useful for finding the connected components of a graph. This article currently describes only the DFS for an undirected graph.
Definition 1 (DFS on an Undirected Graph) Assume that the undirected graph $G = (V,E)$ is connected. The DFS proceeds as follows.
- Fix a vertex $v$ in $G$ and mark it as visited.
- For each edge $(v,w)$ oriented from $v$ to $w$
- If $w$ has been visited, do nothing.
- If $w$ has not been visited, perform a DFS starting from $w$
When the search is complete, it partitions $G$ into two sets. One contains the directed edges between visited vertices, called tree edges, which form a directed spanning tree of the graph. The other contains the remaining edges of $G$ which were left unexamined because they were incident on a vertex that was already visited at some point in the search. Because these unexamined edges can be seen as returning to vertices that were previously visited, they are called back edges.
- 1
- Swamy, M.N.S., Thulasiraman, K., Graphs, Networks and Algorithms, John Wiley and Sons, New York, 1981.
|
"depth first search" is owned by odenskrigare.
|
|
(view preamble | get metadata)
Cross-references: incident, directed spanning tree, tree, edge, vertex, fix, graph, connected components, spanning tree, connected graph, forest, spanning
This is version 12 of depth first search, born on 2008-05-27, modified 2008-06-03.
Object id is 10631, canonical name is DepthFirstSearch.
Accessed 1277 times total.
Classification:
| AMS MSC: | 05C85 (Combinatorics :: Graph theory :: Graph algorithms) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
