PK

PKBytes

Explore tracks
Chapter 33: BFS, DFS and Graph Connectivity
33.04Intermediate / Advanced4 topics17 min4 interactive animations

Cycle detection

A cycle in an undirected graph is an edge back to an already visited vertex other than the one you came from; in a directed graph it is an edge to a vertex that is still on the recursion stack.

Learning goals

  • Detect cycles in undirected graphs while handling the parent edge correctly
  • Detect directed cycles with three colours
  • Detect an undirected cycle with union-find
  • Classify every edge as tree, back, forward or cross

Prerequisites

Depth-first searchConnected componentsUnion-find

A build system with circular dependencies can never finish, and a tree must have no cycle. The two kinds of graph need different checks, because an undirected edge can be walked in both directions.

33.04.1

Undirected DFS parent

In an undirected graph DFS from u sees v, and v sees u on its adjacency list, so the edge you just came along looks like a visit to an old vertex. It is not a cycle. The fix is to skip the **edge** you arrived by, not the parent vertex. Skipping by vertex wrongly ignores *parallel edges*, which form a cycle of length 2.

Give each edge an id and pass it down the recursion. A self-loop is found at once, because the neighbour of u is u itself and it is already visited. Choose *Cycle detection with DFS and a parent edge* in the animation; the "repeated edge is a cycle" preset shows the parallel-edge case.

Java
1static boolean hasCycleByEdgeId(int n, int[][] edges) {   // undirected; parallel edges and self-loops count
2    List<List<int[]>> adj = new ArrayList<>();            // each entry: {neighbour, edge id}
3    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
4    for (int id = 0; id < edges.length; id++) {
5        adj.get(edges[id][0]).add(new int[]{edges[id][1], id});
6        adj.get(edges[id][1]).add(new int[]{edges[id][0], id});
7    }
8    boolean[] seen = new boolean[n];
9    for (int s = 0; s < n; s++)
10        if (!seen[s] && cycleFrom(adj, s, -1, seen)) return true;
11    return false;
12}
13static boolean cycleFrom(List<List<int[]>> adj, int u, int viaEdge, boolean[] seen) {
14    seen[u] = true;
15    for (int[] e : adj.get(u)) {
16        if (e[1] == viaEdge) continue;               // do not walk straight back along the same edge
17        if (seen[e[0]]) return true;                 // a different edge to a visited vertex closes a cycle
18        if (cycleFrom(adj, e[0], e[1], seen)) return true;
19    }
20    return false;
21}

Components, two-colouring and cycle detection in an undirected graph

Interactive · edit the input

Your input

Try

undirected graph · 8 vertices · 6 edges

0
1
2
3
4
5
6
7
Colour / component AColour / component BComponent CConflictBeing expanded

component of each vertex

-0
-1
-2
-3
-4
-5
-6
-7
Setup

Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.

Step 1 / 13
Java
1int[] components(List<List<Integer>> g) {        // component id per vertex
2    int n = g.size(); int[] comp = new int[n]; Arrays.fill(comp, -1);
3    int id = 0;
4    for (int s = 0; s < n; s++) {
5        if (comp[s] != -1) continue;
6        Deque<Integer> q = new ArrayDeque<>(); q.add(s); comp[s] = id;
7        while (!q.isEmpty()) {
8            int u = q.poll();
9            for (int v : g.get(u)) if (comp[v] == -1) { comp[v] = id; q.add(v); }
10        }
11        id++;                                    // the search ended: one whole component labelled
12    }
13    return comp;
14}
15boolean isBipartite(List<List<Integer>> g) {
16    int n = g.size(); int[] color = new int[n]; Arrays.fill(color, -1);
17    for (int s = 0; s < n; s++) {                // check every component
18        if (color[s] != -1) continue;
19        color[s] = 0; Deque<Integer> q = new ArrayDeque<>(); q.add(s);
20        while (!q.isEmpty()) {
21            int u = q.poll();
22            for (int v : g.get(u)) {
23                if (color[v] == -1) { color[v] = color[u] ^ 1; q.add(v); }
24                else if (color[v] == color[u]) return false;        // an odd cycle
25            }
26        }
27    }
28    return true;
29}
30boolean hasCycle(int n, List<int[]>[] g) {       // undirected; g[u] holds {v, edgeId}
31    boolean[] seen = new boolean[n];
32    for (int s = 0; s < n; s++) if (!seen[s] && dfsCycle(g, s, -1, seen)) return true;
33    return false;
34}
35boolean dfsCycle(List<int[]>[] g, int u, int viaEdge, boolean[] seen) {
36    seen[u] = true;
37    for (int[] e : g[u]) {
38        if (e[1] == viaEdge) continue;           // do not walk back along the edge we came by
39        if (seen[e[0]] || dfsCycle(g, e[0], e[1], seen)) return true;   // a seen vertex reached by another edge: a cycle
40    }
41    return false;
42}

