Graph form data is present in many popular and widely used applications. Web crawlers, computer networks, relational databases, and social networks are some good examples. The graph search algorithms are important for any section of computer science. Also, it is important and useful for many coding interviews.

There are a couple of different graph search algorithms available. This is one of the simplest algorithms for graph search and also a type of prototype for many other graph algorithms. Today I will explain the Breadth-first search algorithm in detail and also show a use case of the Breadth-first search algorithm. Here are the elements of this article:

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

Let’s start!

How the Breadth_first_search algorithm works

A graph has two elements. Vertices and edges.

Given,

A graph G = (V, E),

where V is the vertices and E is the edges.

The breadth-first search algorithm systematically explores the edges level by level to discover each vertex that is reachable from the given source vertex s.

Here are the steps to a Breadth-first search process:

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

Here is a visual demonstration of the steps:

Here, we have six vertices, u, v, w, x, y, z, and seven edges ux, uv, vx, vy, xy, wy, wz.

Consider the vertex u as the source or start vertex. Now see how they open level by level in the pictures below.

The source vertex is u is level 1. We check where can we go from L1. From the picture, you can see that ‘u’ has a direct path to v and x. So, they are level 2.

Now, we are in nodes x and v. Both x and v have direct access only to y. So, y is the level3. From both x and v, we can go to u also. But we ignore the already visited nodes.

y has direct access to w only. So, w is the level4. We can go to v and x as well from y. But they are already visited. So, we do not need to worry about them anymore.

At last, w can go to z and z is level5.

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.

For example, node u is linked to nodes v and x. So, it will be expressed as:

'u': ['v', 'x']

Here ‘u’ is the parent of ‘v’ and ‘x’.

We need to do the same with all the other nodes as well. The adjacency list will look like:

adj = {
    'u': ['v', 'x'],
    'x': ['u', 'v', 'y'],
    'v': ['u', 'x', 'y'],
    'y': ['w'],
    'w': ['y', 'z'],
    'z': ['w']
    }

Next, We need to initialize a few variables:

‘visited’ variable to keep track of the node that we already visited,

‘level’ variable to keep track of which level we are currently in,

‘parent’ variable to store the parents of the nodes.

‘traversal_output’ to list the nodes traveled.

Finally, we will use a queue to develop this algorithm. Python has a built-in queue that we can import and use.

from queue import Queue
visited = {}
level = {}
parent = {}
traversal_output = []
queue = Queue()

In the beginning, set ‘False’ to all the nodes in the ‘visited’ dictionary and ‘None’ to all the nodes in the ‘parents’ dictionary and -1 in the level.

for node in adj_list.keys():
        visited[node] = False
        parent[node] = None
        level[node] = -1

As in the picture, assume that the source is ‘u’. To start with, use visited[s] = True, use level 0 and add ‘u’ in the Queue.

s = "u"
visited[s] = True
level[s] = 0
queue.put(s)

Here comes the loop!

At this stage, we need to visit the nodes that are linked to the source node ‘u’. We have it listed in the adjacency list above. For each of them, set them as visited, upgrade their levels as one level above the source node’s level, set their parent as ‘u’, and finally add then in the Queue.

Then do repeat the same with their child nodes. Here is the complete loop:

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)

Output:

['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'}

Traversal_output shows that we traversed through all the nodes.

For each node, visited is true in the second row.

In the third row, we have the level for all the nodes. Please check with the pictures above.

In the fourth row, we have the parents of all the nodes. ‘u’ is the source node. So, ‘u’ does not have a parent.

Combining all the code and putting them in a function:

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

Calling the function and pass the adjacency list ‘adj’ will gives you the same output.

Finding the Shortest Distance

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

Look, we know the parent of each node. From any node, we keep going back through the parents, it will eventually go back to the source node. Right?

For example, say, I want to find the shortest path of ‘w’ from the source node ‘u’. Let’s see, who is w’s parent. it’s ‘y’. y’s parent is ‘v’ and then v’s parent is ‘u’. So, the shortest path is u, v, y, w.

Check in the picture to see if you think this is the shortest path.

We can find the parents of each node from the function we defined above.

traversed, visited, level, parent = Breadth_first_search(adj)

Here is the code to find the shortest path

v = "w"path = []
while v is not None:
    path.append(v)
    v = parent[v]
path.reverse()
print(path)

Output:

['u', 'v', 'y', 'w']

Time Complexity

We have only two elements here. Vertices and edges.

Notice, carefully. We visit each vertex only one time. In the for loop, we ignore the already visited vertices. Consider, V as the set of vertices.

We used an undirected graph here. For an undirected graph, we can visit both ways. The way we can go from ‘u’ to ‘v’, we can go from ‘v’ to ‘u’ as well. In the adjacency list ‘adj’ above, you can see that one node can come up more than once. At most, we will traverse one edge twice. Let E be the set of edges, it will traverse the edges 2E times in the worst case. Som the total time in worst case V+2E.

The time complexity can be expressed as O(V+E) as the coefficient is subsumed by the O.

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.

Feel free to follow me on Twitter and like my Facebook page.

#programming #python #algorithm #technology #searchandsort