32.02Intermediate / Advanced8 topics16 min8 interactive animations

Graph taxonomy

The standard kinds of graph and how to recognise them: directed or undirected, weighted, simple or multi, DAG, tree, bipartite, complete, sparse or dense.

Learning goals

Recognise each kind of graph from its edges
Test the properties that decide which algorithm applies
Implement the tests for simple, tree, DAG, bipartite and complete graphs
Judge density with the edge count against the possible edges

Prerequisites

Graph vocabulary

Choosing an algorithm often starts with a question about the graph: can there be cycles? negative weights? is it a tree? Naming the kind of graph tells you what is allowed and which faster algorithms are available.

32.02.1

Directed/undirected

In an **undirected** graph an edge works both ways; in a **directed** graph (digraph) an edge is an arrow and the two directions are independent. Roads with two-way streets are undirected, web links and follows are directed. An undirected graph is the same as a directed graph in which every arrow has a partner pointing back, so its adjacency matrix is symmetric.

The animation of the classifier takes the same edges either way: choose 'Directed' for 0-1 0-2 1-3 2-3 3-4 and the verdicts include DAG; choose 'Undirected' for the same list and they include tree-related properties instead. Many properties only make sense for one kind: a DAG is directed, a tree is undirected.

Java

1static boolean isSymmetric(int[][] adj) {        // an undirected graph has a symmetric adjacency matrix
2    for (int i = 0; i < adj.length; i++)
3        for (int j = i + 1; j < adj.length; j++)
4            if (adj[i][j] != adj[j][i]) return false;
5    return true;
6}

Classify a graph: simple, connected, tree, DAG, bipartite, complete, dense

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

Property holdsProperty failsBeing checked

verdicts

none yet

Setup

Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.

Step 1 / 10

Java

1boolean isSimple(int n, int[][] edges, boolean directed) {         // no self-loops, no repeated edges
2    Set<Long> seen = new HashSet<>();
3    for (int[] e : edges) {
4        if (e[0] == e[1]) return false;
5        int a = directed ? e[0] : Math.min(e[0], e[1]), b = directed ? e[1] : Math.max(e[0], e[1]);
6        if (!seen.add((long) a * n + b)) return false;
7    }
8    return true;
9}
10boolean isTree(int n, int[][] edges) {           // undirected: n - 1 edges and connected
11    return edges.length == n - 1 && components(n, edges) == 1;
12}
13boolean isDag(int n, int[][] edges) {            // directed: Kahn's algorithm removes every vertex
14    int[] indeg = new int[n]; List<List<Integer>> g = new ArrayList<>();
15    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
16    for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }
17    Deque<Integer> q = new ArrayDeque<>();
18    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
19    int removed = 0;
20    while (!q.isEmpty()) { int u = q.poll(); removed++; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); }
21    return removed == n;
22}
23boolean isComplete(int n, int[][] edges) {       // simple undirected graph with every pair joined
24    return isSimple(n, edges, false) && edges.length == n * (n - 1) / 2;
25}
26double density(int n, int m, boolean directed) { // fraction of the possible edges that are present
27    long possible = directed ? (long) n * (n - 1) : (long) n * (n - 1) / 2;
28    return possible == 0 ? 0 : (double) m / possible;
29}

Live state

0 checks

vertices

edges

kind

undirected

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L1	vertices=5 edges=4 kind=undirected	Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.
2	L1	property=weighted verdict=false	weighted: no. No edge carries a weight: every edge counts the same.
3	L1	property=simple verdict=true	simple: yes. No self-loops and no repeated edges.
4	L1	property=connected verdict=true	connected: yes. One component.
5	L11	property=tree verdict=true	tree: yes. Connected with 5 - 1 = 4 edges.
6	L21	property=DAG verdict=not applicable	DAG: not applicable. A DAG is a directed graph; an undirected edge is a two-way edge.
7	L1	property=bipartite verdict=true	bipartite: yes. The vertices split into two groups with every edge between the groups (checked on the underlying undirected graph).
8	L24	property=complete verdict=false	complete: no. 4 of the 10 possible edges are present.
9	L28	property=sparse verdict=true	sparse: yes. 4 of 10 possible edges = 40%. (This course calls a graph dense from 50% and sparse below; real programs think in terms of E against V and V².)
10	L28	return=simple, connected, tree, bipartite, sparse	Verdicts: simple, connected, tree, bipartite, sparse.