Live state

0 components0 vertices visited

vertices

8

edges

6

No condition evaluated on this step
Execution trace (dry run table)Show 13 steps
StepLineStateWhat happens
1L2vertices=8 edges=6Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.
2L6start=0 component=0Vertex 0 is unlabelled: start component C1 here.
3L9u=0 v=1 component=00 - 1: 1 is unlabelled, so it belongs to C1 too.
4L9u=1 v=2 component=01 - 2: 2 is unlabelled, so it belongs to C1 too.
5L11components=1The queue is empty: component C1 is complete. 1 so far.
6L6start=3 component=1Vertex 3 is unlabelled: start component C2 here.
7L9u=3 v=4 component=13 - 4: 4 is unlabelled, so it belongs to C2 too.
8L11components=2The queue is empty: component C2 is complete. 2 so far.
9L6start=5 component=2Vertex 5 is unlabelled: start component C3 here.
10L9u=5 v=6 component=25 - 6: 6 is unlabelled, so it belongs to C3 too.
11L9u=5 v=7 component=25 - 7: 7 is unlabelled, so it belongs to C3 too.
12L11components=3The queue is empty: component C3 is complete. 3 so far.
13L13return=3 sizes=[3, 2, 3]3 components with sizes [3, 2, 3]. A vertex with no edge is a component of size 1. Cost O(V + E).
33.04.2

Directed three-color DFS

In a directed graph, reaching a visited vertex is not always a cycle: it may be a finished (black) vertex in a different branch. A cycle exists exactly when DFS follows an arrow to a **grey** vertex, one that is still on the recursion stack, because the stack path leads from that vertex to the current one and the arrow closes the loop.

Run the *cycle detection with three colours* option on the two presets: one finds a grey vertex and stops, and in the acyclic one every vertex turns black without a grey hit. A directed graph with no cycle is a DAG, the subject of the next chapter.

Java
1static boolean hasDirectedCycle(List<List<Integer>> g) {
2    int[] colour = new int[g.size()];                // 0 white, 1 grey (on the stack), 2 black (finished)
3    for (int s = 0; s < g.size(); s++)
4        if (colour[s] == 0 && greyHit(g, s, colour)) return true;
5    return false;
6}
7static boolean greyHit(List<List<Integer>> g, int u, int[] colour) {
8    colour[u] = 1;
9    for (int v : g.get(u)) {
10        if (colour[v] == 1) return true;             // an arrow back into the stack: a cycle
11        if (colour[v] == 0 && greyHit(g, v, colour)) return true;
12    }
13    colour[u] = 2;
14    return false;
15}

Depth-first search: times, tree, edge classes, three colours

Interactive · edit the input

Your input

Try

undirected graph · 6 vertices · 6 edges

0
1
2
3
4
5
White: undiscoveredGrey: on the stackBlack: finishedTree edgeBack edgeForward edge

stack (bottom to top)

empty

discovery / finish time

-0
-1
-2
-3
-4
-5
Setup

Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.

