Editor

Python Program for Depth-First Search on a Graph

Intermediate · Data structures

Depth-first search (DFS) explores a graph by going as deep as it can along one path before backing up and trying the next one, like exploring a maze by always taking the first unexplored turning. It is usually written with recursion, and it is used to find paths, detect loops and check whether a graph is all in one piece.

Program

graph_dfs.py
# A
# / \
# B C
# / \ \
# D E---F
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
def dfs(node, visited, depth=0):
visited.append(node)
print(" " * depth + "Visit " + node)
for neighbour in graph[node]:
if neighbour not in visited:
dfs(neighbour, visited, depth + 1) # go deeper first
return visited
order = dfs("A", [])
print("DFS order from A:", " ".join(order))
Output
Visit A
  Visit B
    Visit D
    Visit E
      Visit F
        Visit C
DFS order from A: A B D E F C

How it works

  1. The graph is a dictionary in which each node maps to the list of nodes it is joined to.
  2. dfs() marks the node as visited, then calls itself on the first neighbour not yet visited, so it goes deeper before trying the other neighbours.
  3. From A it goes to B and then D, and since D has no new neighbours, that call ends and the search backs up to B and tries E, then F, then C.
  4. There is no separate base case: a node whose neighbours are all visited simply returns, and that is what makes the search back up.
  5. The indent in the output shows how deep each call is, and the visited list stops the search from going round the loop A, B, E, F, C forever.

Other ways to write it

Using a stack instead of recursion

Using a stack instead of recursion
graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
"D": ["B"], "E": ["B", "F"], "F": ["C", "E"]}
def dfs(start):
visited = []
stack = [start]
while stack: # until the stack is empty
node = stack.pop() # the newest node first
if node in visited:
continue
visited.append(node)
# Push neighbours in reverse so the first one is popped first
for neighbour in reversed(graph[node]):
if neighbour not in visited:
stack.append(neighbour)
return visited
print("DFS order from A:", " ".join(dfs("A")))
Output
DFS order from A: A B D E F C

A stack gives the same last-in, first-out order as the recursive calls, so this loop visits the nodes in the same order without recursion, which also avoids Python's limit of about 1000 nested calls on very large graphs.

Counting the separate pieces of a graph

Counting the separate pieces of a graph
graph = {"A": ["B"], "B": ["A", "C"], "C": ["B"],
"D": ["E"], "E": ["D"], "F": []}
def dfs(node, visited, group):
visited.add(node)
group.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
dfs(neighbour, visited, group)
visited = set()
pieces = []
for node in graph:
if node not in visited: # no earlier search reached this node
group = []
dfs(node, visited, group)
pieces.append(group)
print("Pieces:", pieces)
print("Number of pieces:", len(pieces))
Output
Pieces: [['A', 'B', 'C'], ['D', 'E'], ['F']]
Number of pieces: 3

Each DFS collects every node it can reach, so starting a new search from each node not yet visited splits the graph into its separate pieces, here 3, with F on its own.

Try it yourself

Add an edge between "D" and "F" (in both lists) and see how the DFS order changes.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises