Depth First Search and Breadth First Search in Python

By Akshat Kumar

This Project Highlights the Depth First Search and Breadth First Search Algorithms and their implementation in Python.

A Graph Data structure is a collection of vertices/nodes which are connected to each other using edges. For example, social media sites like Instagram use Graph Data structures to Store user information, every time a user creates a new post a new node is created which is linked to the user's account.

Example of a Graph

Depth First Search is an Algorithm to Find or traverse all the nodes of a Graph, traversing implies visiting all the nodes of a graph. A DFS algorithm works by separating the nodes into two categories:

Visited 

Not-visited 

Its space complexity is measured by O(V) where V is the number of vertices/nodes.

Its Time complexity is measured by O(V + E) where V is the number of vertices/nodes and E is the number of edges.

DFS algorithm:

1) Start by selecting any node A in the graph.

2) Append node A in the visited list.

3) Find all the adjacent/neighbor nodes of node A and stack them in the neighbor list.

4) Select the top node in the neighbor list and append it to the visited list and update the neighbor list with its adjacent/neighbor nodes.

5) repeat till all the nodes are in the visited list.

 

For the example above let's begin with

node: 5

Visited list: 5

Neighbor list: 7  3

 

node: 7

Visited list: 5 7

Neighbor list: 8 3

 

node: 8

Visited list: 5 7 8

Neighbor list: 4 3 

 

node: 4

Visited list: 5 7 8 4

Neighbor list: 3 

 

node: 3

Visited list: 5 7 8 4 3

Neighbor list: 2

 

node: 2 

Visited list: 5 7 8 4 3 2

Neighbor list:

 

Let's See how to implement this in Python

First, we define the graph in Python using dictionaries

graph = {

  '5' : ['7','3'],

  '7' : ['8'],

  '8' : ['4'],

  '3' : ['4', '2'],

  '2' : [],

  '4' : []

}

Then, we define the Visited list

visited = []

 

Then, We create a function for DFS

def DFS(visited, graph, node):  

    if node not in visited:

        print (node)

        visited.append(node)

        for neighbour in graph[node]:

            DFS(visited, graph, neighbour)

 

Driver code

print("Following is the Depth-First Search")

DFS(visited, graph, '5')

 

Output

Following is the Depth-First Search:  5 7 8 4 3 2

 

Similar to DFS, Breadth First Search is an Algorithm to Find or traverse all the nodes/vertices of a Graph.

Its space complexity is measured by O(V) where V is the number of vertices/nodes.

Its Time complexity is measured by O(V + E) where V is the number of vertices/nodes and E is the number of edges.

BFS algorithm:

1) Start by selecting any node A in the graph.

2) Append node A in the visited list.

3) Find all the adjacent/neighbor nodes of node A and queue them in the back of the neighbor list.

4) Select the front node in the neighbor list and append it to the visited list and update the neighbor list with its adjacent/neighbor nodes.

5) repeat till all the nodes are in the visited list.

 

For the example above let's begin with

node: 5

Visited list: 5

Neighbor list: 7  3

 

node: 7

Visited list: 5 7

Neighbor list: 3 8

 

node: 3

Visited list: 5 7 3

Neighbor list: 8 4 2

 

node: 8

Visited list: 5 7 3 8

Neighbor list: 4 2

 

node: 4

Visited list: 5 7 3 8 4

Neighbor list: 2

 

node: 2 

Visited list: 5 7 3 8 4 2

Neighbor list:

 

Let's See The Python implementation of BFS

First, we define the graph in Python using dictionaries

graph = {

  '5' : ['7','3'],

  '7' : ['8'],

  '8' : ['4'],

  '3' : ['4', '2'],

  '2' : [],

  '4' : []

}

Then, we define the Visited list

visited = [] # List for visited nodes.

neighbor_list = []   #Initialize a queue

 

Then, We create a function for BFS

def BFS(visited, graph, node): 

  visited.append(node)

  neighbor_list.append(node)

 

  while neighbor_list:        

    m = neighbor_list.pop(0)

    print (m, end = " ")

 

    for neighbour in graph[m]:

      if neighbour not in visited:

        visited.append(neighbour)

        neighbor_list.append(neighbour)

 

Driver code

print("Following is the Breadth-First Search")

DFS(visited, graph, '5')

 

Output

Following is the Breadth-First Search:  5 7 3 8 4 2