DFS: Difference between revisions
From Rice Wiki
No edit summary |
(→DFS) |
||
Line 1: | Line 1: | ||
{{Infobox Algorithm|runtime=O(V + E)|space=O(V)|class=[[Graph Algorithms]]}} | {{Infobox Algorithm|runtime=O(V + E)|space=O(V)|class=[[Graph Algorithms]]}} | ||
'''Depth-first search''' is a graph traversal algorithm. | |||
= Approach = | |||
The basic idea of DFS is to visit ''every child'' of the visiting node before moving on to the next unvisited node. | |||
# Every node besides one start out being unvisited (''white''). | |||
# DFS begin by visiting a source node. Upon entering a node, DFS marks it as visiting (''grey''). | |||
# DFS then visits all of its child nodes. | |||
# After it has visited all children of a grey node, it marks the visiting parent node as visited (''black''). | |||
# This continues until every node is black. | |||
== Implementation == | == Implementation == | ||
Line 23: | Line 28: | ||
</pre> | </pre> | ||
= Other Applications = | |||
== Edge classification and cycle detection == | |||
DFS can classify edges based on the color of the node it is visiting. | |||
* If the node is ''white'' (unvisited), the edge is called a '''tree edge'''. After DFS ends, all the tree edges form a spanning tree stemming from the source node (if the graph is connected). | |||
* If the node is ''grey'' (visiting), the edge is called a '''back edge'''. During a visit, any grey node is a predecessor of the current node, therefore edges to grey node goes "back" up. Notably, the presence of back edges indicate that there is a '''cycle'''. | |||
* If the node is ''black'' (visited), the edge is called a '''cross edge'''. They "cross" from one branch to another, neither being in the tree nor creating a cycle. | |||
== Entry time and exit time == | |||
Keeping track of the order in which DFS enter and exit nodes can solve problems such as '''topological sort'''. | |||
[[Category:Algorithms]] | [[Category:Algorithms]] |
Revision as of 06:20, 20 March 2024
Depth-first search is a graph traversal algorithm.
Approach
The basic idea of DFS is to visit every child of the visiting node before moving on to the next unvisited node.
- Every node besides one start out being unvisited (white).
- DFS begin by visiting a source node. Upon entering a node, DFS marks it as visiting (grey).
- DFS then visits all of its child nodes.
- After it has visited all children of a grey node, it marks the visiting parent node as visited (black).
- This continues until every node is black.
Implementation
DFS_visit(u) { time = time + 1 d[u] = time color[u] = 'grey' for each v in adj[u] { if color[u] == white DFS_visit(u) } f[u] = time++ color[u] = black }
Other Applications
Edge classification and cycle detection
DFS can classify edges based on the color of the node it is visiting.
- If the node is white (unvisited), the edge is called a tree edge. After DFS ends, all the tree edges form a spanning tree stemming from the source node (if the graph is connected).
- If the node is grey (visiting), the edge is called a back edge. During a visit, any grey node is a predecessor of the current node, therefore edges to grey node goes "back" up. Notably, the presence of back edges indicate that there is a cycle.
- If the node is black (visited), the edge is called a cross edge. They "cross" from one branch to another, neither being in the tree nor creating a cycle.
Entry time and exit time
Keeping track of the order in which DFS enter and exit nodes can solve problems such as topological sort.