AntInLoop

Breadth-First Search (BFS) Algorithm Code Implementations

Complete Breadth-First Search (BFS) Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Breadth-First Search (BFS) Algorithm Guide ยท Launch Interactive Visualizer

C++ Implementation

// Breadth-First Search Implementation in C++
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

class BreadthFirstSearch {
public:
    static std::vector<int> breadthFirstSearch(const std::unordered_map<int, std::vector<int>>& graph, int start) {
        std::unordered_set<int> visited;
        std::queue<int> queue;
        std::vector<int> result;
        
        visited.insert(start);
        queue.push(start);
        
        while (!queue.empty()) {
            int current = queue.front();
            queue.pop();
            result.push_back(current);
            
            // Get all adjacent vertices
            auto it = graph.find(current);
            if (it != graph.end()) {
                for (int neighbor : it->second) {
                    if (visited.find(neighbor) == visited.end()) {
                        visited.insert(neighbor);
                        queue.push(neighbor);
                    }
                }
            }
        }
        
        return result;
    }
    
    // BFS with distance tracking
    static std::unordered_map<int, int> breadthFirstSearchWithDistance(const std::unordered_map<int, std::vector<int>>& graph, int start) {
        std::unordered_set<int> visited;
        std::queue<std::pair<int, int>> queue;
        std::unordered_map<int, int> distances;
        
        visited.insert(start);
        queue.push({start, 0});
        distances[start] = 0;
        
        while (!queue.empty()) {
            auto [node, distance] = queue.front();
            queue.pop();
            
            auto it = graph.find(node);
            if (it != graph.end()) {
                for (int neighbor : it->second) {
                    if (visited.find(neighbor) == visited.end()) {
                        visited.insert(neighbor);
                        distances[neighbor] = distance + 1;
                        queue.push({neighbor, distance + 1});
                    }
                }
            }
        }
        
        return distances;
    }
    
    // BFS for finding shortest path
    static std::vector<int> breadthFirstSearchShortestPath(const std::unordered_map<int, std::vector<int>>& graph, int start, int end) {
        std::unordered_set<int> visited;
        std::queue<std::vector<int>> queue;
        
        visited.insert(start);
        queue.push({start});
        
        while (!queue.empty()) {
            std::vector<int> path = queue.front();
            queue.pop();
            int node = path.back();
            
            if (node == end) {
                return path;
            }
            
            auto it = graph.find(node);
            if (it != graph.end()) {
                for (int neighbor : it->second) {
                    if (visited.find(neighbor) == visited.end()) {
                        visited.insert(neighbor);
                        std::vector<int> newPath = path;
                        newPath.push_back(neighbor);
                        queue.push(newPath);
                    }
                }
            }
        }
        
        return {}; // No path found
    }
    
    // BFS for connected components
    static std::vector<std::vector<int>> breadthFirstSearchConnectedComponents(const std::unordered_map<int, std::vector<int>>& graph) {
        std::unordered_set<int> visited;
        std::vector<std::vector<int>> components;
        
        for (const auto& [node, neighbors] : graph) {
            if (visited.find(node) == visited.end()) {
                std::vector<int> component;
                std::queue<int> queue;
                
                visited.insert(node);
                component.push_back(node);
                queue.push(node);
                
                while (!queue.empty()) {
                    int current = queue.front();
                    queue.pop();
                    
                    auto it = graph.find(current);
                    if (it != graph.end()) {
                        for (int neighbor : it->second) {
                            if (visited.find(neighbor) == visited.end()) {
                                visited.insert(neighbor);
                                component.push_back(neighbor);
                                queue.push(neighbor);
                            }
                        }
                    }
                }
                
                components.push_back(component);
            }
        }
        
        return components;
    }
};

JAVA Implementation

// Breadth-First Search Implementation in Java
import java.util.*;

public class BreadthFirstSearch {
    public static List<Integer> breadthFirstSearch(Map<Integer, List<Integer>> graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        
        visited.add(start);
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);
            
            // Get all adjacent vertices
            List<Integer> neighbors = graph.getOrDefault(current, new ArrayList<>());
            for (int neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        
        return result;
    }
    
