The DFS is the most fundamental search algorithm used to explore nodes and edges of a graph. It runs with a time complexity of $O(V+E)$ and is often used as a building block in other algorithms.
By itself DFS isn't all that useful, but when augmented to perform other tasks such as count connected components, determine connectivity, or find bridges/articulation points then DFS really shines.
#### General idea
DFS plunges depth first into a graph without regard for which edge it takes next until it cannot go any further at which point it backtracks and continues.
#### Pseudocode - Standard DFS
```python
# Instantiate tracking variables
n = 'number of nodes in the graph'
g = 'adjacency list representing graph'
visited = [False,...,False] # size n
def dfs(at):
if visited[at]:
return
visited[at] = True
neighbors = g[at]
for next in neighbors:
dfs(next)
# Start DFS at node zero
start_node = 0
dfs(start_node)
```
#### Pseudocode - DFS to find number of connected components
```python
# Instantiate tracking variables
n = 'number of nodes in the graph'
g = 'adjacency list representing graph'
count = 0 # Tracks number of connected componets
components = 'empty integer array' # size n, holds which component node belongs to
visited = [False,...,False] # size n
def find_components():
for i in range(0, n):
if not visited[i]:
count += 1
dfs(i)
return (count, components)
def dfs(at):
visited[at] = True
components[at] = count
for next in g[at]:
if not visited[next]:
dfs(next)
```
#### Pseudocode- Stack vs recursive implementation
* Note that both of the above implementations have a run time of $O(V + E)$.
* A quick (intuitive) derivation of the above:
* We can look at every single vertex, of which there are $V$. We never look at a vertex twice.
* Then, based on the way that we scan our graph, we never go along the same edge twice. For instance, if we visited `A` and `B`, and there is an edge connecting them, we will never go back along that edge.
### Key Takeaways
> DFS organizes vertices by entry/exit times, and edges into tree and back edges. This organization is what gives DFS its real power.
> DFS on undirected graphs proves useful because it *organizes* the edges of the graph in a *very precise way* (/posts/see [Algorithms and Structures can create new Structures](Algorithms%20and%20Structures%20can%20create%20new%20Structures.md))
### Examples/Use cases
* [Topological-Sort](Topological-Sort.md)
* Compute *strongly connected components*
---
Date: 20211014
Links to: [Graph-Algorithms](Graph-Algorithms.md) [Topological-Sort](Topological-Sort.md) [Depth-First-Search vs. Breadth First Search](Depth-First-Search%20vs.%20Breadth%20First%20Search.md)
Tags:
References:
* Algorithm Design Manual, Chapter 5: Graph Traversal
* [DFS, Topological Sort (MIT)](https://www.youtube.com/watch?v=AfSk24UTFS8)