32.02.2

Weighted/unweighted

In a **weighted** graph each edge has a number: distance, time, cost, capacity. In an unweighted graph every edge counts the same, and a shortest path means the fewest edges, which breadth-first search finds. With weights, 'shortest' means smallest total weight and needs Dijkstra or Bellman-Ford (Chapter 35).

Check the weights before choosing an algorithm. Negative weights break Dijkstra, and zero weights allow special tricks. The classifier marks a graph weighted when any edge carries a weight; try the "Multigraph with a self-loop" preset, where 1-2:5 makes the verdict list include 'weighted'.

Java

1static boolean hasNegativeWeight(int[][] edges) {        // edges are {a, b, w}
2    for (int[] e : edges) if (e[2] < 0) return true;
3    return false;
4}
5static long totalWeight(int[][] edges) {
6    long total = 0;
7    for (int[] e : edges) total += e[2];         // long: many large weights can overflow int
8    return total;
9}

Classify a graph: simple, connected, tree, DAG, bipartite, complete, dense

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

Property holdsProperty failsBeing checked

verdicts

none yet

Setup

Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.

Step 1 / 10

Java

1boolean isSimple(int n, int[][] edges, boolean directed) {         // no self-loops, no repeated edges
2    Set<Long> seen = new HashSet<>();
3    for (int[] e : edges) {
4        if (e[0] == e[1]) return false;
5        int a = directed ? e[0] : Math.min(e[0], e[1]), b = directed ? e[1] : Math.max(e[0], e[1]);
6        if (!seen.add((long) a * n + b)) return false;
7    }
8    return true;
9}
10boolean isTree(int n, int[][] edges) {           // undirected: n - 1 edges and connected
11    return edges.length == n - 1 && components(n, edges) == 1;
12}
13boolean isDag(int n, int[][] edges) {            // directed: Kahn's algorithm removes every vertex
14    int[] indeg = new int[n]; List<List<Integer>> g = new ArrayList<>();
15    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
16    for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }
17    Deque<Integer> q = new ArrayDeque<>();
18    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
19    int removed = 0;
20    while (!q.isEmpty()) { int u = q.poll(); removed++; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); }
21    return removed == n;
22}
23boolean isComplete(int n, int[][] edges) {       // simple undirected graph with every pair joined
24    return isSimple(n, edges, false) && edges.length == n * (n - 1) / 2;
25}
26double density(int n, int m, boolean directed) { // fraction of the possible edges that are present
27    long possible = directed ? (long) n * (n - 1) : (long) n * (n - 1) / 2;
28    return possible == 0 ? 0 : (double) m / possible;
29}

Live state

0 checks

vertices

edges

kind

undirected

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L1	vertices=5 edges=4 kind=undirected	Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.
2	L1	property=weighted verdict=false	weighted: no. No edge carries a weight: every edge counts the same.
3	L1	property=simple verdict=true	simple: yes. No self-loops and no repeated edges.
4	L1	property=connected verdict=true	connected: yes. One component.
5	L11	property=tree verdict=true	tree: yes. Connected with 5 - 1 = 4 edges.
6	L21	property=DAG verdict=not applicable	DAG: not applicable. A DAG is a directed graph; an undirected edge is a two-way edge.
7	L1	property=bipartite verdict=true	bipartite: yes. The vertices split into two groups with every edge between the groups (checked on the underlying undirected graph).
8	L24	property=complete verdict=false	complete: no. 4 of the 10 possible edges are present.
9	L28	property=sparse verdict=true	sparse: yes. 4 of 10 possible edges = 40%. (This course calls a graph dense from 50% and sparse below; real programs think in terms of E against V and V².)
10	L28	return=simple, connected, tree, bipartite, sparse	Verdicts: simple, connected, tree, bipartite, sparse.

