11.1 Breadth-First Search (BFS) Algorithm

Breadth-First Search (BFS) is a graph traversal algorithm that explores neighboring vertices before moving to the next level. It uses a queue to visit vertices in a first-in, first-out order, ensuring a systematic level-by-level exploration 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 time complexity of O(V + E) and space complexity 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

• 

  Queue Data Structure - Basics Behind View original

  Is this image relevant?

• 

  CS 360: Lecture 16: Breadth-First Search View original

  Is this image relevant?

• 

  Queue Data Structure - Basics Behind View original

  Is this image relevant?

• 

  CS 360: Lecture 16: Breadth-First Search View original

  Is this image relevant?

1 of 2

Top images from around the web for Characteristics of BFS algorithm

• 

  Queue Data Structure - Basics Behind View original

  Is this image relevant?

• 

  CS 360: Lecture 16: Breadth-First Search View original

  Is this image relevant?

• 

  Queue Data Structure - Basics Behind View original

  Is this image relevant?

• 

  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 vertex 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

1. Choose a starting vertex and enqueue it into a queue data structure
2. Mark the starting vertex as visited to avoid revisiting it later
3. While the queue is not empty, perform the following steps:
   • Dequeue 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
4. 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 \geq 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