Depth-First Search vs. Breadth-First Search in Python

The simplified explanation of the two traversals algorithm.

What does it even mean to traverse a tree?

Preorder traversal

Until all nodes are traversed
Step 1 − Visit the root node
Step 2 − Recursively traverse left subtree
Step 3 − Recursively traverse the right subtree.
Image for post
Image for post

Inorder traversal

Until all nodes are traversed 
Step 1 − Recursively traverse left subtree
Step 2 − Visit the root node
Step 3 − Recursively traverse the right subtree.
Image for post
Image for post
In-order Traversal

Postorder traversal

Until all nodes are traversed 
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse the right subtree.
Step 3 − Visit the root node.
Image for post
Image for post
Postorder Traversal

Depth-First Search (DFS)

Image for post
Image for post
The depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post

DFS in Python

graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : [],
'D' : [],
'E' : []
}
def dfs(visited, graph, node):
if node not in visited:
print (node)
visited.add(node)
for neighbor in graph[node]:
dfs(visited, graph, neighbor)

Breadth-First Search

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post

BFS in Python

graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : [],
'D' : [],
'E' : []
}
def bfs(visited, graph, node):
visited.append(node)
queue.append(node)

while queue:
s = queue.pop(0)
print (s, end = " ")

for neighbor in graph[s]:
if neighbor not in visited:
visited.append(neighbor)
queue.append(neighbor)

BFS vs. DFS

Image for post
Image for post
Image for post
Image for post
Quick summary

That’s it!

Image for post
Image for post
Source: meme

Resource:

Written by

Interests: Data Science, Machine Learning, AI, Stats, Python | Minimalist | A fan of odd things.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store