Breadth-First Search Algorithm: An Introduction
As computer science students, we all come across graph theory in our curriculum, where we study the properties of graphs and their various representations. Graphs are a set of objects interconnected by edges or arcs.
They are used to model real-world scenarios, such as transportation networks, social networks, or genealogy trees.
Traversal techniques are essential when exploring a graph.
Traversal refers to visiting all the vertices of a graph in a given order. In this article, we will be discussing the Breadth-First Search (BFS) algorithm, which is a popular traversal technique.
1. Definition of BFS
Breadth-first search is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order. It starts by visiting the first node of the graph, then the nodes at the next level, and so on until all nodes are visited.
In other words, BFS visits all the nodes at a given level before moving on to the nodes at the next level.
2. BFS Algorithm for Graph in Python
In Python, we can represent a graph using an adjacency list. An adjacency list is a dictionary where each key represents a vertex of the graph, and the corresponding value is a list of its adjacent vertices.
2.1. The following is an implementation of the BFS algorithm for a graph in Python:
- Create a queue and enqueue the first vertex
- Mark the first vertex as visited
- While the queue is not empty:
- Dequeue the first vertex
- For each adjacent vertex of the dequeued vertex:
- If the adjacent vertex is not visited, mark it as visited and enqueue it into the queue
The above algorithm uses a queue data structure to keep track of the nodes that need to be visited.
We also use a visited set to keep track of the nodes that have been visited.
2.2. Example of BFS Traversal
Let’s consider the following graph:
A---B---C
| | |
D---E---F
| |
G---H
Suppose we want to traverse the above graph using BFS. We start by visiting the first vertex, which is A.
Since A is the starting vertex, we mark it as visited, and we add it to the queue. Our queue now contains only A.
We dequeue A and add its adjacent vertices, B and D, to the queue. The queue now contains B and D.
We mark both of them as visited, and their corresponding vertices are added to the end of the queue. The queue now contains C and E.
We dequeue B and add its adjacent vertices, A, C, D, and E. We ignore A and D since they have already been visited.
We add C and E to the end of the queue, making the queue [D, C, E]. We continue dequeuing vertices and adding their adjacent vertices to the queue until we have traversed all the vertices.
The BFS traversal of the graph produces the following sequence of vertices: A, B, D, C, E, F, G, H.
3. Implementing BFS Algorithm in Python
In this section, we will take a closer look at the implementation of the BFS algorithm in Python. We will provide a step-by-step guide on how to create a graph, represent it using an adjacency list, and traverse it using the BFS algorithm.
3.1. Code Implementation for BFS Algorithm in Python
To implement BFS algorithm in Python, we start by creating a graph using an adjacency list. The graph can be represented using a dictionary, where each key corresponds to a vertex, and the value is a list of its adjacent vertices.
graph = { "A" : ["B","D"],
"B" : ["A","C","E"],
"C" : ["B","F"],
"D" : ["A","E"],
"E" : ["B","D","F","G"],
"F" : ["C","E","H"],
"G" : ["E","H"],
"H" : ["F","G"] }
Once we have created the adjacency list, we can proceed to implement the BFS algorithm. To do this, we define a function called bfs that takes two parameters: the graph and the starting vertex.
def bfs(graph, start_vertex):
visited = set()
queue = []
visited.add(start_vertex)
queue.append(start_vertex)
while queue:
current_vertex = queue.pop(0)
print(current_vertex)
for neighbor in graph[current_vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Let’s go through this code step by step. First, we create an empty set called visited to keep track of the visited vertices.
We also create an empty list called queue to keep track of the vertices that need to be visited. We mark the starting vertex as visited and add it to the queue.
We then enter a while loop that runs as long as there are vertices in the queue. Inside the while loop, we use the pop(0) function to dequeue the first vertex from the queue and print it.
We then iterate over each adjacent vertex of the dequeued vertex and check if it has been visited. If it has not been visited, we mark it as visited, add it to the end of the queue, and continue with the next vertex in the queue.
3.2. Explanation of BFS Algorithm Execution
BFS algorithm execution involves a series of steps that are repeated until all the vertices of the graph have been visited. When executed correctly, the algorithm should traverse the graph in breadth-first order, i.e., visiting all the nodes of a given level before moving on to the nodes at the next level.
3.3. Let us consider the example graph from the previous section and execute the BFS algorithm:
graph = { "A" : ["B","D"],
"B" : ["A","C","E"],
"C" : ["B","F"],
"D" : ["A","E"],
"E" : ["B","D","F","G"],
"F" : ["C","E","H"],
"G" : ["E","H"],
"H" : ["F","G"] }
bfs(graph, "A")
At the first iteration, the starting vertex “A” is marked as visited, and it is added to the queue. The queue now contains A.
visited = {'A'}
queue = ['A']
Dequeue vertex “A” and print it:
visited = {'A'}
queue = []
Print A
Since the dequeued vertex “A” has two adjacent vertices, B and D, we add them to the end of the queue. The queue now contains B and D.
visited = {'A', 'B', 'D'}
queue = ['B', 'D']
Print B
Dequeue vertex B and print it. Since B has three adjacent vertices, A, C, and E, we add them to the end of the queue.
The queue now contains D, A, C, and E.
visited = {'A', 'B', 'C', 'D', 'E'}
queue = ['D', 'A', 'C', 'E']
Print D
Dequeue vertex D and print it. Since D has two adjacent vertices, A and E, we add them to the end of the queue.
The queue now contains A, C, E, and E.
visited = {'A', 'B', 'C', 'D', 'E'}
queue = ['A','C', 'E', 'E']
Print C
Dequeue vertex A and print it. A has one adjacent vertex B, which has already been visited.
We skip this vertex and move on to the next vertex in the queue, which is C.
visited = {'A', 'B', 'C', 'D', 'E'}
queue = ['C', 'E', 'E']
Print E
Dequeue vertex C and print it. Since C has two adjacent vertices B and F, we add them to the end of the queue.
The queue now contains E, E, B, F.
visited = {'A', 'B', 'C', 'D', 'E', 'F'}
queue = ['E', 'E', 'B', 'F']
Print E
Dequeue vertex E and print it. E has four adjacent vertices, B, D, F, and G.
We add them to the end of the queue. The queue now contains E, B, F, G, and F.
visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}
queue = ['B', 'F', 'G', 'F']
Print B
Dequeue vertex B and print it. The queue now contains F, G, F, A, and C.
visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}
queue = ['F', 'G', 'F', 'A', 'C']
Print F
And so on, until all the vertices of the graph have been visited.
4. Conclusion
In this article, we have discussed the implementation of the BFS algorithm in Python. We have also gone through a detailed explanation of the execution of the BFS algorithm.
BFS is a powerful algorithm that is used for graph traversal, shortest path algorithms, network analysis, and more. Understanding the BFS algorithm is essential for anyone interested in computer science and data structures.
5. Conclusion
In this article, we have discussed the Breadth-First Search (BFS) algorithm, which is a popular traversal technique used in graph theory. We have provided a definition of BFS, discussed its implementation in Python, and demonstrated its execution on a sample graph.
BFS is a simple and efficient algorithm that visits all the vertices of a graph in breadth-first order. It is used for various applications such as shortest path algorithms, network analysis, and social network analysis.
One of the significant advantages of BFS over other algorithms is that it guarantees finding the shortest path for unweighted graphs. We first started with an introduction to graph theory, where we discussed graphs’ various representations and real-world applications.
We then went on to explain the importance of graph traversal techniques, where we covered the definition of BFS as a traversal technique. To implement the BFS algorithm in Python, we created a graph using an adjacency list, which is a dictionary where each key corresponds to a vertex, and the value is a list of its adjacent vertices.
We also went through the different steps of the BFS algorithm, which include marking the starting vertex as visited, adding it to the queue, dequeuing the vertex and iterating over its adjacent vertices. To demonstrate the execution of the BFS algorithm in Python, we used a sample graph with eight nodes and 11 edges and printed the visited vertices in breadth-first order.
We also discussed the importance of debugging when implementing the BFS algorithm and the use of visualization tools to debug. In conclusion, understanding the BFS algorithm is essential in computer science, particularly for data structures and algorithms.
The BFS algorithm is widely used for traversing large graphs in an efficient and systematic manner, and this article has provided a comprehensive guide on how to implement and execute BFS in Python. Whether you’re a beginner or an experienced programmer, the BFS algorithm is an essential piece of knowledge that can enable you to solve complex problems related to graph theory.
The BFS algorithm represents one of the fundamental concepts in computer science, and acquiring a good understanding of it marks a strong foundation for mastering other computing concepts and techniques. In this article, we have discussed the Breadth-First Search (BFS) algorithm, which is a popular traversal technique used in graph theory.
We defined BFS, went through its implementation in Python, and demonstrated the execution of the algorithm on a sample graph. BFS is a simple and efficient algorithm that guarantees finding the shortest path for unweighted graphs, making it useful for various applications like shortest path algorithms and network analysis.
Understanding the BFS algorithm is crucial in computer science and data structures as it forms the basis for mastering other computing concepts and techniques. By reading this article, readers can gain a better understanding of the BFS algorithm and its implementation in Python, which is an essential piece of knowledge that can enable them to solve complex problems related to graph theory.