Breadth-First Search Algorithm in Details: Graph Algorithm
Breadth first search algorithm

Breadth-First Search Algorithm in Details: Graph Algorithm

  1. Developing the algorithm in Python
  2. How to use this algorithm to find the shortest path of any node from the source node.
  3. Time complexity

How the Breadth_first_search algorithm works

A graph has two elements. Vertices and edges.

  1. Initialize a set for level with start vertex S as level 1.
  2. Explore which other vertex is reachable from the start. Those vertices will be considered as level 2.
  3. In this way, vertices will be opened level by level.
Image for post
Image for post
Image for post
Image for post
Image for post

Algorithm in Python

Before we can dive into the algorithm let’s make an adjacency list. That is to make a dictionary where each node will be a key and the nodes that are linked to it will be the values stored in a list.

'u': ['v', 'x']
adj = {
    'u': ['v', 'x'],
    'x': ['u', 'v', 'y'],
    'v': ['u', 'x', 'y'],
    'y': ['w'],
    'w': ['y', 'z'],
    'z': ['w']
    }
from queue import Queue
visited = {}
level = {}
parent = {}
traversal_output = []
queue = Queue()
for node in adj_list.keys():
        visited[node] = False
        parent[node] = None
        level[node] = -1
s = "u"
visited[s] = True
level[s] = 0
queue.put(s)
while not queue.empty():
    u = queue.get()
    traversal_output.append(u)
    for v in adj_list[u]:
        if not visited[v]:
            visited[v] = True
            parent[v] = u
            level[v] = level[u] + 1
            queue.put(v)
print(traversal_output)
print(visited)
print(level)
print(parent)
['u', 'v', 'x', 'y', 'w', 'z']
{'u': True, 'x': True, 'v': True, 'y': True, 'w': True, 'z': True}
{'u': 0, 'x': 1, 'v': 1, 'y': 2, 'w': 3, 'z': 4}
{'u': None, 'x': 'u', 'v': 'u', 'y': 'v', 'w': 'y', 'z': 'w'}
def Breadth_first_search(adj_list):
    visited = {}
    level = {}
    parent = {}
    traversal_output = []
    queue = Queue()
    for node in adj_list.keys():
        visited[node] = False
        parent[node] = None
        level[node] = -1
    s = "u"
    visited[s] = True
    level[s] = 0
    queue.put(s)
    while not queue.empty():
        u = queue.get()
        traversal_output.append(u)
        for v in adj_list[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                level[v] = level[u] + 1
                queue.put(v)
    return traversal_output, visited, level, parent

Finding the Shortest Distance

This algorithm can be used to find the shortest path from the source to any other node. How?

traversed, visited, level, parent = Breadth_first_search(adj)
v = "w"path = []
while v is not None:
    path.append(v)
    v = parent[v]
path.reverse()
print(path)
['u', 'v', 'y', 'w']

Time Complexity

We have only two elements here. Vertices and edges.

Conclusion

I tried to explain, how the Breadth_first_search algorithm works using visuals, developed the algorithm in Python, How to find the shortest path using the Breadth_first_search algorithm, and the time complexity of this algorithm. I hope it is clear to you now.

#programming #python #algorithm #technology #searchandsort

Leave a Reply

Close Menu