Breadth First Search (BFS)

Description

Breadth First Search (BFS) is a graph traversal algorithm that explores all vertices at the present depth before moving on to vertices at the next depth level. Starting from a chosen source vertex, it systematically explores the graph layer by layer, making it particularly effective for:

• Finding shortest paths in unweighted graphs
• Testing if a graph is bipartite
• Finding all nodes within one connected component
• Finding the shortest cycle in an unweighted graph

Visualization

How It Works

BFS works by following these steps:

1. Start at a chosen vertex (root node)
2. Explore all neighboring vertices at the present depth
3. Move to the next level of vertices
4. Repeat until all vertices have been visited

Implementation

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')  # Process current vertex
        
        # Add all unvisited neighbors to queue
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

#include <queue>
#include <vector>
#include <unordered_set>

void bfs(const vector<vector<int>>& graph, int start) {
    unordered_set<int> visited;
    queue<int> q;
    
    visited.insert(start);
    q.push(start);
    
    while (!q.empty()) {
        int vertex = q.front();
        q.pop();
        cout << vertex << " ";  // Process current vertex
        
        // Add all unvisited neighbors to queue
        for (int neighbor : graph[vertex]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

public class BFS {
    public void Search(Dictionary<int, List<int>> graph, int start)
    {
        var visited = new HashSet<int>();
        var queue = new Queue<int>();
        
        visited.Add(start);
        queue.Enqueue(start);
        
        while (queue.Count > 0)
        {
            int vertex = queue.Dequeue();
            Console.Write($"{vertex} ");  // Process current vertex
            
            // Add all unvisited neighbors to queue
            foreach (int neighbor in graph[vertex])
            {
                if (!visited.Contains(neighbor))
                {
                    visited.Add(neighbor);
                    queue.Enqueue(neighbor);
                }
            }
        }
    }
}

Complexity Analysis

Where V is the number of vertices and E is the number of edges in the graph.

Advantages and Disadvantages

Applications

• Shortest path finding in unweighted graphs
• Web crawling
• Social networking (finding connections)
• GPS navigation systems
• Peer-to-peer networks
• Broadcasting in network