32.02.3

Simple/multigraph

A **simple graph** has no self-loops and no repeated edges between the same pair. A **multigraph** allows parallel edges, and a graph with loops allows an edge from a vertex to itself. Many theorems assume simple graphs: for example a simple undirected graph has at most n(n-1)/2 edges. Real data is often not simple, so decide up front whether to keep, merge or drop the extra edges.

In the preset "Multigraph with a self-loop" (0-1 0-1 1-1 1-2:5) the classifier reports two problems: a repeated edge and a self-loop, so 'simple' is missing from the verdicts. To test, normalise each edge to an ordered pair for undirected graphs and look for loops and repeats.

Java

1static boolean isSimple(int n, int[][] edges, boolean directed) {         // no self-loops, no repeated edges
2    Set<Long> seen = new HashSet<>();
3    for (int[] e : edges) {
4        if (e[0] == e[1]) return false;
5        int a = directed ? e[0] : Math.min(e[0], e[1]), b = directed ? e[1] : Math.max(e[0], e[1]);
6        if (!seen.add((long) a * n + b)) return false;
7    }
8    return true;
9}

Classify a graph: simple, connected, tree, DAG, bipartite, complete, dense

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

Property holdsProperty failsBeing checked

verdicts

none yet

Setup

Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.

Step 1 / 10

Java

1boolean isSimple(int n, int[][] edges, boolean directed) {         // no self-loops, no repeated edges
2    Set<Long> seen = new HashSet<>();
3    for (int[] e : edges) {
4        if (e[0] == e[1]) return false;
5        int a = directed ? e[0] : Math.min(e[0], e[1]), b = directed ? e[1] : Math.max(e[0], e[1]);
6        if (!seen.add((long) a * n + b)) return false;
7    }
8    return true;
9}
10boolean isTree(int n, int[][] edges) {           // undirected: n - 1 edges and connected
11    return edges.length == n - 1 && components(n, edges) == 1;
12}
13boolean isDag(int n, int[][] edges) {            // directed: Kahn's algorithm removes every vertex
14    int[] indeg = new int[n]; List<List<Integer>> g = new ArrayList<>();
15    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
16    for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }
17    Deque<Integer> q = new ArrayDeque<>();
18    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
19    int removed = 0;
20    while (!q.isEmpty()) { int u = q.poll(); removed++; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); }
21    return removed == n;
22}
23boolean isComplete(int n, int[][] edges) {       // simple undirected graph with every pair joined
24    return isSimple(n, edges, false) && edges.length == n * (n - 1) / 2;
25}
26double density(int n, int m, boolean directed) { // fraction of the possible edges that are present
27    long possible = directed ? (long) n * (n - 1) : (long) n * (n - 1) / 2;
28    return possible == 0 ? 0 : (double) m / possible;
29}

Live state

0 checks

vertices

edges

kind

undirected

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L1	vertices=5 edges=4 kind=undirected	Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.
2	L1	property=weighted verdict=false	weighted: no. No edge carries a weight: every edge counts the same.
3	L1	property=simple verdict=true	simple: yes. No self-loops and no repeated edges.
4	L1	property=connected verdict=true	connected: yes. One component.
5	L11	property=tree verdict=true	tree: yes. Connected with 5 - 1 = 4 edges.
6	L21	property=DAG verdict=not applicable	DAG: not applicable. A DAG is a directed graph; an undirected edge is a two-way edge.
7	L1	property=bipartite verdict=true	bipartite: yes. The vertices split into two groups with every edge between the groups (checked on the underlying undirected graph).
8	L24	property=complete verdict=false	complete: no. 4 of the 10 possible edges are present.
9	L28	property=sparse verdict=true	sparse: yes. 4 of 10 possible edges = 40%. (This course calls a graph dense from 50% and sparse below; real programs think in terms of E against V and V².)
10	L28	return=simple, connected, tree, bipartite, sparse	Verdicts: simple, connected, tree, bipartite, sparse.

32.02.4

DAG

