32.01Intermediate / Advanced10 topics17 min10 interactive animations

Graph vocabulary

The words used to talk about graphs: vertices, edges, degree, paths, walks, trails, cycles, components and connectedness, each with a precise meaning.

Learning goals

Name the parts of a graph and count degrees, including in-degree and out-degree
Tell walks, trails, paths and cycles apart by what may repeat
Explain components and connectedness for undirected and directed graphs
Turn each definition into a small Java check

Prerequisites

ArraysSets and mapsTrees (basic vocabulary)

A road map, a friendship network and a build-dependency list look nothing alike, yet all are graphs: things and the connections between them. Precise words let you say exactly what a problem asks: a path, not just a walk; connected, not just reachable.

32.01.1

Vertices

A graph is a pair G = (V, E): a set V of **vertices** (also called nodes) and a set E of **edges** joining them. Vertices stand for the things: cities, people, tasks, board positions. In code they are almost always the integers 0 to n - 1, because an integer indexes an array. When the real things have names, translate each name to an integer once, at the boundary, and keep the table to translate back.

Open the animation and add the preset's edges one at a time: the graph has 5 vertices before any edge exists, and a vertex with no edge is still a vertex (it is an *isolated* vertex). The number of vertices is written n or |V|.

Java

1class VertexIds {                                // map arbitrary names to the integers 0..n-1
2    private final Map<String, Integer> id = new HashMap<>();
3    private final List<String> names = new ArrayList<>();
4    int idOf(String name) {                      // the first time a name is seen it gets the next number
5        return id.computeIfAbsent(name, k -> { names.add(k); return names.size() - 1; });
6    }
7    String nameOf(int v) { return names.get(v); }
8    int count() { return names.size(); }
9}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.01.2

Edges

An **edge** joins two vertices. In an *undirected* graph the edge {a, b} has no direction: it is the same as {b, a}. In a *directed* graph the edge (a, b) is an arrow from a to b, different from (b, a). A weighted edge also carries a number such as a distance or cost. The number of edges is written m or |E|.

Store an undirected edge once and read it in both directions, or store it twice as two arrows; the representations lesson shows how each structure handles this. A record is a convenient way to carry an edge in Java, with a helper that flips it.

Java

1record Edge(int from, int to, int weight) {      // a directed edge; an undirected edge is read both ways
2    Edge reversed() { return new Edge(to, from, weight); }
3    boolean isSelfLoop() { return from == to; }
4}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.01.3

Degree

The **degree** of a vertex is the number of edge ends that touch it. A self-loop has both ends at the same vertex, so it adds 2. In the preset "Undirected, five edges" (0-1 0-2 1-3 2-3 3-4) the degrees are [2, 2, 2, 3, 1]: vertex 3 is touched by three edges and vertex 4 by one. Summing a row of the adjacency matrix gives the degree, which is why the animation's matrix counts the two ends of a loop on the diagonal.

A vertex of degree 0 is isolated and a vertex of degree 1 is a *leaf*. The degrees of all vertices always add up to twice the number of edges (the handshaking lemma, below). Computing them takes one pass over the edge list.

Java

1static int[] degrees(int n, int[][] edges) {     // undirected; a self-loop a-a adds 2 to a
2    int[] deg = new int[n];
3    for (int[] e : edges) { deg[e[0]]++; deg[e[1]]++; }
4    return deg;
5}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.01.4

In-degree/out-degree

In a directed graph each vertex has an **out-degree**, the number of arrows leaving it, and an **in-degree**, the number of arrows entering it. A vertex with in-degree 0 is a *source* and one with out-degree 0 is a *sink*. Every arrow leaves one vertex and enters one vertex, so the out-degrees add up to m and so do the in-degrees.

Switch the animation to "Directed: rows are out-edges": the matrix rows now sum to the out-degrees [2, 1, 1, 1, 0] and the columns to the in-degrees [0, 1, 1, 2, 1]. Both add up to 5, the number of arrows. Vertex 0 is a source (nothing enters it) and vertex 4 is a sink. In-degrees drive topological sorting in the next chapter.

Java

1static int[][] inOutDegrees(int n, int[][] edges) {      // returns {in, out}
2    int[] in = new int[n], out = new int[n];
3    for (int[] e : edges) { out[e[0]]++; in[e[1]]++; }
4    return new int[][]{in, out};
5}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.01.5

