(BFS) is a graph algorithm that explores neighboring vertices before moving to the next level. It uses a to visit vertices in a first-in, first-out order, ensuring a systematic level-by-level of the graph.
BFS has various applications, including finding the shortest path in unweighted graphs, identifying connected components, and checking if a graph is bipartite. With a of O(V + E) and of O(V), BFS efficiently explores graphs in a breadth-wise manner.
Breadth-First Search (BFS) Algorithm
Characteristics of BFS algorithm
Top images from around the web for Characteristics of BFS algorithm
CS 360: Lecture 16: Breadth-First Search View original
Is this image relevant?
1 of 2
Graph traversal algorithm explores all neighboring vertices before moving to the next level (breadth-wise exploration)
Visits vertices in layers or levels, exploring all neighbors of the current level before progressing to the next level
Guarantees the shortest path between the starting and any other reachable vertex in an unweighted graph (shortest path property)
Utilizes a queue data structure to keep track of vertices to be visited (FIFO order)
Explores vertices in a first-in, first-out (FIFO) order, ensuring a systematic and level-by-level traversal
Discovers all vertices at a distance k from the starting vertex before discovering any vertices at distance k+1 (level-wise discovery)
Can be used to find the shortest path, identify connected components, or check if a graph is bipartite (various applications)
Queue-based BFS implementation
Choose a starting vertex and it into a queue data structure
Mark the starting vertex as visited to avoid revisiting it later
While the queue is not empty, perform the following steps:
a vertex from the front of the queue
Process the dequeued vertex (perform desired operations or computations)
Enqueue all unvisited neighbors of the dequeued vertex into the queue
Mark the neighboring vertices as visited to prevent duplicate visits
Repeat step 3 until the queue becomes empty, indicating that all reachable vertices have been explored
Pseudocode for BFS implementation:
function BFS(graph, startVertex):
queue = new Queue()
visited = new Set()
queue.enqueue(startVertex)
visited.add(startVertex)
while queue is not empty:
currentVertex = queue.dequeue()
process(currentVertex)
for each neighbor of currentVertex:
if neighbor is not in visited:
queue.enqueue(neighbor)
visited.add(neighbor)
Complexity analysis of BFS
Time complexity of BFS is O(V+E), where V represents the number of vertices and E represents the number of edges in the graph
In the worst case, BFS visits all vertices and traverses all edges in the graph
For a connected graph, E≥V−1, allowing the time complexity to be simplified to O(E)
Space complexity of BFS is O(V), determined by the maximum number of vertices in the queue at any given time
In the worst case, the queue may contain all vertices in one level, which can be up to O(V)
The visited set requires O(V) space to keep track of visited vertices throughout the traversal
Applications of BFS
Finding the shortest path in an unweighted graph
BFS guarantees the shortest path due to its level-wise exploration
Maintain a distance array or hash table to store the distance of each vertex from the starting vertex
Update the distance of each vertex when it is first encountered during the BFS traversal
The distance of the destination vertex from the starting vertex represents the shortest path length
Identifying connected components in an undirected graph
Run BFS from an unvisited vertex and mark all reachable vertices as part of the same connected component
Repeat the process starting from another unvisited vertex until all vertices have been visited
Each BFS traversal identifies a separate connected component
Checking if a graph is bipartite (can be divided into two disjoint sets with no edges within each set)
Assign colors (red and blue) to vertices during the BFS traversal
If any adjacent vertices have the same color, the graph is not bipartite
If the coloring is consistent throughout the traversal, the graph is bipartite