A **DAG** (directed acyclic graph) is a directed graph with no directed cycle. DAGs describe dependencies: course prerequisites, build targets, task schedules. They can be ordered so that every arrow points forward (a topological order, Chapter 34), and many hard problems become easy on a DAG because dynamic programming can follow that order.

The classifier uses Kahn's algorithm: repeatedly remove a vertex with no incoming arrow; if every vertex is removed, there was no cycle. The preset "A DAG" (0-1 0-2 1-3 2-3 3-4) is accepted; "A directed cycle" (0-1 1-2 2-3 3-1) leaves vertices 1, 2 and 3 stuck, so it is not.

Java

1static boolean isDag(int n, int[][] edges) {     // directed: Kahn's algorithm removes every vertex
2    int[] indeg = new int[n];
3    List<List<Integer>> g = new ArrayList<>();
4    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
5    for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }
6    Deque<Integer> q = new ArrayDeque<>();
7    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
8    int removed = 0;
9    while (!q.isEmpty()) {
10        int u = q.poll();
11        removed++;
12        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
13    }
14    return removed == n;                         // some vertex left over means a cycle
15}

Classify a graph: simple, connected, tree, DAG, bipartite, complete, dense

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

Property holdsProperty failsBeing checked

verdicts

none yet

Setup

Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.

Step 1 / 10

Java

1boolean isSimple(int n, int[][] edges, boolean directed) {         // no self-loops, no repeated edges
2    Set<Long> seen = new HashSet<>();
3    for (int[] e : edges) {
4        if (e[0] == e[1]) return false;
5        int a = directed ? e[0] : Math.min(e[0], e[1]), b = directed ? e[1] : Math.max(e[0], e[1]);
6        if (!seen.add((long) a * n + b)) return false;
7    }
8    return true;
9}
10boolean isTree(int n, int[][] edges) {           // undirected: n - 1 edges and connected
11    return edges.length == n - 1 && components(n, edges) == 1;
12}
13boolean isDag(int n, int[][] edges) {            // directed: Kahn's algorithm removes every vertex
14    int[] indeg = new int[n]; List<List<Integer>> g = new ArrayList<>();
15    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
16    for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }
17    Deque<Integer> q = new ArrayDeque<>();
18    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
19    int removed = 0;
20    while (!q.isEmpty()) { int u = q.poll(); removed++; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); }
21    return removed == n;
22}
23boolean isComplete(int n, int[][] edges) {       // simple undirected graph with every pair joined
24    return isSimple(n, edges, false) && edges.length == n * (n - 1) / 2;
25}
26double density(int n, int m, boolean directed) { // fraction of the possible edges that are present
27    long possible = directed ? (long) n * (n - 1) : (long) n * (n - 1) / 2;
28    return possible == 0 ? 0 : (double) m / possible;
29}

Live state

0 checks

vertices

edges

kind

undirected

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L1	vertices=5 edges=4 kind=undirected	Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.
2	L1	property=weighted verdict=false	weighted: no. No edge carries a weight: every edge counts the same.
3	L1	property=simple verdict=true	simple: yes. No self-loops and no repeated edges.
4	L1	property=connected verdict=true	connected: yes. One component.
5	L11	property=tree verdict=true	tree: yes. Connected with 5 - 1 = 4 edges.
6	L21	property=DAG verdict=not applicable	DAG: not applicable. A DAG is a directed graph; an undirected edge is a two-way edge.
7	L1	property=bipartite verdict=true	bipartite: yes. The vertices split into two groups with every edge between the groups (checked on the underlying undirected graph).
8	L24	property=complete verdict=false	complete: no. 4 of the 10 possible edges are present.
9	L28	property=sparse verdict=true	sparse: yes. 4 of 10 possible edges = 40%. (This course calls a graph dense from 50% and sparse below; real programs think in terms of E against V and V².)
10	L28	return=simple, connected, tree, bipartite, sparse	Verdicts: simple, connected, tree, bipartite, sparse.

32.02.5

Tree

