Breadth-first search is a traversal technique in which we traverse a graph and print the vertices exactly once. In this article, we will study and implement the breadth-first search for traversing graphs in python.
What is the Breadth-First Search Algorithm?
In breadth-first search, we traverse each vertex of the graph exactly once by starting from any single vertex. For each selected vertex we first print the vertex and then we print all of its neighbors. This process is continued till all the vertices are traversed. While traversing a graph with breadth-first search, it looks like we are moving in layers starting from the selected vertex.
This can be understood clearly from the following example.
If we visit the above graph in a breadth-first manner starting from 0, we will process the vertices in the order 0–>1–>3–>2–>4–>5. There may be alternative traversal too. In case we process 3 before 1 while we are at 0, then the BFS traversal of the graph will look like : 0–>3–>1–>4–>2–>5.
Breadth-First Search Algorithm for a Graph in Python
As we have a general idea for the breadth-first search, we will now formulate the algorithm for the BFS traversal of the graph. Here, we will assume that all the vertices of the graph are reachable from the starting vertex.
Also read: Implement a graph in Python
Suppose that we have been given a graph in its adjacency list representation and a starting vertex and we have to traverse the graph.
We will first print the value in the starting vertex, then we will print the value of neighbors of the starting vertex and we will move on to the next level after completing the current level till all the vertices of the graph are printed.
So, we have the task of printing the vertices in the current level of the graph starting from the first vertex till every vertex is traversed. To implement this concept we will use the first in first out technique i.e. queue to process the graph.
Also, we will use a list of visited vertices to check if the vertex is traversed in the past or not so that no vertices are printed twice.
We will print a vertex, add it to the list of visited vertices, and put its neighbors in the queue. We will take out the vertices one by one from the queue, add them to the visited list after printing them, and then we will put their neighbors into the queue. Here is the algorithm for breadth-first search traversal for a graph that depicts the entire process.
Algorithm BFS:
Input: Graph(Adjacency list) and Source vertex
Output: BFS traversal of graph
Start:
1.Create an empty queue Q.
2.Create an empty set to keep record of visited vertices.
3.Insert source vertex into the Q and Mark the source as visited.
4.If Q is empty, return. Else goto 5.
5.Take out a vertex v from Q.
6.Print the Vertex.
7.Insert all the vertices in the adjacency list of v which are not in visited list into Q and mark them visited.
8.Goto 4.
Stop.
Breadth-first search traversal of a graph in Python
Now that we are familiar with the concepts and algorithm, we will implement the breadth-first search algorithm for the graph and then we will execute the algorithm for the graph given in the above example figure.
from queue import Queue
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
print("The adjacency List representing the graph is:")
print(graph)
def bfs(graph, source):
Q = Queue()
visited_vertices = set()
Q.put(source)
visited_vertices.update({0})
while not Q.empty():
vertex = Q.get()
print(vertex, end="-->")
for u in graph[vertex]:
if u not in visited_vertices:
Q.put(u)
visited_vertices.update({u})
print("BFS traversal of graph with source 0 is:")
bfs(graph, 0)
Output:
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
BFS traversal of graph with source 0 is:
0-->1-->3-->2-->4-->5-->
If you have not been able to understand the execution of the code, here is a modified BFS algorithm explaining each step.
from queue import Queue
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
print("The adjacency List representing the graph is:")
print(graph)
def bfs_explanation(graph, source):
Q = Queue()
visited_vertices = set()
Q.put(source)
visited_vertices.update({0})
while not Q.empty():
vertex = Q.get()
print("Processing {} after taking out from Q".format(vertex))
for u in graph[vertex]:
if u not in visited_vertices:
print("At {}, adding {} to Q".format(vertex, u))
Q.put(u)
visited_vertices.update({u})
print("visited vertices are: ", visited_vertices)
print("Explanation of BFS traversal of graph with source 0 is:")
bfs_explanation(graph, 0)
Output:
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
Explanation of BFS traversal of graph with source 0 is:
Processing 0 after taking out from Q
At 0, adding 1 to Q
At 0, adding 3 to Q
visited vertices are: {0, 1, 3}
Processing 1 after taking out from Q
At 1, adding 2 to Q
visited vertices are: {0, 1, 2, 3}
Processing 3 after taking out from Q
At 3, adding 4 to Q
visited vertices are: {0, 1, 2, 3, 4}
Processing 2 after taking out from Q
At 2, adding 5 to Q
visited vertices are: {0, 1, 2, 3, 4, 5}
Processing 4 after taking out from Q
visited vertices are: {0, 1, 2, 3, 4, 5}
Processing 5 after taking out from Q
visited vertices are: {0, 1, 2, 3, 4, 5}
Conclusion
In this article, we have seen the underlying concepts behind the breadth-first search traversal algorithm for a graph, designed its algorithm, and then implemented it in python. We have also seen the step-by-step execution of the algorithm in Python. Stay tuned for more informative articles.