Paths

A **path** is a sequence of vertices in which each consecutive pair is joined by an edge and **no vertex repeats**. Its length is the number of edges. Paths are what shortest-path algorithms look for. A single vertex is a path of length 0.

The preset "A path" in the animation checks 0 → 1 → 2 → 3 → 4: every step uses an existing edge, no vertex appears twice, and the verdict is 'path'. Repeating a vertex would turn it into a trail or a walk, as the next items show.

Java

1static boolean isPath(boolean[][] adj, int[] seq) {      // simple graph; seq lists the vertices in order
2    Set<Integer> seen = new HashSet<>();
3    for (int i = 0; i < seq.length; i++) {
4        if (!seen.add(seq[i])) return false;              // a vertex repeats
5        if (i > 0 && !adj[seq[i - 1]][seq[i]]) return false;     // consecutive vertices must be adjacent
6    }
7    return true;
8}

Walk, trail, path, closed walk, cycle: classify a vertex sequence

Interactive · edit the input

undirected graph · 5 vertices · 6 edges

#1,5

Edge used for the first timeNo such edgeCurrent vertexEdge used again

sequence

Setup

The sequence 0 → 1 → 2 → 3 → 0 has 4 steps. Check each step against the edges, then see which vertices and edges repeat.

Step 1 / 6

Java

1String classify(boolean[][] adj, int[] seq) {    // simple undirected graph; seq lists the vertices in order
2    Set<Integer> vertices = new HashSet<>(); Set<Long> edges = new HashSet<>();
3    boolean repeatedVertex = false, repeatedEdge = false;
4    vertices.add(seq[0]);
5    for (int i = 1; i < seq.length; i++) {
6        int a = seq[i - 1], b = seq[i];
7        if (!adj[a][b]) return "not a walk";     // consecutive vertices must be joined by an edge
8        long id = (long) Math.min(a, b) * 1000 + Math.max(a, b);
9        if (!edges.add(id)) repeatedEdge = true; // the same edge used twice
10        if (!vertices.add(b) && !(i == seq.length - 1 && b == seq[0])) repeatedVertex = true;
11    }
12    boolean closed = seq.length > 1 && seq[0] == seq[seq.length - 1];
13    if (closed && !repeatedVertex && !repeatedEdge && seq.length - 1 >= 3) return "cycle";
14    if (closed && !repeatedEdge) return "closed trail";
15    if (closed) return "closed walk";
16    if (!repeatedVertex) return "path";
17    return repeatedEdge ? "walk" : "trail";
18}

Live state

0 steps

sequence

0 → 1 → 2 → 3 → 0

length

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L4	sequence=0 → 1 → 2 → 3 → 0 length=4	The sequence 0 → 1 → 2 → 3 → 0 has 4 steps. Check each step against the edges, then see which vertices and edges repeat.
2	L10	step=0 → 1 edge used again=false vertex seen before=false	Step 1: 0 → 1 uses the edge 0-1. 1 is new.
3	L10	step=1 → 2 edge used again=false vertex seen before=false	Step 2: 1 → 2 uses the edge 1-2. 2 is new.
4	L10	step=2 → 3 edge used again=false vertex seen before=false	Step 3: 2 → 3 uses the edge 2-3. 3 is new.
5	L10	step=3 → 0 edge used again=false vertex seen before=true	Step 4: 3 → 0 uses the edge 3-0. 0 is the start vertex, so the walk closes.
6	L17	return=cycle	0 → 1 → 2 → 3 → 0 is a cycle. It returns to its start and nothing else repeats.

32.01.6

Walks

A **walk** is the loosest of the four: consecutive vertices must be joined by an edge, but vertices and edges may repeat as often as you like. Every path, trail and cycle is also a walk. Counting walks of a given length is a classic use of the adjacency matrix: the entry (i, j) of A^k counts the walks of length k from i to j.

In the preset "A walk that repeats an edge" (0 → 1 → 2 → 1 → 3) the animation notices that the edge 1-2 is used twice and that vertex 1 repeats: it is a walk and nothing stricter. The preset "Not a walk: a missing edge" fails at the first step because 0-2 is not an edge.

Java