    // BFS with distance tracking
    public static Map<Integer, Integer> breadthFirstSearchWithDistance(Map<Integer, List<Integer>> graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        Map<Integer, Integer> distances = new HashMap<>();
        
        visited.add(start);
        queue.offer(new int[]{start, 0});
        distances.put(start, 0);
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int node = current[0];
            int distance = current[1];
            
            List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
            for (int neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    distances.put(neighbor, distance + 1);
                    queue.offer(new int[]{neighbor, distance + 1});
                }
            }
        }
        
        return distances;
    }
    
    // BFS for finding shortest path
    public static List<Integer> breadthFirstSearchShortestPath(Map<Integer, List<Integer>> graph, int start, int end) {
        Set<Integer> visited = new HashSet<>();
        Queue<List<Integer>> queue = new LinkedList<>();
        
        visited.add(start);
        queue.offer(Arrays.asList(start));
        
        while (!queue.isEmpty()) {
            List<Integer> path = queue.poll();
            int node = path.get(path.size() - 1);
            
            if (node == end) {
                return path;
            }
            
            List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
            for (int neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    List<Integer> newPath = new ArrayList<>(path);
                    newPath.add(neighbor);
                    queue.offer(newPath);
                }
            }
        }
        
        return null; // No path found
    }
    
    // BFS for connected components
    public static List<List<Integer>> breadthFirstSearchConnectedComponents(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        List<List<Integer>> components = new ArrayList<>();
        
        for (int node : graph.keySet()) {
            if (!visited.contains(node)) {
                List<Integer> component = new ArrayList<>();
                Queue<Integer> queue = new LinkedList<>();
                
                visited.add(node);
                component.add(node);
                queue.offer(node);
                
                while (!queue.isEmpty()) {
                    int current = queue.poll();
                    List<Integer> neighbors = graph.getOrDefault(current, new ArrayList<>());
                    
                    for (int neighbor : neighbors) {
                        if (!visited.contains(neighbor)) {
                            visited.add(neighbor);
                            component.add(neighbor);
                            queue.offer(neighbor);
                        }
                    }
                }
                
                components.add(component);
            }
        }
        
        return components;
    }
}

JAVASCRIPT Implementation

// Breadth-First Search Implementation in JavaScript
function breadthFirstSearch(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];
  
  visited.add(start);
  
  while (queue.length > 0) {
    const current = queue.shift();
    result.push(current);
    
    // Get all adjacent vertices
    const neighbors = graph[current] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  
  return result;
}

// BFS with distance tracking
function breadthFirstSearchWithDistance(graph, start) {
  const visited = new Set();
  const queue = [{ node: start, distance: 0 }];
  const distances = new Map();
  
  visited.add(start);
  distances.set(start, 0);
  
  while (queue.length > 0) {
    const { node, distance } = queue.shift();
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        distances.set(neighbor, distance + 1);
        queue.push({ node: neighbor, distance: distance + 1 });
      }
    }
  }
  
  return distances;
}

// BFS for finding shortest path
function breadthFirstSearchShortestPath(graph, start, end) {
  const visited = new Set();
  const queue = [{ node: start, path: [start] }];
  
  visited.add(start);
  
  while (queue.length > 0) {
    const { node, path } = queue.shift();
    
    if (node === end) {
      return path;
    }
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push({ 
          node: neighbor, 
          path: [...path, neighbor] 
        });
      }
    }
  }
  
  return null; // No path found
}

// BFS for connected components
function breadthFirstSearchConnectedComponents(graph) {
  const visited = new Set();
  const components = [];
  
  for (const node in graph) {
    if (!visited.has(node)) {
      const component = [];
      const queue = [node];
      
      visited.add(node);
      component.push(node);
      
      while (queue.length > 0) {
        const current = queue.shift();
        const neighbors = graph[current] || [];
        
        for (const neighbor of neighbors) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            component.push(neighbor);
            queue.push(neighbor);
          }
        }
      }
      
      components.push(component);
    }
  }
  
  return components;
}

PYTHON Implementation

# Breadth-First Search Implementation in Python
from collections import deque

def breadth_first_search(graph, start):
    visited = set()
    queue = deque([start])
    result = []
    
    visited.add(start)
    
    while queue:
        current = queue.popleft()
        result.append(current)
        
        # Get all adjacent vertices
        neighbors = graph.get(current, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

# BFS with distance tracking
def breadth_first_search_with_distance(graph, start):
    visited = set()
    queue = deque([(start, 0)])
    distances = {}
    
    visited.add(start)
    distances[start] = 0
    
    while queue:
        node, distance = queue.popleft()
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                distances[neighbor] = distance + 1
                queue.append((neighbor, distance + 1))
    
    return distances

# BFS for finding shortest path
def breadth_first_search_shortest_path(graph, start, end):
    visited = set()
    queue = deque([(start, [start])])
    
    visited.add(start)
    
    while queue:
        node, path = queue.popleft()
        
        if node == end:
            return path
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # No path found

# BFS for connected components
def breadth_first_search_connected_components(graph):
    visited = set()
    components = []
    
    for node in graph:
        if node not in visited:
            component = []
            queue = deque([node])
            
            visited.add(node)
            component.append(node)
            
            while queue:
                current = queue.popleft()
                neighbors = graph.get(current, [])
                
                for neighbor in neighbors:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        component.append(neighbor)
                        queue.append(neighbor)
            
            components.append(component)
    
    return components