Step 1 / 15
Java
1int[] disc, fin; int time;
2void dfs(List<List<Integer>> g, int u) {         // recursive
3    disc[u] = ++time;                            // u turns grey
4    for (int v : g.get(u))
5        if (disc[v] == 0) dfs(g, v);             // tree edge: go deeper
6    fin[u] = ++time;                             // u turns black
7}
8void dfsIterative(List<List<Integer>> g, int s) {
9    int[] next = new int[g.size()];              // position in each vertex's neighbour list
10    Deque<Integer> stack = new ArrayDeque<>();
11    disc[s] = ++time; stack.push(s);
12    while (!stack.isEmpty()) {
13        int u = stack.peek();
14        if (next[u] < g.get(u).size()) {
15            int v = g.get(u).get(next[u]++);
16            if (disc[v] == 0) { disc[v] = ++time; stack.push(v); }
17        } else { fin[u] = ++time; stack.pop(); }
18    }
19}
20// directed graphs: classify the edge u -> v when it is examined
21String classify(int u, int v) {
22    if (disc[v] == 0) return "tree";
23    if (fin[v] == 0) return "back";              // v is still on the stack (grey): a cycle
24    return disc[u] < disc[v] ? "forward" : "cross";
25}

Live state

0 tree edges0 back edges0 forward edges0 cross edges

start

0

No condition evaluated on this step
Execution trace (dry run table)Show 15 steps
StepLineStateWhat happens
1L1start=0Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.
2L3u=0 disc[u]=1 time=1Discover 0 at time 1: it turns grey and goes on the stack (a new DFS tree starts here).
3L5u=0 v=1 disc[v]=20 - 1: 1 is white, so this is a tree edge. Discover 1 at time 2: it turns grey, and the search goes deeper.
4L5u=1 v=3 disc[v]=31 - 3: 3 is white, so this is a tree edge. Discover 3 at time 3: it turns grey, and the search goes deeper.
5L5u=3 v=2 disc[v]=43 - 2: 2 is white, so this is a tree edge. Discover 2 at time 4: it turns grey, and the search goes deeper.
6L5u=2 v=0 class=back2 - 0: 0 is grey, still on the stack: an edge to an ancestor, a back edge. It closes a cycle.
7L6v=2 fin[v]=5 time=52 has no unexplored neighbour left: it turns black at time 5 and is popped. Back to 3.
8L5u=3 v=4 disc[v]=63 - 4: 4 is white, so this is a tree edge. Discover 4 at time 6: it turns grey, and the search goes deeper.
9L5u=4 v=5 disc[v]=74 - 5: 5 is white, so this is a tree edge. Discover 5 at time 7: it turns grey, and the search goes deeper.
10L6v=5 fin[v]=8 time=85 has no unexplored neighbour left: it turns black at time 8 and is popped. Back to 4.
11L6v=4 fin[v]=9 time=94 has no unexplored neighbour left: it turns black at time 9 and is popped. Back to 3.
12L6v=3 fin[v]=10 time=103 has no unexplored neighbour left: it turns black at time 10 and is popped. Back to 1.
13L6v=1 fin[v]=11 time=111 has no unexplored neighbour left: it turns black at time 11 and is popped. Back to 0.
14L6u=0 fin[u]=12 time=120 finishes at time 12: all vertices reachable from it are black.
15L6return=[0, 1, 3, 2, 4, 5] tree edges=5 back edges=1Preorder (discovery order): [0, 1, 3, 2, 4, 5]. 5 tree edges and 1 back edge; the numbers under each vertex are discovery/finish times, and the nesting of the intervals mirrors the DFS tree.
33.04.3

DSU undirected cycle detection

Union-find gives a search-free test for undirected graphs. Process edges one at a time: if the two endpoints already have the same root, they were already connected, so this edge closes a cycle; otherwise union them. The first edge that fails is a **redundant edge**.

This also works when edges arrive as a stream, which a DFS cannot handle without rebuilding the graph. It does not apply to directed graphs, where connectivity through arrows is one-way. The animation for union-find on edges includes the redundant-edge question.

Java
1static int firstRedundantEdge(int n, int[][] edges) {   // index of the first edge that closes a cycle, or -1
2    int[] parent = new int[n];
3    for (int i = 0; i < n; i++) parent[i] = i;
4    for (int i = 0; i < edges.length; i++) {
5        int a = find(parent, edges[i][0]), b = find(parent, edges[i][1]);
6        if (a == b) return i;                        // already connected, so this edge adds a cycle
7        parent[a] = b;
8    }
9    return -1;
10}
11static int find(int[] parent, int x) {
12    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }   // path halving
13    return x;
14}

Union-find on edges: components, redundant edge, Kruskal