1static boolean isWalk(boolean[][] adj, int[] seq) {      // every consecutive pair must be an edge
2    for (int i = 1; i < seq.length; i++)
3        if (!adj[seq[i - 1]][seq[i]]) return false;
4    return true;
5}

Walk, trail, path, closed walk, cycle: classify a vertex sequence

Interactive · edit the input

undirected graph · 5 vertices · 6 edges

#1,5

Edge used for the first timeNo such edgeCurrent vertexEdge used again

sequence

Setup

The sequence 0 → 1 → 2 → 3 → 0 has 4 steps. Check each step against the edges, then see which vertices and edges repeat.

Step 1 / 6

Java

1String classify(boolean[][] adj, int[] seq) {    // simple undirected graph; seq lists the vertices in order
2    Set<Integer> vertices = new HashSet<>(); Set<Long> edges = new HashSet<>();
3    boolean repeatedVertex = false, repeatedEdge = false;
4    vertices.add(seq[0]);
5    for (int i = 1; i < seq.length; i++) {
6        int a = seq[i - 1], b = seq[i];
7        if (!adj[a][b]) return "not a walk";     // consecutive vertices must be joined by an edge
8        long id = (long) Math.min(a, b) * 1000 + Math.max(a, b);
9        if (!edges.add(id)) repeatedEdge = true; // the same edge used twice
10        if (!vertices.add(b) && !(i == seq.length - 1 && b == seq[0])) repeatedVertex = true;
11    }
12    boolean closed = seq.length > 1 && seq[0] == seq[seq.length - 1];
13    if (closed && !repeatedVertex && !repeatedEdge && seq.length - 1 >= 3) return "cycle";
14    if (closed && !repeatedEdge) return "closed trail";
15    if (closed) return "closed walk";
16    if (!repeatedVertex) return "path";
17    return repeatedEdge ? "walk" : "trail";
18}

Live state

0 steps

sequence

0 → 1 → 2 → 3 → 0

length

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L4	sequence=0 → 1 → 2 → 3 → 0 length=4	The sequence 0 → 1 → 2 → 3 → 0 has 4 steps. Check each step against the edges, then see which vertices and edges repeat.
2	L10	step=0 → 1 edge used again=false vertex seen before=false	Step 1: 0 → 1 uses the edge 0-1. 1 is new.
3	L10	step=1 → 2 edge used again=false vertex seen before=false	Step 2: 1 → 2 uses the edge 1-2. 2 is new.
4	L10	step=2 → 3 edge used again=false vertex seen before=false	Step 3: 2 → 3 uses the edge 2-3. 3 is new.
5	L10	step=3 → 0 edge used again=false vertex seen before=true	Step 4: 3 → 0 uses the edge 3-0. 0 is the start vertex, so the walk closes.
6	L17	return=cycle	0 → 1 → 2 → 3 → 0 is a cycle. It returns to its start and nothing else repeats.

32.01.7

Trails

A **trail** is a walk in which **no edge repeats**, although vertices may. Euler's famous question, whether a route can use every edge exactly once, asks for a trail through all edges. A closed trail is called a circuit.

In "A trail that is not a path" the sequence 0 → 1 → 3 → 2 → 1 uses the four different edges 0-1, 1-3, 3-2 and 2-1, so it is a trail, but vertex 1 appears twice, so it is not a path. To check, collect the edges in a set keyed by their two ends in a fixed order, since in an undirected graph a-b and b-a are the same edge.

Java

1static boolean isTrail(boolean[][] adj, int[] seq) {     // a walk that never reuses an edge
2    Set<Long> used = new HashSet<>();
3    for (int i = 1; i < seq.length; i++) {
4        int a = seq[i - 1], b = seq[i];
5        if (!adj[a][b]) return false;
6        long id = (long) Math.min(a, b) * 1000 + Math.max(a, b);       // the same edge in both directions
7        if (!used.add(id)) return false;
8    }
9    return true;
10}

Walk, trail, path, closed walk, cycle: classify a vertex sequence

Interactive · edit the input

undirected graph · 5 vertices · 6 edges

#1,5

Edge used for the first timeNo such edgeCurrent vertexEdge used again

sequence

Setup

The sequence 0 → 1 → 2 → 3 → 0 has 4 steps. Check each step against the edges, then see which vertices and edges repeat.

Step 1 / 6

