Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Basic Idea
Depth-first search (DFS) goes "deeper" in the graph whenever possible: it follows one branch as far as it can before backtracking.
Process:
- keep moving to an unvisited neighbour until a dead end (e.g. a leaf) is reached
- backtrack to the most recently visited vertex that still has an unvisited neighbour, and continue from there
- stop when every vertex reachable from the start has been visited
Stack Implementation
DFS uses a LIFO stack, in exactly the same frame as BFS with a queue:
- push
startonto a stacks - while
sis not empty: take the top valuev, remove it froms, and visit it if it is not visited yet - push all unvisited adjacent vertices of
vontos, pushing them in reverse so the leftmost is on top
| DFS | BFS | |
|---|---|---|
| Data structure | stack (LIFO) | queue (FIFO) |
| Take the next vertex from | top | front |
| Explores | deep first, then backtracks | level by level |

For this tree the visiting order is A B D G I H J K L C E F.
Python Code with Adjacency List
def dfs(graph, start):
visited = [False] * (len(graph) + 1)
stack = [start]
order = []
while stack:
vertex = stack.pop() # take the top of the stack
if not visited[vertex]:
order.append(vertex)
visited[vertex] = True
for neighbor in reversed(graph[vertex]):
if not visited[neighbor]:
stack.append(neighbor)
return orderThe order is not unique: it depends on the order of each adjacency list. For the 13-vertex grid example starting at 1, the code prints 1 3 2 6 5 7 8 4 9 12 11 10 13.
Applications
Uses (BFS works for both too):
- connectivity test: run DFS from any vertex, and the graph is connected if and only if every vertex was visited
- unconnected graphs: if vertices remain unvisited, start a new DFS from one of them, and repeat until all are visited, each run finds one component
Time Complexity
Same as BFS: every vertex and every edge is handled a constant number of times, so DFS is .