BFS is a graph traversal technique to explore and analyse graphs. It systematically visits all the neighbouring vertices of a current vertex before moving on to the next level of vertices.
Read on to learn about BFS.
Understanding Graph Traversal Algorithm in Data Structure
Graph traversal algorithms in data structures are essential techniques for systematically visiting and exploring each node or vertex within a graph. They play a crucial role in understanding the relationships and connectivity present in complex data structures.
Graph traversal algorithms facilitate the examination of graphs by navigating through their nodes in a specific order.
Graph traversal algorithms are widely used in network analysis, routing algorithms, and web crawling, among other fields. They empower efficient analysis and ease the decision-making processes.
The two main approaches for graph traversal are:
- DFS or the depth-first search algorithm (DFS)
- BFS or the breadth first search algorithm
Unlike BFS, DFS explores a graph by traversing as far as possible along each branch before backtracking.
What is Breadth First Search Algorithm?
BFS algorithm starts from a given source vertex and explores the graph layer by layer, examining all the vertices at the same level before descending further. It uses a queue data structure to maintain the order of exploration, ensuring that vertices are visited in a breadth first manner.
Understanding How BFS Algorithm Works
To implement BFS, a queue data structure is used to maintain the exploration order. The algorithm begins by enqueuing the source vertex and marking it as visited. Then, while the queue is not empty, it dequeues a vertex, visits its adjacent unvisited vertices, enqueues them, and marks them as visited.
This process continues until all vertices have been visited or until the desired condition is met. Using this approach, BFS guarantees that vertices in the BFS graph are visited in order of their distance from the source vertex.
Need for the Breadth First Search Algorithm
There are several reasons why using the BFS algorithm is essential:
- Shortest Path Finding: BFS guarantees the shortest path between two vertices in an unweighted graph, making it an ideal choice for route planning or navigation systems.
- Completeness: BFS is complete for finite graphs, ensuring it explores the entire graph and visits all reachable vertices.
- Breadth-First Traversal: BFS explores vertices at the same level before moving to deeper levels, providing a breadth-first exploration of the graph.
- Minimal Memory Usage: BFS uses minimal memory compared to other graph traversal algorithms like DFS, as it only needs to store vertices in the queue.
- Optimal Solution and Accuracy: In unweighted graphs, BFS ensures that the first occurrence of a target vertex will yield the shortest path, making it efficient for searching tasks.
Programmers often use breadth first search Python for various applications in graph theory and data structures.
Gain an in-depth understanding of graph traversal algorithms and their structures with an MS in Full Stack AI and ML course.
BFS Algorithm Rules
Some important rules to remember when implementing the breadth first search algorithm for graph traversal:
- Queue: Use a queue data structure to keep track of the vertices to be visited in the breadth first traversal.
- Visited Marking: Maintain a visited array or set to keep track of the vertices that have been visited during the traversal.
- Enqueue and Mark: Enqueue the starting vertex into the queue and mark it as visited.
- Dequeue and Visit Neighbors: While the queue is not empty, dequeue a vertex, visit it, and enqueue its unvisited neighbouring vertices.
- Order of Visit: Visit the vertices in the order they were enqueued, ensuring a breadth-first exploration.
- Avoid Revisiting: Check if a vertex has already been visited before enqueueing it to avoid revisiting vertices.
- Termination: Terminate the algorithm when the queue becomes empty, indicating that all reachable vertices have been visited.
- Shortest Path: If finding the shortest path, track the parent of each vertex to reconstruct the path once the destination is reached.
Top Machine Learning and AI Courses Online
BFS Algorithm Architecture
The architecture of the BFS algorithm is broken down below:
- Queue: The BFS algorithm uses a queue data structure to maintain an orderly process when exploring vertex positions. The queue follows the First-In, First-Out (FIFO) principle to ensure that vertices are processed in their order of arrival in the queue.
- Visited Array or Set: A visited array or set tracks the vertices visited during BFS traversal and ensures that each vertex is processed only once. It ensures no revisited vertices occur while processing each vertex correctly only once.
- BFS Tree: As the BFS algorithm explores the graph, it constructs a BFS tree. The BFS tree represents the traversal path and reveals the hierarchical relationships between vertices. Each vertex in the tree has its parent, the vertex discovered during the traversal.
- Enqueue and Mark: The BFS algorithm starts by enqueueing the source vertex into the queue and marking it as visited.
- Dequeue and Visit Neighbours: While the queue is not empty, the algorithm dequeues a vertex, visits it, and explores its neighbouring vertices. Each unvisited neighbour is enqueued into the queue and marked as visited.
- Termination: The BFS algorithm terminates when the queue becomes empty. This indicates that all reachable vertices have been visited and processed.
Enrol for the Machine Learning Course from the World’s top Universities. Earn Master, Executive PGP, or Advanced Certificate Programs to fast-track your career.
Pseudocode Of Breadth First Search Algorithm
BFS(graph, start_vertex): queue = create an empty queue visited = create an empty set or array to track visited vertices enqueue start_vertex into the queue add start_vertex to visited while queue is not empty: current_vertex = dequeue from the queue process(current_vertex) // e.g., print or perform operations on the current_vertex for each neighbour in graph[current_vertex]: if neighbour is not in visited: enqueue neighbour into the queue add neighbour to visited
The BFS algorithm starts by initialising an empty queue and an empty set/array to track visited vertices. It begins the traversal from the start_vertex, which is enqueued into the queue and marked as visited.
The algorithm then enters a while loop that continues as long as its queue remains nonempty. At each iteration, a vertex at the front of its queue (denoted by current_vertex) is removed and processed, either through operations on it or printing it out.
Next, the algorithm explores all the neighbours of the current_vertex. For each unvisited neighbour, it enqueues the neighbour into the queue and marks it as visited.
The process continues until the queue becomes empty, indicating that all reachable vertices from the start_vertex have been visited.
You can also check out our free courses offered by upGrad in Management, Data Science, Machine Learning, Digital Marketing, and Technology. All of these courses have top-notch learning resources, weekly live lectures, industry assignments, and a certificate of course completion – all free of cost!
BFS Algorithm Example
Let’s consider the following graph to understand a BFS example:
A––B
| |
C––D
We want to perform a breadth first search (BFS) traversal from vertex A to visit all the vertices.
Step 1:
- Enqueue vertex A into the queue.
- Mark A as visited.
- Queue: [A]
- Visited: {A}
Step 2:
- Dequeue A from the queue and process it (e.g., print or perform operations).
- Enqueue its neighbours, B and C, into the queue (as they have yet to be visited).
- Mark B and C as visited.
- Queue: [B, C]
- Visited: {A, B, C}
Step 3:
- Dequeue B from the queue and process it.
- Enqueue its neighbour D into the queue (as it is not visited yet).
- Mark D as visited.
- Queue: [C, D]
- Visited: {A, B, C, D}
Step 4:
- Dequeue C from the queue and process it.
- There are no unvisited neighbours of C, so no vertices are enqueued.
- Queue: [D]
- Visited: {A, B, C, D}
Step 5:
- Dequeue D from the queue and process it.
- There are no unvisited neighbours of D, so no vertices are enqueued.
- Queue: []
- Visited: {A, B, C, D}
The BFS algorithm has now traversed all vertices reachable from the starting vertex A in a breadth-first manner. The order of traversal is A, B, C, and D.
Complexities Associated With Breadth First Search Algorithm
The complexity of the breadth first search algorithm can be analysed in terms of time and space complexity.
1.Time Complexity
BFS has an O(V + E) time complexity, where V represents the number of nodes (vertices) in the graph, and E represents its edges. When dequeuing from its queue or exploring its adjacent vertices, BFS attempts to visit all nodes and edges once. Thus its time complexity increases linearly as more nodes and edges enter or exit it.
2. Space Complexity
Space complexity for BFS grows linearly with the number of vertices in a graph (V), represented as an integer value. This is because even under extreme conditions, the BFS queue can simultaneously contain all vertices in its maximum level traversal. Furthermore, its visited array or set requires O(V) space to store visited vertices visited during traversal; hence BFS grows linearly in space complexity with each increase in graph vertex count.
In-demand Machine Learning Skills
Breadth First Search Algorithm Code Applications
Here are a few examples of the numerous applications of the BFS algorithm in various domains, showcasing its versatility and usefulness in graph exploration and analysis:
- Shortest Path: BFS can be used to find the shortest path between two vertices in an unweighted graph. The shortest path can be reconstructed by tracking the parent nodes during traversal.
- Connectivity: BFS can determine whether a graph is connected or not. The graph is connected if BFS reaches all vertices from a given source vertex.
- Web Crawling: BFS is widely used in web crawling or web scraping. It helps explore web pages systematically by following links and discovering new pages at each level.
- Social Network Analysis: BFS can help analyse social networks, identify clusters, find the shortest path between users, or calculate measures like degrees of separation.
- Bipartite Graphs: BFS can determine whether a graph is bipartite or not. It can colour the vertices with two different colours such that no two adjacent vertices have the same colour.
- Minimum Spanning Tree: BFS can be used to find the minimum spanning tree (MST) of a connected, weighted graph when all edge weights are equal.
- Puzzle Solving: BFS can solve puzzles like the sliding tile puzzle or the maze problem, finding the shortest path to the goal state.
- Network Routing: BFS is used in network routing algorithms, such as finding the shortest path between routers or determining the best route for data packets.
Conclusion
The Breadth First Search (BFS) algorithm is an invaluable tool for exploring and analysing graphs in a breadth-first manner. Its efficiency, accuracy in finding the shortest path, and versatility in various applications make it a fundamental technique in data structures and algorithms.
Aspiring IT professionals or software developers looking to enhance their skills and master graph traversal algorithms like DFS and BFS can check out upGrad’s Advanced Certificate Programme in Machine Learning & NLP from IIITB. Put yourself at the forefront of a technologically evolving landscape with upGrad.