A **tree** is a connected undirected graph with no cycle. Equivalent definitions: connected with exactly n - 1 edges; acyclic with exactly n - 1 edges; exactly one path between any two vertices. Both conditions matter: n - 1 edges alone is not enough, since the edges could form a cycle and leave a vertex out. A forest is an acyclic graph, a collection of trees.

The preset "A path is a tree" (0-1 1-2 2-3 3-4) has 4 edges on 5 vertices and is connected, so it is a tree. To test, check edges == n - 1 and then union the edges: if any edge joins two vertices already connected, there is a cycle; otherwise the graph is a tree. The graph-transform animation shows the same test step by step.

Java

1static boolean isTree(int n, int[][] edges) {    // undirected: n - 1 edges and no cycle (hence connected)
2    if (edges.length != n - 1) return false;
3    int[] parent = new int[n];
4    for (int i = 0; i < n; i++) parent[i] = i;
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) return false;                // the edge closes a cycle
10        parent[a] = b;
11    }
12    return true;
13}

Graph complement, edge reversal and the tree test

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

New edgeOriginal edgeBeing examinedNot a tree edge

Setup

The complement has the same vertices and exactly the pairs that are NOT edges. A simple graph on 5 vertices has n(n-1)/2 = 10 possible edges; 4 are present, so the complement will have 6.

Step 1 / 12

Java

1boolean[][] complement(boolean[][] adj) {        // simple undirected graph
2    int n = adj.length;
3    boolean[][] c = new boolean[n][n];
4    for (int i = 0; i < n; i++)
5        for (int j = 0; j < n; j++)
6            if (i != j) c[i][j] = !adj[i][j];    // an edge is present exactly when it was absent
7    return c;
8}
9List<List<Integer>> reverse(List<List<Integer>> g) {     // directed: flip every edge
10    List<List<Integer>> r = new ArrayList<>();
11    for (int i = 0; i < g.size(); i++) r.add(new ArrayList<>());
12    for (int u = 0; u < g.size(); u++)
13        for (int v : g.get(u)) r.get(v).add(u);          // u -> v becomes v -> u
14    return r;
15}
16boolean isTree(int n, int[][] edges) {           // n - 1 edges and connected (no cycle then follows)
17    if (edges.length != n - 1) return false;
18    DSU d = new DSU(n);
19    for (int[] e : edges) if (!d.union(e[0], e[1])) return false;    // an edge inside one set would close a cycle
20    return true;
21}

Live state

0 edges

edges

possible edges

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L1	edges=4 possible edges=10	The complement has the same vertices and exactly the pairs that are NOT edges. A simple graph on 5 vertices has n(n-1)/2 = 10 possible edges; 4 are present, so the complement will have 6.
2	L6	pair=0-1 present=true complement edges=0	0-1 is an edge of the graph, so it is missing from the complement.
3	L6	pair=0-2 present=false complement edges=1	0-2 is not an edge, so it becomes an edge of the complement.
4	L6	pair=0-3 present=false complement edges=2	0-3 is not an edge, so it becomes an edge of the complement.
5	L6	pair=0-4 present=false complement edges=3	0-4 is not an edge, so it becomes an edge of the complement.
6	L6	pair=1-2 present=true complement edges=3	1-2 is an edge of the graph, so it is missing from the complement.
7	L6	pair=1-3 present=false complement edges=4	1-3 is not an edge, so it becomes an edge of the complement.
8	L6	pair=1-4 present=false complement edges=5	1-4 is not an edge, so it becomes an edge of the complement.
9	L6	pair=2-3 present=true complement edges=5	2-3 is an edge of the graph, so it is missing from the complement.
10	L6	pair=2-4 present=false complement edges=6	2-4 is not an edge, so it becomes an edge of the complement.
11	L6	pair=3-4 present=true complement edges=6	3-4 is an edge of the graph, so it is missing from the complement.
12	L7	return=6 graph + complement=10	The complement has 6 edges, and 4 + 6 = 10: together they make the complete graph.

32.02.6

Bipartite

