Implement DFS Algo

The problem, simply

You get a graph: dots (rooms) joined by lines (doors). A door works both ways. You also get a starting room.

Visit every room you can reach, but go deep first: from a room, walk through the first door to a room you have not seen, and keep going. Only when you are stuck do you step back and try the next door. Give back the rooms in the order you first entered them.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep the doors in a big square table, an adjacency matrix: cell [u][v] is 1 when rooms u and v share a door.

1. Enter the start room: chalk it and write it down.
2. Read its whole row of the table, from column 0 to column V - 1.
3. The first 1 that leads to an unchalked room: go in there right away and repeat from step 1.
4. When the row is finished, go back to the room you came from and keep reading its row where you left off.

import java.util.*;

class Solution {
    public List<Integer> dfs(int V, int[][] edges, int start) {
        int[][] table = new int[V][V];
        for (int[] e : edges) {
            table[e[0]][e[1]] = 1;
            table[e[1]][e[0]] = 1;
        }
        List<Integer> order = new ArrayList<>();
        dive(table, start, new boolean[V], order);
        return order;
    }

    private void dive(int[][] table, int u, boolean[] seen, List<Integer> order) {
        seen[u] = true;                       // chalk mark
        order.add(u);
        for (int v = 0; v < table.length; v++) {   // read the whole row
            if (table[u][v] == 1 && !seen[v]) {
                dive(table, v, seen, order);  // go deeper right away
            }
        }
    }
}

How long it takes: every room reads a row of V cells, so O(V^2) no matter how few doors there are. Extra room: the table is O(V^2), plus the call stack.

Way 2: the clever way

Give each room its own list of neighbours, an adjacency list, so a room only looks at the doors it really has. The deep dive itself stays the same, and recursion keeps the ball of string for us: every room we are still inside waits on the call stack.

1. Build the neighbour lists. Add each door to both rooms.
2. dfs(u): chalk u and write it down.
3. For each neighbour v of u: if v has no chalk, call dfs(v) right now.
4. When the loop ends, dfs(u) returns, which is the same as following the string back.

import java.util.*;

class Solution {
    public List<Integer> dfs(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]);
            adj.get(e[1]).add(e[0]);
        }
        List<Integer> order = new ArrayList<>();
        dive(adj, start, new boolean[V], order);
        return order;
    }

    private void dive(List<List<Integer>> adj, int u, boolean[] seen, List<Integer> order) {
        seen[u] = true;                   // chalk mark
        order.add(u);
        for (int v : adj.get(u)) {        // only the doors this room has
            if (!seen[v]) {
                dive(adj, v, seen, order);   // go deeper; returning is walking back
            }
        }
    }
}

How long it takes: every room is entered once and every door is looked at from both sides, so O(V + E). Extra room: the chalk marks and the call stack, at most V deep, O(V).

Another way: your own stack

A very deep graph (a line of a million rooms) can overflow the call stack. You can hold the string yourself with a pile of rooms, a stack. Push neighbours in reverse order so the first neighbour comes off the top first, and chalk a room when you take it off the pile, because the same room can be pushed more than once.

import java.util.*;

class Solution {
    public List<Integer> dfs(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]);
            adj.get(e[1]).add(e[0]);
        }
        List<Integer> order = new ArrayList<>();
        boolean[] seen = new boolean[V];
        Deque<Integer> pile = new ArrayDeque<>();
        pile.push(start);
        while (!pile.isEmpty()) {
            int u = pile.pop();
            if (seen[u]) continue;            // pushed twice, already explored
            seen[u] = true;
            order.add(u);
            List<Integer> nb = adj.get(u);
            for (int i = nb.size() - 1; i >= 0; i--) {   // reverse, so the first door is on top
                if (!seen[nb.get(i)]) pile.push(nb.get(i));
            }
        }
        return order;
    }
}

This gives the same order as the recursive way, in O(V + E) time. The pile can hold up to O(E) entries because a room may be pushed once per door.

Watch out for

• Forgetting that doors go both ways in an undirected graph. Add the edge to both lists.
• A graph in pieces. Loop over all rooms and call dfs on every unseen one.
• In the stack version, pushing neighbours in normal order gives a valid deep dive but a different order than the recursion. Push in reverse when the judge wants the recursive order.
• Deep recursion in Java overflows at roughly ten thousand levels with the default stack. Use your own stack, or run the search in a thread with a bigger stack.

What interviewers ask next

• Count the pieces (connected components) of a graph? Start a dive from every unseen room and count the dives.
• Does an undirected graph have a loop? During the dive, if you meet a seen room that is not the room you just came from, there is a loop.
• Does a directed graph have a loop? Keep three marks: not seen, on the current string (on the stack), finished. Meeting a room that is still on the string means a loop.
• Topological order? Add each room to a list when its dfs finishes, then reverse the list.
• When is DFS better than BFS? When you need to explore whole paths (backtracking, loops, bridges, finishing order). BFS is the one for shortest paths in steps.

Remember this

Grown-up words: rooms are vertices, doors are edges, the chalk marks are the visited array, the ball of string is the recursion call stack (or an explicit stack), and diving deep first is depth first search (DFS).