Depth First Seach And Breath First Search In Python
Sep 3rd, 2021 - written by Kimserey with .
In Python, it is very easy to implement depth first search (DFS) and breath first search (BFS) algorithms using the built in data types and recursion. In today’s post, we will look at some different flavours of DFS and BFS together with examples where they are used.
DFS and BFS in Trees
Let’s start first by setting up a binary tree structure:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
In [1]: class Node:
...: def __init__(self, val=0, left=None, right=None):
...: self.val = val
...: self.left = left
...: self.right = right
...:
...:
In [2]: root = Node(1, Node(2, Node(3), Node(4)), Node(5, Node(6)))
# 1
# / \
# / \
# 2 5
# / \ /
# 3 4 6
Depth first search is a traversal algorithm where we traverse the children nodes by going to the depth of a path prior moving to another path.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In [7]: def dfs(node):
...: if not node:
...: return
...:
...: print(node.val)
...: dfs(node.left)
...: dfs(node.right)
In [8]: dfs(root)
1
2
3
4
5
6
We can see the order of traversal goes from the root till the leaf on the left side and goes to the depth of the tree on each branch.
We can either return a value or not return a value. It is useful to return a value when we must execute some comparison between the parent node and the child node or if the child node is necessary to be set on the parent node (e.g. we are constructing a new tree).
Breath first search is a traversal algorithm where adjacent/siblings nodes are visited prior children nodes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
In [9]: def bfs(node):
...: nodes = [node]
...:
...: while nodes:
...: n = nodes.pop(0)
...:
...: print(n.val)
...: if n.left:
...: nodes.append(n.left)
...: if n.right:
...: nodes.append(n.right)
In [10]: bfs(root)
1
2
5
3
4
6
Here we can see that the nodes are visited by adjacent nodes. BFS is useful in cases where we want to keep track of the steps or the level at which we are visitiing the node as the exploration of the tree is gradual, we can increment the steps to keep track of how far a node is from the root.
DFS in Arrays
DFS is usually discussed with trees and graphs but it’s also commonly used in one dimensional arrays. It usually take the shape of a recursion function but it is in a way the same methodology applied as for the graphs:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
In [22]: a = [1, 2, 3, 4, 5, 6]
In [23]: def dfs(numbers, cur):
...: if len(cur) == 4:
...: print(cur)
...: return
...:
...: for i, n in enumerate(numbers):
...: dfs(numbers[i+1:], cur + [n])
In [24]: dfs(a, [])
[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 3, 6]
[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 5, 6]
[1, 3, 4, 5]
[1, 3, 4, 6]
[1, 3, 5, 6]
[1, 4, 5, 6]
[2, 3, 4, 5]
[2, 3, 4, 6]
[2, 3, 5, 6]
[2, 4, 5, 6]
[3, 4, 5, 6]
Here we are displaying the combination of four contiguous elemenets of an array. We can see that DFS was applied as we expanded the first path till the last node [1, 2, 3] and then expanded the rest of the possiblities, 4, 5 and 6. This could have been represented as a tree.
DFS and BFS in Graphs
Lastly DFS and BFS are also useful when trying to solve problems with graphs. Graphs can either be represented as vertices and edges but they can also appear in the form of 2D matrices.
1
2
3
4
In [37]: a = [[0] * 4 for _ in range(4)]
In [38]: aAn
Out[38]: [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
We start first by creating a 2D matrice of 0’s which will serve us to illustrate DFS versus BFS.
Just like trees, DFS can be used in graphs or matrices by exploring the depth of paths, the only variation is that there is multiple direction to expand so we have to keep track of which direction we already have expanded.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
In [49]: m, n = len(a), len(a[0])
...: seen = set()
...:
...: def dfs(i, j, val):
...: if i < 0 or i == n or j < 0 or j == m or (i, j) in seen:
...: return
...:
...: a[i][j] = val
...: seen.add((i, j))
...:
...: dfs(i-1, j, val + 1)
...: dfs(i+1, j, val + 1)
...: dfs(i, j-1, val + 1)
...: dfs(i, j+1, val + 1)
In [50]: dfs(0, 0, 1)
In [52]: for row in a:
...: print(row)
...:
[1, 8, 9, 16]
[2, 7, 10, 15]
[3, 6, 11, 14]
[4, 5, 12, 13]
We can see that we explore the matrice following the order predefined by our DFS function which expandsd in order when applicable:
- down
- up
- left
- right
BFS algorithm is imiplemented in the same way as with the tree where we use a queue:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
In [65]: def bfs():
...: cells = [(0, 0)]
...: seen = set()
...: val = 1
...:
...: while cells:
...: i, j = cells.pop(0)
...: a[i][j] = val
...: seen.add((i, j))
...: val += 1
...:
...: if 0 <= i-1 and (i-1, j) not in seen:
...: cells.append((i-1, j))
...:
...: if i+1 < m and (i+1, j) not in seen:
...: cells.append((i+1, j))
...:
...: if 0 <= j-1 and (i, j-1) not in seen:
...: cells.append((i, j-1))
...:
...: if j+1 < n and (i, j+1) not in seen:
...: cells.append((i, j+1))
...:
In [66]: bfs()
In [67]: a
Out[67]: [[1, 3, 7, 15], [2, 6, 14, 29], [4, 12, 27, 49], [8, 23, 46, 69]]
In [68]: for row in a:
...: print(row)
...:
[1, 3, 7, 15]
[2, 6, 14, 29]
[4, 12, 27, 49]
[8, 23, 46, 69]
We can see that we explore adjacent cells first. And that concludes today’s post!
Conclusion
Today we looked at the differences between depth first search and breath first search in the context of trees, 1D array and 2D array. We saw how the searches could be implemented in Python with examples and got an intuition on how they would navigate the datastructure given. I hope you liked this post and I see you on the next one!