Java

1String classify(boolean[][] adj, int[] seq) {    // simple undirected graph; seq lists the vertices in order
2    Set<Integer> vertices = new HashSet<>(); Set<Long> edges = new HashSet<>();
3    boolean repeatedVertex = false, repeatedEdge = false;
4    vertices.add(seq[0]);
5    for (int i = 1; i < seq.length; i++) {
6        int a = seq[i - 1], b = seq[i];
7        if (!adj[a][b]) return "not a walk";     // consecutive vertices must be joined by an edge
8        long id = (long) Math.min(a, b) * 1000 + Math.max(a, b);
9        if (!edges.add(id)) repeatedEdge = true; // the same edge used twice
10        if (!vertices.add(b) && !(i == seq.length - 1 && b == seq[0])) repeatedVertex = true;
11    }
12    boolean closed = seq.length > 1 && seq[0] == seq[seq.length - 1];
13    if (closed && !repeatedVertex && !repeatedEdge && seq.length - 1 >= 3) return "cycle";
14    if (closed && !repeatedEdge) return "closed trail";
15    if (closed) return "closed walk";
16    if (!repeatedVertex) return "path";
17    return repeatedEdge ? "walk" : "trail";
18}

Live state

0 steps

sequence

0 → 1 → 2 → 3 → 0

length

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L4	sequence=0 → 1 → 2 → 3 → 0 length=4	The sequence 0 → 1 → 2 → 3 → 0 has 4 steps. Check each step against the edges, then see which vertices and edges repeat.
2	L10	step=0 → 1 edge used again=false vertex seen before=false	Step 1: 0 → 1 uses the edge 0-1. 1 is new.
3	L10	step=1 → 2 edge used again=false vertex seen before=false	Step 2: 1 → 2 uses the edge 1-2. 2 is new.
4	L10	step=2 → 3 edge used again=false vertex seen before=false	Step 3: 2 → 3 uses the edge 2-3. 3 is new.
5	L10	step=3 → 0 edge used again=false vertex seen before=true	Step 4: 3 → 0 uses the edge 3-0. 0 is the start vertex, so the walk closes.
6	L17	return=cycle	0 → 1 → 2 → 3 → 0 is a cycle. It returns to its start and nothing else repeats.

32.01.8

Cycles

A **cycle** is a closed path: it starts and ends at the same vertex, the edges are all different, and no other vertex repeats; in a simple graph it has at least 3 edges. A graph with no cycle is *acyclic*; an undirected acyclic graph is a forest. Cycle detection comes up in dependency checking, deadlock detection and spanning trees.

The preset "A cycle" accepts 0 → 1 → 2 → 3 → 0. The classification is a ladder: not a walk, walk, trail, path, closed walk, closed trail, cycle, from loosest to strictest. The code below returns the strictest label that fits.

Term	Vertices may repeat	Edges may repeat	Closed?
walk	yes	yes	optional
trail	yes	no	optional
path	no	no	no
closed walk / circuit	yes	yes / no	yes
cycle	only the start = end	no	yes

Java

1static String classify(boolean[][] adj, int[] seq) {     // simple undirected graph; seq lists the vertices in order
2    Set<Integer> vertices = new HashSet<>();
3    Set<Long> edges = new HashSet<>();
4    boolean repeatedVertex = false, repeatedEdge = false;
5    vertices.add(seq[0]);
6    for (int i = 1; i < seq.length; i++) {
7        int a = seq[i - 1], b = seq[i];
8        if (!adj[a][b]) return "not a walk";
9        long id = (long) Math.min(a, b) * 1000 + Math.max(a, b);
10        if (!edges.add(id)) repeatedEdge = true;
11        if (!vertices.add(b) && !(i == seq.length - 1 && b == seq[0])) repeatedVertex = true;
12    }
13    boolean closed = seq.length > 1 && seq[0] == seq[seq.length - 1];
14    if (closed && !repeatedVertex && !repeatedEdge && seq.length - 1 >= 3) return "cycle";
15    if (closed && !repeatedEdge) return "closed trail";
16    if (closed) return "closed walk";
17    if (!repeatedVertex) return "path";
18    return repeatedEdge ? "walk" : "trail";
19}

Walk, trail, path, closed walk, cycle: classify a vertex sequence