Interactive · edit the input

Your input

Try

disjoint-set forest (arrow = parent, roots on top) · 6 nodes

0
1
2
3
4
5
Edge kept (joins two sets)Edge skipped (same set)Edge being testedNot tested yetA root

edges in the order given

0-11
1-22
3-43
2-04
4-55
Setup

Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.

Step 1 / 7
Java
1int countComponents(int n, int[][] edges) {
2    DSU d = new DSU(n); int comps = n;
3    for (int[] e : edges) if (d.union(e[0], e[1])) comps--;       // a successful union merges two components
4    return comps;
5}
6int[] firstCycleEdge(int n, int[][] edges) {     // the first edge whose endpoints are already connected
7    DSU d = new DSU(n);
8    for (int[] e : edges) if (!d.union(e[0], e[1])) return e;
9    return null;
10}
11long kruskal(int n, int[][] edges) {             // edges are {a, b, w}
12    int[][] sorted = edges.clone();
13    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));      // stable: ties keep the input order
14    DSU d = new DSU(n); long total = 0;
15    for (int[] e : sorted) if (d.union(e[0], e[1])) total += e[2];   // keep an edge only if it joins two components
16    return total;
17}

Live state

0 edges kept0 edges skipped6 components

vertices

6

edges

5

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1vertices=6 edges=5Start with n components, one per vertex. Every edge whose endpoints are in different sets merges two components (count - 1); an edge inside one set changes nothing.
2L3edge=0-1 components=5Edge 0-1 joins the sets of roots 0 and 1: 5 components left.
3L3edge=1-2 components=4Edge 1-2 joins the sets of roots 0 and 2: 4 components left.
4L3edge=3-4 components=3Edge 3-4 joins the sets of roots 3 and 4: 3 components left.
5L3edge=2-0 root of a=0 root of b=0Edge 2-0: both ends have root 0, so they are already connected. Skip it.
6L3edge=4-5 components=2Edge 4-5 joins the sets of roots 3 and 5: 2 components left.
7L4return=22 connected components (provinces). The edges kept form a spanning forest with 4 edges.
33.04.4

Edge classification

DFS on a directed graph sorts every edge u -> v into one of four kinds by the state of v when the edge is examined. **Tree**: v is white and becomes a child of u. **Back**: v is grey, an ancestor of u. **Forward**: v is black and a descendant of u (disc[u] < disc[v]). **Cross**: v is black and in another subtree (disc[v] < disc[u]).

A directed graph has a cycle exactly when it has a back edge. In an undirected graph only tree and back edges occur. Choose *Directed: classify every edge* in the animation: the preset contains one edge of each kind.

Java
1static List<String> classifyArrows(List<List<Integer>> g) {   // "u->v tree|back|forward|cross" in the order DFS examines them
2    int n = g.size();
3    int[] colour = new int[n], disc = new int[n];
4    int[] clock = {0};
5    List<String> out = new ArrayList<>();
6    for (int s = 0; s < n; s++)
7        if (colour[s] == 0) classify(g, s, colour, disc, clock, out);
8    return out;
9}
10static void classify(List<List<Integer>> g, int u, int[] colour, int[] disc, int[] clock, List<String> out) {
11    colour[u] = 1;
12    disc[u] = clock[0]++;
13    for (int v : g.get(u)) {
14        if (colour[v] == 0) { out.add(u + "->" + v + " tree"); classify(g, v, colour, disc, clock, out); }
15        else if (colour[v] == 1) out.add(u + "->" + v + " back");                       // v is still on the stack
16        else out.add(u + "->" + v + (disc[u] < disc[v] ? " forward" : " cross"));       // v is already finished
17    }
18    colour[u] = 2;
19}

Depth-first search: times, tree, edge classes, three colours

Interactive · edit the input

Your input

Try

undirected graph · 6 vertices · 6 edges

0
1
2
3
4
5
White: undiscoveredGrey: on the stackBlack: finishedTree edgeBack edgeForward edge

stack (bottom to top)

empty

discovery / finish time

-0
-1
-2
-3
-4
-5
Setup

Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.

