Detect Cycle in Directed Graph using BFS DFS Algo

The problem, simply

You get a directed graph: V rooms and one-way arrows between them. A cycle is a path that follows arrows and comes back to a room it already passed.

Return true if the graph has at least one cycle, and false if it has none.

A story to remember it

Picture it

Examples

Way 1: the simple way

For every room, ask: can I leave this room and come back to it? Start a search from each room's neighbors and see if it reaches the room again.

1. For each room s, put its neighbors in a waiting line and mark them seen.
2. Search outward. If you ever reach s, return true.
3. If no room can get back to itself, return false.

class DirectedCycleBrute {
    public static boolean hasCycle(int V, List<List<Integer>> adj) {
        for (int s = 0; s < V; s++) {
            boolean[] seen = new boolean[V];
            Deque<Integer> line = new ArrayDeque<>();
            for (int v : adj.get(s)) if (!seen[v]) { seen[v] = true; line.add(v); }
            while (!line.isEmpty()) {
                int u = line.poll();
                if (u == s) return true;                  // walked back home
                for (int v : adj.get(u)) {
                    if (!seen[v]) { seen[v] = true; line.add(v); }
                }
            }
        }
        return false;
    }
}

How long it takes: one search per room, each O(V + E), so O(V * (V + E)). Extra room: the seen array and the line, O(V).

Way 2: the clever way

One depth first walk, with three kinds of rooms: new, on the walk (the string is in it), and done.

1. Mark the room "on the walk" when you step in.
2. Try each arrow out. If it leads to a room that is on the walk, return true. If it leads to a new room, walk into it. If it leads to a done room, skip it.
3. When all arrows are tried, mark the room "done" and step back.
4. Start a walk from every room that is still new.

class DirectedCycleDfs {
    static final int NEW = 0, ON_WALK = 1, DONE = 2;

    public static boolean hasCycle(int V, List<List<Integer>> adj) {
        int[] state = new int[V];
        for (int i = 0; i < V; i++) {
            if (state[i] == NEW && walk(i, adj, state)) return true;
        }
        return false;
    }

    static boolean walk(int u, List<List<Integer>> adj, int[] state) {
        state[u] = ON_WALK;                               // the string is in this room
        for (int v : adj.get(u)) {
            if (state[v] == ON_WALK) return true;         // back into our own path
            if (state[v] == NEW && walk(v, adj, state)) return true;
        }
        state[u] = DONE;                                  // roll the string back
        return false;
    }
}

How long it takes: every room is stepped into once and every arrow is tried once, O(V + E). Extra room: the state array and the call stack, O(V).

Another way: peel off rooms with no arrows in

This is Kahn's way, with a waiting line, a queue. A room with no arrows coming in can be handled first. Remove it and its arrows, and new rooms may lose their last incoming arrow. If the graph has no cycle, you can peel off every room. Rooms on a cycle always keep one arrow coming in, so they never get peeled.

1. Count the arrows coming into each room.
2. Put every room with count 0 in the line.
3. Take a room out, count it, and lower the count of each room it points to. Any that hit 0 join the line.
4. If you counted fewer than V rooms, there is a cycle.

class DirectedCycleKahn {
    public static boolean hasCycle(int V, List<List<Integer>> adj) {
        int[] arrowsIn = new int[V];
        for (int u = 0; u < V; u++) for (int v : adj.get(u)) arrowsIn[v]++;
        Deque<Integer> line = new ArrayDeque<>();
        for (int i = 0; i < V; i++) if (arrowsIn[i] == 0) line.add(i);
        int peeled = 0;
        while (!line.isEmpty()) {
            int u = line.poll();
            peeled++;
            for (int v : adj.get(u)) {
                if (--arrowsIn[v] == 0) line.add(v);      // its last arrow in is gone
            }
        }
        return peeled < V;                                // someone was stuck in a loop
    }
}

Same O(V + E) time and O(V) extra room, and no recursion, so it is safe for very deep graphs.

Watch out for

• Forgetting to mark a room "done" when you step back. Then it stays "on the walk" forever and causes false alarms later.
• Starting only from room 0. A loop that 0 cannot reach is missed. Loop over all rooms.
• Self-loops: the DFS sees state[u] == ON_WALK for v == u and correctly says true.

What interviewers ask next

• How do you print the cycle? Keep parent[v] = u when you walk in. When you find the arrow u to v with v on the walk, follow parents from u back to v.
• Can you finish all courses with these prerequisites? That is this exact question: possible only if there is no cycle.
• Give a valid order of tasks. Kahn's peel order is a topological order. With DFS, the reverse of the "done" order is one too.
• Why does the undirected parent trick not work here? In a directed graph, an arrow back to an already seen room may lead to a finished side branch, not to your own path. You must know which rooms are still on the path.

Remember this

Grown-up words: rooms are vertices, one-way doors are directed edges, the string is the recursion stack, the three states are often called white, gray and black, a "done" sticker is a fully explored vertex, peeling rooms with no arrows in is Kahn's algorithm, and the count of arrows in is the in-degree.