Interactive · edit the input

undirected graph · 5 vertices · 6 edges

#1,5

Edge used for the first timeNo such edgeCurrent vertexEdge used again

sequence

Setup

The sequence 0 → 1 → 2 → 3 → 0 has 4 steps. Check each step against the edges, then see which vertices and edges repeat.

Step 1 / 6

Java

1String classify(boolean[][] adj, int[] seq) {    // simple undirected graph; seq lists the vertices in order
2    Set<Integer> vertices = new HashSet<>(); Set<Long> edges = new HashSet<>();
3    boolean repeatedVertex = false, repeatedEdge = false;
4    vertices.add(seq[0]);
5    for (int i = 1; i < seq.length; i++) {
6        int a = seq[i - 1], b = seq[i];
7        if (!adj[a][b]) return "not a walk";     // consecutive vertices must be joined by an edge
8        long id = (long) Math.min(a, b) * 1000 + Math.max(a, b);
9        if (!edges.add(id)) repeatedEdge = true; // the same edge used twice
10        if (!vertices.add(b) && !(i == seq.length - 1 && b == seq[0])) repeatedVertex = true;
11    }
12    boolean closed = seq.length > 1 && seq[0] == seq[seq.length - 1];
13    if (closed && !repeatedVertex && !repeatedEdge && seq.length - 1 >= 3) return "cycle";
14    if (closed && !repeatedEdge) return "closed trail";
15    if (closed) return "closed walk";
16    if (!repeatedVertex) return "path";
17    return repeatedEdge ? "walk" : "trail";
18}

Live state

0 steps

sequence

0 → 1 → 2 → 3 → 0

length

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L4	sequence=0 → 1 → 2 → 3 → 0 length=4	The sequence 0 → 1 → 2 → 3 → 0 has 4 steps. Check each step against the edges, then see which vertices and edges repeat.
2	L10	step=0 → 1 edge used again=false vertex seen before=false	Step 1: 0 → 1 uses the edge 0-1. 1 is new.
3	L10	step=1 → 2 edge used again=false vertex seen before=false	Step 2: 1 → 2 uses the edge 1-2. 2 is new.
4	L10	step=2 → 3 edge used again=false vertex seen before=false	Step 3: 2 → 3 uses the edge 2-3. 3 is new.
5	L10	step=3 → 0 edge used again=false vertex seen before=true	Step 4: 3 → 0 uses the edge 3-0. 0 is the start vertex, so the walk closes.
6	L17	return=cycle	0 → 1 → 2 → 3 → 0 is a cycle. It returns to its start and nothing else repeats.

32.01.9

Components

A **connected component** of an undirected graph is a maximal set of vertices in which any two are joined by a path. Every vertex lies in exactly one component; a vertex with no edges is a component of size 1. Components partition the graph, and most algorithms must run once per component to cover everything.

In the preset "Three components" the edges 0-1 1-2 3-4 5-6 6-7 7-5 split 8 vertices into three components of sizes 3, 2 and 3. Finding them takes one search per unlabelled vertex, O(V + E) in total, or a union-find.

Java

1static int countComponents(int n, int[][] edges) {
2    List<List<Integer>> g = new ArrayList<>();
3    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
4    for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
5    boolean[] seen = new boolean[n];
6    int count = 0;
7    for (int s = 0; s < n; s++) {
8        if (seen[s]) continue;
9        count++;                                 // a new, unvisited component starts here
10        Deque<Integer> stack = new ArrayDeque<>();
11        stack.push(s); seen[s] = true;
12        while (!stack.isEmpty()) {
13            int u = stack.pop();
14            for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; stack.push(v); }
15        }
16    }
17    return count;
18}

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

Interactive · edit the input

undirected graph · 8 vertices · 6 edges

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