A graph is **bipartite** when its vertices can be split into two groups with every edge going between the groups, none inside one. Equivalently, it can be coloured with two colours so no edge joins equal colours; equivalently, it has no odd cycle. Matching problems (jobs and workers, students and courses) are bipartite by nature.

In the animation, "An even cycle is bipartite" (0-1 1-2 2-3 3-0) passes: the colours alternate around the square. "A triangle is complete, not bipartite" fails, because a triangle is an odd cycle. The test is a breadth-first colouring started once in every component (Chapter 33 develops it in detail).

Java

1static boolean isBipartite(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    int[] color = new int[n];
6    Arrays.fill(color, -1);
7    for (int s = 0; s < n; s++) {
8        if (color[s] != -1) continue;
9        color[s] = 0;
10        Deque<Integer> q = new ArrayDeque<>();
11        q.add(s);
12        while (!q.isEmpty()) {
13            int u = q.poll();
14            for (int v : g.get(u)) {
15                if (color[v] == -1) { color[v] = color[u] ^ 1; q.add(v); }
16                else if (color[v] == color[u]) return false;     // an edge inside one group: an odd cycle
17            }
18        }
19    }
20    return true;
21}

Classify a graph: simple, connected, tree, DAG, bipartite, complete, dense

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

Property holdsProperty failsBeing checked

verdicts

none yet

Setup

Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.

Step 1 / 10

Java

1boolean isSimple(int n, int[][] edges, boolean directed) {         // no self-loops, no repeated edges
2    Set<Long> seen = new HashSet<>();
3    for (int[] e : edges) {
4        if (e[0] == e[1]) return false;
5        int a = directed ? e[0] : Math.min(e[0], e[1]), b = directed ? e[1] : Math.max(e[0], e[1]);
6        if (!seen.add((long) a * n + b)) return false;
7    }
8    return true;
9}
10boolean isTree(int n, int[][] edges) {           // undirected: n - 1 edges and connected
11    return edges.length == n - 1 && components(n, edges) == 1;
12}
13boolean isDag(int n, int[][] edges) {            // directed: Kahn's algorithm removes every vertex
14    int[] indeg = new int[n]; List<List<Integer>> g = new ArrayList<>();
15    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
16    for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }
17    Deque<Integer> q = new ArrayDeque<>();
18    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
19    int removed = 0;
20    while (!q.isEmpty()) { int u = q.poll(); removed++; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); }
21    return removed == n;
22}
23boolean isComplete(int n, int[][] edges) {       // simple undirected graph with every pair joined
24    return isSimple(n, edges, false) && edges.length == n * (n - 1) / 2;
25}
26double density(int n, int m, boolean directed) { // fraction of the possible edges that are present
27    long possible = directed ? (long) n * (n - 1) : (long) n * (n - 1) / 2;
28    return possible == 0 ? 0 : (double) m / possible;
29}

Live state

0 checks

vertices

edges

kind

undirected

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L1	vertices=5 edges=4 kind=undirected	Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.
2	L1	property=weighted verdict=false	weighted: no. No edge carries a weight: every edge counts the same.
3	L1	property=simple verdict=true	simple: yes. No self-loops and no repeated edges.
4	L1	property=connected verdict=true	connected: yes. One component.
5	L11	property=tree verdict=true	tree: yes. Connected with 5 - 1 = 4 edges.
6	L21	property=DAG verdict=not applicable	DAG: not applicable. A DAG is a directed graph; an undirected edge is a two-way edge.
7	L1	property=bipartite verdict=true	bipartite: yes. The vertices split into two groups with every edge between the groups (checked on the underlying undirected graph).
8	L24	property=complete verdict=false	complete: no. 4 of the 10 possible edges are present.
9	L28	property=sparse verdict=true	sparse: yes. 4 of 10 possible edges = 40%. (This course calls a graph dense from 50% and sparse below; real programs think in terms of E against V and V².)
10	L28	return=simple, connected, tree, bipartite, sparse	Verdicts: simple, connected, tree, bipartite, sparse.

32.02.7

Complete

A **complete graph** K_n has an edge between every pair of vertices: n(n-1)/2 edges when undirected, n(n-1) arrows when directed. It is the densest simple graph. The triangle K_3 has 3 edges, K_4 has 6 and K_5 has 10.

