Practice › Graphs
BFS of a Graph
Easy · Graphs · Asked at Amazon, Microsoft, Google, Samsung
Print the breadth-first search order starting from node 1. When a node has several unvisited neighbours, visit them in increasing order. Print only the nodes reachable from node 1.
Input
First line: n m. Next m lines: u v — an undirected edge (nodes are 1..n).
Output
The BFS order, space-separated.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ m ≤ 2 · 10^5
Sort every adjacency list first. Mark a node as visited when you push it into the queue, not when you pop it.
Example 1
Input
5 4 1 2 1 3 2 4 3 5
Output
1 2 3 4 5
Example 2
Input
4 3 1 4 1 2 4 3
Output
1 2 4 3
Hints
- Sort each adjacency list so neighbours are taken in increasing order.
- Use a queue. Mark a node visited when it is pushed — otherwise it can be pushed twice.
Approach
Build adjacency lists from the edges and sort them. Push node 1 and mark it. Repeatedly pop the front node, output it, and push each unvisited neighbour (marking it immediately). The queue processes nodes in order of distance from node 1, which is the BFS order.
Complexity: O(n + m log m) time (sorting) · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (auto &a : adj) sort(a.begin(), a.end());
vector<bool> seen(n + 1, false);
vector<int> order;
queue<int> q;
q.push(1);
seen[1] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : adj[u])
if (!seen[v]) seen[v] = true, q.push(v);
}
for (size_t i = 0; i < order.size(); i++) cout << order[i] << (i + 1 < order.size() ? " " : "\n");
return 0;
}Python solution
import sys
from collections import deque
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v = data[2 + 2 * i], data[3 + 2 * i]
adj[u].append(v)
adj[v].append(u)
for a in adj:
a.sort()
seen = [False] * (n + 1)
seen[1] = True
order, q = [], deque([1])
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
if not seen[v]:
seen[v] = True
q.append(v)
print(*order)Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int m = (int) in.nval;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
in.nextToken();
int u = (int) in.nval;
in.nextToken();
int v = (int) in.nval;
adj.get(u).add(v);
adj.get(v).add(u);
}
for (List<Integer> a : adj) Collections.sort(a);
boolean[] seen = new boolean[n + 1];
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(1);
seen[1] = true;
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
int u = q.poll();
sb.append(sb.length() > 0 ? " " : "").append(u);
for (int v : adj.get(u))
if (!seen[v]) { seen[v] = true; q.add(v); }
}
System.out.println(sb);
}
}