Graph · 5 of 43

Detect Cycle in UnDirected Graph using BFS DFS Algo

Walk the hallways of a maze with chalk and find out if some hallways form a loop.

Simple way: time O(E * (V + E))
room O(V + E)
Clever way: time O(V + E)
room O(V)

The problem, simply

You get an undirected graph: V spots and two-way hallways between them. A cycle is a loop of at least three different spots, where you can walk around and come back without using any hallway twice.

Return true if the graph has a cycle, and false otherwise.

A story to remember it

Picture it

graph

Spots 1, 2, 3 and 4 form a loop. Spot 0 hangs off the side and is not part of it.

rejected

Examples

A loop of four

In: V = 5, edges = [[0,1],[1,2],[2,3],[3,4],[4,1]]
Out: true

1, 2, 3, 4 and back to 1.

A tree

In: V = 4, edges = [[0,1],[0,2],[2,3]]
Out: false

Every spot has exactly one way to reach it from 0. No loop anywhere.

The loop is in another piece

In: V = 6, edges = [[0,1],[2,3],[3,4],[4,2]]
Out: true

A walk from 0 only sees 0 and 1. You must start new walks from 2 and 5 too, and 2, 3, 4 form a triangle.

One hallway

In: V = 2, edges = [[0,1]]
Out: false

From 1 you can see 0, but that is the hallway you came through. Going back is not a loop.

Way 1: the simple way

A hallway is part of a loop exactly when its two ends are still connected after you block that hallway. So try blocking each hallway, one at a time.

For each hallway u to v, pretend it is blocked.
Search from u. If you can still reach v, there is another way around: return true.
If no hallway passes the test, return false.

java

class UndirectedCycleBrute {
    public static boolean hasCycle(int V, int[][] edges) {
        List<List<int[]>> adj = new ArrayList<>();          // {neighbor, hallway number}
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int id = 0; id < edges.length; id++) {
            adj.get(edges[id][0]).add(new int[]{edges[id][1], id});
            adj.get(edges[id][1]).add(new int[]{edges[id][0], id});
        }
        for (int blocked = 0; blocked < edges.length; blocked++) {
            int from = edges[blocked][0], to = edges[blocked][1];
            boolean[] seen = new boolean[V];
            Deque<Integer> line = new ArrayDeque<>();
            line.add(from);
            seen[from] = true;
            while (!line.isEmpty()) {
                int u = line.poll();
                if (u == to) return true;                    // another way around
                for (int[] nb : adj.get(u)) {
                    if (nb[1] != blocked && !seen[nb[0]]) { seen[nb[0]] = true; line.add(nb[0]); }
                }
            }
        }
        return false;
    }
}

How long it takes: one search per hallway, O(E * (V + E)). Extra room: the hallway lists, O(V + E).

Way 2: the clever way

One walk with chalk is enough. Carry the spot you came from.

Start a walk from every spot that has no chalk yet.
At spot u, which you reached from parent, look at each neighbor v.
No chalk on v: walk there, with u as its parent.
Chalk on v and v is the parent: that is the hallway you came through. Skip it.
Chalk on v and v is not the parent: a loop. Return true.

Walk with chalk and remember where you came from

01 / 10

graph

stackcall stack

Start at 0. Nobody brought us here, so "came from" is none.

looking now
checking
rejected
path

java

class UndirectedCycleDfs {
    public static boolean hasCycle(int V, int[][] edges) {
        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]);
        }
        boolean[] chalk = new boolean[V];
        for (int i = 0; i < V; i++) {                        // every piece of the maze
            if (!chalk[i] && walk(i, -1, adj, chalk)) return true;
        }
        return false;
    }

    static boolean walk(int u, int parent, List<List<Integer>> adj, boolean[] chalk) {
        chalk[u] = true;
        for (int v : adj.get(u)) {
            if (!chalk[v]) {
                if (walk(v, u, adj, chalk)) return true;
            } else if (v != parent) {
                return true;                                 // seen, and not where we came from
            }
        }
        return false;
    }
}

How long it takes: each spot is walked into once and each hallway is looked at from both ends, O(V + E). Extra room: the chalk array and the call stack, O(V).

Another way: a waiting line

The same check works with a queue instead of recursion. Each entry in the line remembers which spot it came from.

java

class UndirectedCycleBfs {
    public static boolean hasCycle(int V, int[][] edges) {
        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]);
        }
        boolean[] chalk = new boolean[V];
        for (int s = 0; s < V; s++) {
            if (chalk[s]) continue;
            Deque<int[]> line = new ArrayDeque<>();          // {spot, came from}
            line.add(new int[]{s, -1});
            chalk[s] = true;
            while (!line.isEmpty()) {
                int[] cur = line.poll();
                int u = cur[0], parent = cur[1];
                for (int v : adj.get(u)) {
                    if (!chalk[v]) {
                        chalk[v] = true;
                        line.add(new int[]{v, u});
                    } else if (v != parent) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

Same O(V + E) time and O(V) extra room, with no risk of a too-deep call stack.

Watch out for

Starting only from spot 0. Loop over every spot, or a loop in another piece is missed.
Using the directed trick (three states) here is not needed, and using this parent trick on a directed graph is wrong.
A hallway from a spot to itself is a loop. In the DFS, v == u is chalked and is not the parent, so it returns true.

What interviewers ask next

Can you do it with union find? Yes. For each hallway, if both ends are already in the same group, that hallway closes a loop. Otherwise join the two groups. Nearly O(E).
Is there a counting shortcut? A graph with no loop is a forest, so it has exactly V - pieces hallways. If E > V - pieces, there is a loop.
Return the loop itself: keep parents, and when you find u to v, walk parents from u up to v.
Check if a graph is a valid tree: no loop and exactly one piece, which is the same as E == V - 1 and connected.

Remember this

Grown-up words: spots are vertices, hallways are undirected edges, chalk is the visited array, the spot you came from is the parent, the call stack is depth first search, the waiting line is breadth first search, and the pieces are connected components.