The preset "A triangle is complete, not bipartite" shows K_3: the classifier finds 3 edges out of the 3 possible and reports 'complete'. Complete graphs appear as worst cases (every pair is adjacent) and in problems about cliques. Note that 'complete' needs a simple graph: duplicate edges could fake the right count.

Java

1static boolean isComplete(int n, int[][] edges) {        // simple undirected graph with every pair joined
2    if (!isSimple(n, edges)) return false;       // repeated edges could fake the count
3    return edges.length == n * (n - 1) / 2;
4}
5private static boolean isSimple(int n, int[][] edges) {
6    Set<Long> seen = new HashSet<>();
7    for (int[] e : edges) {
8        if (e[0] == e[1]) return false;
9        if (!seen.add((long) Math.min(e[0], e[1]) * n + Math.max(e[0], e[1]))) return false;
10    }
11    return true;
12}

Classify a graph: simple, connected, tree, DAG, bipartite, complete, dense

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

Property holdsProperty failsBeing checked

verdicts

none yet

Setup

Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.

Step 1 / 10

Java

1boolean isSimple(int n, int[][] edges, boolean directed) {         // no self-loops, no repeated edges
2    Set<Long> seen = new HashSet<>();
3    for (int[] e : edges) {
4        if (e[0] == e[1]) return false;
5        int a = directed ? e[0] : Math.min(e[0], e[1]), b = directed ? e[1] : Math.max(e[0], e[1]);
6        if (!seen.add((long) a * n + b)) return false;
7    }
8    return true;
9}
10boolean isTree(int n, int[][] edges) {           // undirected: n - 1 edges and connected
11    return edges.length == n - 1 && components(n, edges) == 1;
12}
13boolean isDag(int n, int[][] edges) {            // directed: Kahn's algorithm removes every vertex
14    int[] indeg = new int[n]; List<List<Integer>> g = new ArrayList<>();
15    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
16    for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }
17    Deque<Integer> q = new ArrayDeque<>();
18    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
19    int removed = 0;
20    while (!q.isEmpty()) { int u = q.poll(); removed++; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); }
21    return removed == n;
22}
23boolean isComplete(int n, int[][] edges) {       // simple undirected graph with every pair joined
24    return isSimple(n, edges, false) && edges.length == n * (n - 1) / 2;
25}
26double density(int n, int m, boolean directed) { // fraction of the possible edges that are present
27    long possible = directed ? (long) n * (n - 1) : (long) n * (n - 1) / 2;
28    return possible == 0 ? 0 : (double) m / possible;
29}

Live state

0 checks

vertices

edges

kind

undirected

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L1	vertices=5 edges=4 kind=undirected	Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.
2	L1	property=weighted verdict=false	weighted: no. No edge carries a weight: every edge counts the same.
3	L1	property=simple verdict=true	simple: yes. No self-loops and no repeated edges.
4	L1	property=connected verdict=true	connected: yes. One component.
5	L11	property=tree verdict=true	tree: yes. Connected with 5 - 1 = 4 edges.
6	L21	property=DAG verdict=not applicable	DAG: not applicable. A DAG is a directed graph; an undirected edge is a two-way edge.
7	L1	property=bipartite verdict=true	bipartite: yes. The vertices split into two groups with every edge between the groups (checked on the underlying undirected graph).
8	L24	property=complete verdict=false	complete: no. 4 of the 10 possible edges are present.
9	L28	property=sparse verdict=true	sparse: yes. 4 of 10 possible edges = 40%. (This course calls a graph dense from 50% and sparse below; real programs think in terms of E against V and V².)
10	L28	return=simple, connected, tree, bipartite, sparse	Verdicts: simple, connected, tree, bipartite, sparse.

32.02.8

Sparse/dense

A graph is **sparse** when it has few edges compared with the possible number (about V or V log V) and **dense** when the edge count is close to V². There is no sharp line; what matters is which of E and V² dominates in an algorithm's running time. Road networks and social networks are sparse; the complete graph is dense.