Step 1 / 15
Java
1int[] disc, fin; int time;
2void dfs(List<List<Integer>> g, int u) {         // recursive
3    disc[u] = ++time;                            // u turns grey
4    for (int v : g.get(u))
5        if (disc[v] == 0) dfs(g, v);             // tree edge: go deeper
6    fin[u] = ++time;                             // u turns black
7}
8void dfsIterative(List<List<Integer>> g, int s) {
9    int[] next = new int[g.size()];              // position in each vertex's neighbour list
10    Deque<Integer> stack = new ArrayDeque<>();
11    disc[s] = ++time; stack.push(s);
12    while (!stack.isEmpty()) {
13        int u = stack.peek();
14        if (next[u] < g.get(u).size()) {
15            int v = g.get(u).get(next[u]++);
16            if (disc[v] == 0) { disc[v] = ++time; stack.push(v); }
17        } else { fin[u] = ++time; stack.pop(); }
18    }
19}
20// directed graphs: classify the edge u -> v when it is examined
21String classify(int u, int v) {
22    if (disc[v] == 0) return "tree";
23    if (fin[v] == 0) return "back";              // v is still on the stack (grey): a cycle
24    return disc[u] < disc[v] ? "forward" : "cross";
25}

Live state

0 tree edges0 back edges0 forward edges0 cross edges

start

0

No condition evaluated on this step
Execution trace (dry run table)Show 15 steps
StepLineStateWhat happens
1L1start=0Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.
2L3u=0 disc[u]=1 time=1Discover 0 at time 1: it turns grey and goes on the stack (a new DFS tree starts here).
3L5u=0 v=1 disc[v]=20 - 1: 1 is white, so this is a tree edge. Discover 1 at time 2: it turns grey, and the search goes deeper.
4L5u=1 v=3 disc[v]=31 - 3: 3 is white, so this is a tree edge. Discover 3 at time 3: it turns grey, and the search goes deeper.
5L5u=3 v=2 disc[v]=43 - 2: 2 is white, so this is a tree edge. Discover 2 at time 4: it turns grey, and the search goes deeper.
6L5u=2 v=0 class=back2 - 0: 0 is grey, still on the stack: an edge to an ancestor, a back edge. It closes a cycle.
7L6v=2 fin[v]=5 time=52 has no unexplored neighbour left: it turns black at time 5 and is popped. Back to 3.
8L5u=3 v=4 disc[v]=63 - 4: 4 is white, so this is a tree edge. Discover 4 at time 6: it turns grey, and the search goes deeper.
9L5u=4 v=5 disc[v]=74 - 5: 5 is white, so this is a tree edge. Discover 5 at time 7: it turns grey, and the search goes deeper.
10L6v=5 fin[v]=8 time=85 has no unexplored neighbour left: it turns black at time 8 and is popped. Back to 4.
11L6v=4 fin[v]=9 time=94 has no unexplored neighbour left: it turns black at time 9 and is popped. Back to 3.
12L6v=3 fin[v]=10 time=103 has no unexplored neighbour left: it turns black at time 10 and is popped. Back to 1.
13L6v=1 fin[v]=11 time=111 has no unexplored neighbour left: it turns black at time 11 and is popped. Back to 0.
14L6u=0 fin[u]=12 time=120 finishes at time 12: all vertices reachable from it are black.
15L6return=[0, 1, 3, 2, 4, 5] tree edges=5 back edges=1Preorder (discovery order): [0, 1, 3, 2, 4, 5]. 5 tree edges and 1 back edge; the numbers under each vertex are discovery/finish times, and the nesting of the intervals mirrors the DFS tree.

Practice ladder

Now try it yourself

Easy

  • Find if Path Exists in Graph

Medium

  • Course Schedule
  • Redundant Connection
  • Graph Valid Tree
  • Find Eventual Safe States

Advanced

  • Redundant Connection II
  • Course Schedule II

Key takeaways

  • Undirected: an edge to a visited vertex, other than the edge you arrived by, is a cycle; skip by edge id so parallel edges count.
  • Directed: a cycle exists exactly when DFS meets a grey vertex (a back edge).
  • Union-find finds the first edge that closes a cycle in an undirected graph, even when edges stream in.
  • DFS sorts directed edges into tree, back, forward and cross edges.