Implement BFS algorithm

The problem, simply

You get a graph: some dots (we will call them rooms) and some lines between them (doors). A door works both ways. You also get a starting room.

Visit every room you can reach. First the rooms one door away, then the rooms two doors away, then three, and so on. Give back the rooms in the order you visited them.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write the doors in a big square table. Row u, column v holds a 1 when there is a door between u and v. This table is called an adjacency matrix.

1. Put the start room in the waiting line and mark it seen.
2. Take the room at the front of the line and write it down.
3. To find its neighbours, read its whole row of the table. Every 1 in an unseen column is a new room: mark it seen and add it to the back of the line.
4. Repeat until the line is empty.

import java.util.*;

class Solution {
    public List<Integer> bfs(int V, int[][] edges, int start) {
        int[][] table = new int[V][V];
        for (int[] e : edges) {
            table[e[0]][e[1]] = 1;          // a door works both ways
            table[e[1]][e[0]] = 1;
        }
        List<Integer> order = new ArrayList<>();
        boolean[] seen = new boolean[V];
        Queue<Integer> line = new ArrayDeque<>();
        seen[start] = true;
        line.add(start);
        while (!line.isEmpty()) {
            int u = line.poll();
            order.add(u);
            for (int v = 0; v < V; v++) {      // read the whole row
                if (table[u][v] == 1 && !seen[v]) {
                    seen[v] = true;
                    line.add(v);
                }
            }
        }
        return order;
    }
}

How long it takes: every room reads a full row of V cells, so O(V^2), even when there are only a few doors. Extra room: the table has V * V cells, O(V^2).

Way 2: the clever way

Give every room its own short list of neighbours, an adjacency list. Now a room only looks at the doors it really has.

1. Build the neighbour lists from the edges. Add each door to both rooms.
2. Mark the start room seen and put it in the waiting line, a queue.
3. Take the room at the front and write it down.
4. For each neighbour on its list: if it is not seen yet, mark it seen right now and add it to the back of the line.
5. Repeat until the line is empty.

Because the line is first come, first served, all rooms one door away come out before any room two doors away. That is why the order goes ring by ring.

import java.util.*;

class Solution {
    public List<Integer> bfs(int V, int[][] edges, int start) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);        // a door works both ways
            adj.get(e[1]).add(e[0]);
        }
        List<Integer> order = new ArrayList<>();
        boolean[] seen = new boolean[V];
        Queue<Integer> line = new ArrayDeque<>();
        seen[start] = true;                 // mark when you add, not when you take
        line.add(start);
        while (!line.isEmpty()) {
            int u = line.poll();            // leave from the front
            order.add(u);
            for (int v : adj.get(u)) {      // only the doors this room really has
                if (!seen[v]) {
                    seen[v] = true;
                    line.add(v);            // join at the back
                }
            }
        }
        return order;
    }
}

How long it takes: every room joins the line once, and every door is looked at twice (once from each side), so O(V + E). Extra room: the seen list and the line hold at most V rooms, O(V). The neighbour lists take O(V + E), but that is the input.

Watch out for

• Forgetting that a door goes both ways. For an undirected graph, add v to u's list and u to v's list.
• A graph in pieces. One search only reaches one piece. Loop over all rooms and start a new search from every unseen one.
• Using a stack instead of a queue. Then you dive deep first, which is depth first search, not rings.
• The order inside a ring depends on the order of the neighbour lists. If the judge expects a fixed order, keep the lists in input order (or sorted).

What interviewers ask next

• Shortest path in a graph with no weights? Breadth first search already finds it. Store dist[v] = dist[u] + 1 when you add v; that is what the badges in the animation show.
• How do you rebuild the path, not just the length? Store parent[v] = u when you add v, then walk back from the target.
• How many pieces does the graph have? Start a search from every unseen room and count how many searches you started.
• Many starting rooms at once (rotting oranges, nearest exit)? Put all of them in the line at the start with distance 0. It works like one search from a super start.
• Is the graph two-colourable (bipartite)? Run the search and give each new room the opposite colour of the room that found it. A door between two rooms of the same colour means no.

Remember this

Grown-up words: rooms are vertices, doors are edges, the neighbour lists are an adjacency list, the big table is an adjacency matrix, the waiting line is a queue, the rings are levels, and visiting ring by ring is breadth first search (BFS).