Depth-First Search (DFS)

A graph traversal algorithm that explores as far as possible along each branch before backtracking.

Sredni

O(V + E)O(V)OIJOI

Select programming language

Choose the language to see the DFS implementation.

Select example

Small, Medium, and Large examples show recursion code generation. Very large shows only the call stack.

DFS (Python): Small graph (4 vertices)

Graph

1/0

Animation speed1.0x

Source codePython
1graph = {
2    1: [2, 3],
3    2: [4],
4    3: [4],
5    4: []
6}
7visited = set()
8
9def dfs(vertex):
10    """Depth-first search (DFS)."""
11    visited.add(vertex)
12    print(f"Visiting: {vertex}")
13
14    for neighbor in graph[vertex]:
15        if neighbor not in visited:
16            dfs(neighbor)
17
18dfs(1)
19print(visited)

Variables0 variables

No variables at this step

1/0

Animation speed1.0x

1	graph = {
2	1: [2, 3],
3	2: [4],
4	3: [4],
5	4: []
6	}
7	visited = set()
8
9	def dfs(vertex):
10	"""Depth-first search (DFS)."""
11	visited.add(vertex)
12	print(f"Visiting: {vertex}")
13
14	for neighbor in graph[vertex]:
15	if neighbor not in visited:
16	dfs(neighbor)
17
18	dfs(1)
19	print(visited)