Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Sort each adjacency list so neighbours are taken in increasing order.
  2. 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);
    }
}

Solve BFS of a Graph online · All practice problems