BFS using STL for competitive coding
A STL based simple implementation of BFS using queue and vector in STL. The adjacency list is represented using vectors of vector.
In BFS, we start with a node.
- Create a queue and enqueue source into it.
- Mark source as visited.
- While queue is not empty, do following
- Dequeue a vertex from queue. Let this be f.
- Print f
- Enqueue all not yet visited adjacent of f and mark them visited.
Below is an example BFS starting from source vertex 1. Note that there can be multiple BFSs possible for a graph (even from a particular vertex).
For more details of BFS, refer this post .
The code here is simplified such that it could be used in competitive coding.
Implementation:
// A Quick implementation of BFS using
// vectors and queue
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<bool> v;
vector<vector<int> > g;
void edge(int a, int b)
{
g[a].pb(b);
// for undirected graph add this line
// g[b].pb(a);
}
void bfs(int u)
{
queue<int> q;
q.push(u);
v[u] = true;
while (!q.empty()) {
int f = q.front();
q.pop();
cout << f << " ";
// Enqueue all adjacent of f and mark them visited
for (auto i = g[f].begin(); i != g[f].end(); i++) {
if (!v[*i]) {
q.push(*i);
v[*i] = true;
}
}
}
}
// Driver code
int main()
{
int n, e;
cin >> n >> e;
v.assign(n, false);
g.assign(n, vector<int>());
int a, b;
for (int i = 0; i < e; i++) {
cin >> a >> b;
edge(a, b);
}
for (int i = 0; i < n; i++) {
if (!v[i])
bfs(i);
}
return 0;
}
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
public class Main {
static void bfs(Map<Integer, List<Integer> > graph,
int root)
{
// Set to keep track of visited vertices
boolean[] visited = new boolean[graph.size()];
// Queue for BFS traversal
Queue<Integer> queue = new ArrayDeque<>();
// Enqueue the root vertex
queue.add(root);
// Mark root as visited
visited[root] = true;
// BFS traversal
while (!queue.isEmpty()) {
// Dequeue a vertex from the queue
int vertex = queue.poll();
System.out.print(vertex + " ");
// Visit all adjacent vertices of the dequeued
// vertex
for (int neighbour : graph.getOrDefault(
vertex, new ArrayList<>())) {
// If neighbour has not been visited, mark
// it as visited and enqueue it
if (!visited[neighbour]) {
visited[neighbour] = true;
queue.add(neighbour);
}
}
}
}
public static void main(String[] args)
{
// Create a map to use as an adjacency list
Map<Integer, List<Integer> > graph
= new HashMap<>();
// Define the edges
int[][] edges
= { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 0, 4 },
{ 1, 5 }, { 2, 5 }, { 3, 6 }, { 4, 6 },
{ 5, 7 }, { 6, 7 } };
// Create the graph
for (int[] edge : edges) {
int a = edge[0];
int b = edge[1];
graph.computeIfAbsent(a, k -> new ArrayList<>())
.add(b);
graph.computeIfAbsent(b, k -> new ArrayList<>())
.add(a);
}
// Perform BFS starting from vertex 0
System.out.println("BFS starting from vertex 0:");
bfs(graph, 0);
}
}
from collections import defaultdict, deque
def bfs(graph, root):
visited = set()
queue = deque([root])
while queue:
# Dequeue a vertex from queue
vertex = queue.popleft()
print(vertex, end=" ")
# If not visited, mark it as visited, and enqueue it
for neighbour in graph[vertex]:
if neighbour not in visited:
queue.append(neighbour)
visited.add(neighbour)
# Create a dictionary to use as an adjacency list
graph = defaultdict(list)
edges = [(0, 1), (0, 2), (0, 3), (0, 4), (1, 5),
(2, 5), (3, 6), (4, 6), (5, 7), (6, 7)]
# Create the graph
for edge in edges:
a, b = edge
graph[a].append(b)
graph[b].append(a)
# Perform BFS
print("BFS starting from vertex 0:")
bfs(graph, 0)
function bfs(graph, root) {
// Set to keep track of visited vertices
let visited = new Array(Object.keys(graph).length).fill(false);
// Queue for BFS traversal
let queue = [];
// Enqueue the root vertex
queue.push(root);
// Mark root as visited
visited[root] = true;
// BFS traversal
while (queue.length !== 0) {
// Dequeue a vertex from the queue
let vertex = queue.shift();
process.stdout.write(vertex + " ");
// Visit all adjacent vertices of the dequeued vertex
for (let neighbour of graph[vertex] || []) {
// If neighbour has not been visited, mark it as visited and enqueue it
if (!visited[neighbour]) {
visited[neighbour] = true;
queue.push(neighbour);
}
}
}
}
// Define the edges
let edges = [
[0, 1], [0, 2], [0, 3], [0, 4],
[1, 5], [2, 5], [3, 6], [4, 6],
[5, 7], [6, 7]
];
// Create the graph
let graph = {};
for (let edge of edges) {
let [a, b] = edge;
graph[a] = graph[a] || [];
graph[b] = graph[b] || [];
graph[a].push(b);
graph[b].push(a);
}
// Perform BFS starting from vertex 0
console.log("BFS starting from vertex 0:");
bfs(graph, 0);
Input:
8 10
0 1
0 2
0 3
0 4
1 5
2 5
3 6
4 6
5 7
6 7
Output:
0 1 2 3 4 5 6 7
Time Complexity: O(V+E) – we traverse all vertices at least once and check every edge.
Auxiliary Space: O(V) – for using a queue to store vertices.