Density is E divided by the number of possible edges. The classifier calls a graph dense from 50% and sparse below, a convention used only in this course for the animation: the path on 5 vertices has 4 of 10 possible edges (40%, sparse) and the 4-cycle has 4 of 6 (67%, dense). For real programs think in terms of E against V²: an adjacency matrix pays V² whatever E is.

Java

1static double density(int n, long m, boolean directed) {         // the fraction of possible edges that are present
2    long possible = directed ? (long) n * (n - 1) : (long) n * (n - 1) / 2;
3    return possible == 0 ? 0 : (double) m / possible;
4}

Classify a graph: simple, connected, tree, DAG, bipartite, complete, dense

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

Property holdsProperty failsBeing checked

verdicts

none yet

Setup

Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.

Step 1 / 10

Java

1boolean isSimple(int n, int[][] edges, boolean directed) {         // no self-loops, no repeated edges
2    Set<Long> seen = new HashSet<>();
3    for (int[] e : edges) {
4        if (e[0] == e[1]) return false;
5        int a = directed ? e[0] : Math.min(e[0], e[1]), b = directed ? e[1] : Math.max(e[0], e[1]);
6        if (!seen.add((long) a * n + b)) return false;
7    }
8    return true;
9}
10boolean isTree(int n, int[][] edges) {           // undirected: n - 1 edges and connected
11    return edges.length == n - 1 && components(n, edges) == 1;
12}
13boolean isDag(int n, int[][] edges) {            // directed: Kahn's algorithm removes every vertex
14    int[] indeg = new int[n]; List<List<Integer>> g = new ArrayList<>();
15    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
16    for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }
17    Deque<Integer> q = new ArrayDeque<>();
18    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
19    int removed = 0;
20    while (!q.isEmpty()) { int u = q.poll(); removed++; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); }
21    return removed == n;
22}
23boolean isComplete(int n, int[][] edges) {       // simple undirected graph with every pair joined
24    return isSimple(n, edges, false) && edges.length == n * (n - 1) / 2;
25}
26double density(int n, int m, boolean directed) { // fraction of the possible edges that are present
27    long possible = directed ? (long) n * (n - 1) : (long) n * (n - 1) / 2;
28    return possible == 0 ? 0 : (double) m / possible;
29}

Live state

0 checks

vertices

edges

kind

undirected

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L1	vertices=5 edges=4 kind=undirected	Undirected graph with 5 vertices and 4 edges. Each property below is decided from the vertices and edges alone.
2	L1	property=weighted verdict=false	weighted: no. No edge carries a weight: every edge counts the same.
3	L1	property=simple verdict=true	simple: yes. No self-loops and no repeated edges.
4	L1	property=connected verdict=true	connected: yes. One component.
5	L11	property=tree verdict=true	tree: yes. Connected with 5 - 1 = 4 edges.
6	L21	property=DAG verdict=not applicable	DAG: not applicable. A DAG is a directed graph; an undirected edge is a two-way edge.
7	L1	property=bipartite verdict=true	bipartite: yes. The vertices split into two groups with every edge between the groups (checked on the underlying undirected graph).
8	L24	property=complete verdict=false	complete: no. 4 of the 10 possible edges are present.
9	L28	property=sparse verdict=true	sparse: yes. 4 of 10 possible edges = 40%. (This course calls a graph dense from 50% and sparse below; real programs think in terms of E against V and V².)
10	L28	return=simple, connected, tree, bipartite, sparse	Verdicts: simple, connected, tree, bipartite, sparse.

Practice ladder

Now try it yourself

Easy

Find the Town Judge
Find Center of Star Graph

Medium

Is Graph Bipartite?
Course Schedule
Graph Valid Tree

Advanced

Possible Bipartition
Redundant Connection

Key takeaways

Directed or undirected, weighted or not, simple or multi: decide these first.
A tree is connected and acyclic with n - 1 edges; a DAG is directed with no cycle; bipartite means no odd cycle.
A complete graph has n(n-1)/2 edges; density is edges over possible edges.