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