edges

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	vertices=8 edges=6	Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.
2	L6	start=0 component=0	Vertex 0 is unlabelled: start component C1 here.
3	L9	u=0 v=1 component=0	0 - 1: 1 is unlabelled, so it belongs to C1 too.
4	L9	u=1 v=2 component=0	1 - 2: 2 is unlabelled, so it belongs to C1 too.
5	L11	components=1	The queue is empty: component C1 is complete. 1 so far.
6	L6	start=3 component=1	Vertex 3 is unlabelled: start component C2 here.
7	L9	u=3 v=4 component=1	3 - 4: 4 is unlabelled, so it belongs to C2 too.
8	L11	components=2	The queue is empty: component C2 is complete. 2 so far.
9	L6	start=5 component=2	Vertex 5 is unlabelled: start component C3 here.
10	L9	u=5 v=6 component=2	5 - 6: 6 is unlabelled, so it belongs to C3 too.
11	L9	u=5 v=7 component=2	5 - 7: 7 is unlabelled, so it belongs to C3 too.
12	L11	components=3	The queue is empty: component C3 is complete. 3 so far.
13	L13	return=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).

32.01.10

Connectedness

An undirected graph is **connected** when it has exactly one component: a path exists between every pair of vertices. A directed graph needs two notions. It is **weakly connected** if it is connected after ignoring the direction of arrows, and **strongly connected** if every vertex can reach every other following the arrows. Strong connectivity is stronger: a directed path 0 → 1 → 2 is weakly connected but not strongly.

To test strong connectivity, run one search from vertex 0 along the arrows and another along the reversed arrows: the graph is strongly connected exactly when both reach every vertex (every vertex is reachable from 0, and 0 is reachable from every vertex). Chapter 38 finds the strongly connected components themselves.

Java

1static boolean isConnected(int n, int[][] edges) {       // undirected
2    int[] parent = new int[n];
3    for (int i = 0; i < n; i++) parent[i] = i;
4    int comps = n;
5    for (int[] e : edges) {
6        int a = e[0], b = e[1];
7        while (parent[a] != a) a = parent[a];
8        while (parent[b] != b) b = parent[b];
9        if (a != b) { parent[a] = b; comps--; }
10    }
11    return comps == 1;
12}
13static boolean isStronglyConnected(int n, int[][] arrows) {       // directed
14    return reachesAll(n, arrows, false) && reachesAll(n, arrows, true);
15}
16private static boolean reachesAll(int n, int[][] arrows, boolean reversed) {     // from vertex 0
17    List<List<Integer>> g = new ArrayList<>();
18    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
19    for (int[] e : arrows) { if (reversed) g.get(e[1]).add(e[0]); else g.get(e[0]).add(e[1]); }
20    boolean[] seen = new boolean[n];
21    Deque<Integer> q = new ArrayDeque<>();
22    q.add(0); seen[0] = true; int count = 1;
23    while (!q.isEmpty()) {
24        int u = q.poll();
25        for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; count++; q.add(v); }
26    }
27    return count == n;
28}

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

Interactive · edit the input

undirected graph · 8 vertices · 6 edges

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

edges

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	vertices=8 edges=6	Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.
2	L6	start=0 component=0	Vertex 0 is unlabelled: start component C1 here.
3	L9	u=0 v=1 component=0	0 - 1: 1 is unlabelled, so it belongs to C1 too.
4	L9	u=1 v=2 component=0	1 - 2: 2 is unlabelled, so it belongs to C1 too.
5	L11	components=1	The queue is empty: component C1 is complete. 1 so far.
6	L6	start=3 component=1	Vertex 3 is unlabelled: start component C2 here.
7	L9	u=3 v=4 component=1	3 - 4: 4 is unlabelled, so it belongs to C2 too.
8	L11	components=2	The queue is empty: component C2 is complete. 2 so far.
9	L6	start=5 component=2	Vertex 5 is unlabelled: start component C3 here.
10	L9	u=5 v=6 component=2	5 - 6: 6 is unlabelled, so it belongs to C3 too.
11	L9	u=5 v=7 component=2	5 - 7: 7 is unlabelled, so it belongs to C3 too.
12	L11	components=3	The queue is empty: component C3 is complete. 3 so far.
13	L13	return=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).

Practice ladder

Now try it yourself

Easy

Find the Town Judge
Find Center of Star Graph

Medium

Find if Path Exists in Graph
Number of Connected Components in an Undirected Graph

Advanced

Reconstruct Itinerary
Minimum Number of Vertices to Reach All Nodes

Key takeaways

A graph is vertices plus edges; label the vertices 0 to n - 1 in code.
Degree counts edge ends (a self-loop counts twice); directed graphs split it into in-degree and out-degree.
Walk ⊇ trail ⊇ path, and a cycle is a closed path; components partition the vertices.