Chapter 14: Graphs

14.1Basic concepts

Graph algorithms speak a small vocabulary: vertex, edge, degree, path, cycle, connectivity. The words mean roughly what they do in everyday speech, but each has a precise definition, and correctness arguments rest on it.

14.1.1What is a graph?

A city map shows intersections, the roads between them, and much detail besides: lengths, slopes, lanes. To answer “which intersection can I reach from which?” two facts suffice: the intersections, and which pairs are joined directly by a road. The abstract structure built from these two facts is a graph.

|V| is the size of V. Throughout, n counts vertices, m counts edges, and costs are stated in these terms: “O(n + m) time” grows with vertices plus edges.

A graph generalizes a tree, which has a root, one parent per non-root node, and no cycles. A graph requires none of this:

• No root. No vertex is special; an algorithm must be told where to start.
• Cycles. Edges can lead back to the start; in Figure 14.1, 1 → 2 → 3 → 1 is one.
• Several routes. From 0 to 3 you can go 0 → 1 → 3 or 0 → 4 → 3.

A tree models one-to-many relationships; a graph models many-to-many ones. A person has many friends, each with many friends; a course has several prerequisites and is a prerequisite of several others. The algorithms pay for this flexibility: they may reach a vertex twice and must notice.

14.1.2Vertices and edges

A vertex stands for a modeled object: a city, a person, a computer, a web page, a course. It may carry a label, name, or position, but algorithms prefer vertices numbered 0 to n − 1, so per-vertex data can live in arrays indexed by vertex.

Modeled as a graph, “what is the shortest route from Istanbul to Van?” becomes a graph algorithm problem; with road lengths on the edges, Dijkstra's algorithm solves it (14.4.4). Modeling keeps the essence and drops the rest: paving is irrelevant to the shortest route, length is not.

An edge stands for a relationship: a road, a network link, a friendship. If (v, w) is an edge, v and w are adjacent, each a neighbor of the other, and the edge is incident to both. In Figure 14.1, 1 and 3 are neighbors; 0 and 2 are not.

Figure 14.3 shows a typical trait of real networks: many vertices, few neighbors each. Millions of members, but at most a few thousand friends per person, so the edges are a tiny fraction of those possible. Such graphs are sparse, and sparsity decides how to store them (14.2.6).

14.1.3Degree and the handshake lemma

An intersection's degree is the number of roads meeting there. A road that leaves an intersection and returns to it is attached at both ends, which is why a self-loop counts twice.

The degrees in Figure 14.4 sum to 1 + 3 + 3 + 2 + 5 + 2 + 0 = 16, and the graph has seven ordinary edges plus a self-loop, eight in all. The sum being exactly twice the edge count is no accident.

At a party, the numbers of hands each guest shook add up to twice the number of handshakes, since each handshake involves two hands. Two consequences:

• The degrees give the edge count: m = Σ deg(v) / 2. Degrees summing to 30 mean 15 edges.
• The sum is even, so the number of odd-degree vertices is even. No graph has degrees 3, 3, 2, 2, 1: their sum is 11.

14.1.4Directed graphs

Friendship is symmetric, and a two-way road runs both ways. Other relationships go one way: a web page may link to one that does not link back, a prerequisite does not work in reverse, a one-way street runs one way. These are modeled by a directed graph, or digraph.

Count the arrows: two enter B (from A and D), so its in-degree is 2; two leave E (to D and F), so its out-degree is 2. Nothing enters A or leaves F.

Both rows sum to 6, the number of edges: each arrow adds 1 to its tail's out-degree and 1 to its head's in-degree, so Σ in-degree = Σ out-degree = m. In directed graphs, the undirected 2m splits into two sums.

Reachability depends on direction too. In Figure 14.5 A reaches B, but nothing reaches A. From B you can go to C, E, D, and back to B, so B, C, E, and D reach one another, while A and F hang off this group.

14.1.5Paths and cycles

In an unweighted graph a path's length is its number of edges: k + 1 vertices, length k. A path that follows the arrows of a directed graph is a directed path; such a cycle is a directed cycle.

Both cycles in Figure 14.6 have length six, and there are others: C → G → L → C uses the edges C–G, G–L, and L–C. The number of cycles grows fast with the number of edges.

In a tree, exactly one simple path joins any two nodes. In a graph there may be several, and two different simple paths together form a cycle. Istanbul → Ankara → Izmir → Istanbul is a simple cycle of flights: no city is visited twice. Istanbul → Ankara → Izmir → Ankara → Istanbul passes Ankara twice, so it is a cycle but not a simple one.

14.1.6Two example graphs

Here are the concepts at work on a small undirected graph and a small directed one.

A sequence is a path if each consecutive pair is an edge; 2 → 5 → 3 is not, since 5–3 is missing. Only then do we check simplicity: does a vertex repeat?

14.1.7Connected and complete graphs

Connectivity asks for a path, completeness for an edge: a complete graph is connected, not necessarily vice versa. “Largest” matters: a component includes every vertex that can reach any of its members. Components split the vertices into disjoint groups; a connected graph has one.

The edge count has two bounds. In a simple undirected graph (no self-loops or parallel edges) each vertex pair has at most one edge, and there are n(n − 1)/2 pairs: n choices, then n − 1, halved because each pair is counted twice. So m ≤ n(n − 1)/2, with equality only when complete: K₅ has 5 · 4 / 2 = 10 edges, the complete graph on 10 vertices 10 · 9 / 2 = 45.

A connected graph has m ≥ n − 1. Add edges one by one to an empty graph: it starts with n components, and each edge either merges two or falls inside one, so reaching one component takes at least n − 1 edges. A connected graph with exactly n − 1 edges is a tree, as we will see again with spanning trees (14.5.1).

These bounds separate sparse from dense graphs: m ≈ n is sparse, m ≈ n² dense. Road and social networks are sparse; small groups where everyone knows everyone are dense.

14.1.8Weighted graphs

Often a connection has a cost: a road's length, a link's latency, a pipeline's price, a line's capacity.

Hence shortest-path algorithms. Without weights the shortest path has the fewest edges; with weights, edge counts mislead and the weight sum decides. An unweighted graph is a weighted one with all weights 1.

14.1.9The graph ADT

A graph can first be defined as an abstract data type (ADT): which operations exist and what they do, not how memory carries them out. The Graph interface of Goodrich, Tamassia, and Goldwasser has these basic operations.

Algorithms lean on two of these: getEdge(u, v) (are u and v adjacent?) and outgoingEdges(v) (who are v's neighbors?). BFS, DFS, Dijkstra, and Prim call the second once per vertex, so how fast a representation lists neighbors sets their running time.

removeVertex(v) removes the incident edges for consistency: an edge without an endpoint is meaningless. The cost of each operation depends on the representation.

14.2Graph representations

A graph can be stored in three forms, each speeding up some operations and slowing others. We take them in turn, compare their costs, and trace how Java builds an adjacency list and matrix.

14.2.1Three representations; the edge list

The three basic ways to store a graph are:

• Edge list: all edges in a single list, such as [(A,B), (A,E), …].
• Adjacency list: for each vertex, a list of its neighbors, such as V[i] = {j, k, l}.
• Adjacency matrix: an n × n array whose cell M[i][j] records whether there is an edge from i to j.

The edge list is the simplest: for Figure 14.11 it is (A, B) (A, E) (B, C) (B, E) (C, D) (D, E). A separate vertex list keeps edgeless vertices, for O(n + m) memory. Adding an edge appends one item: O(1).

Queries are the weakness. Testing adjacency means searching the unordered list for (u, v) or (v, u), O(m) in the worst case, and finding u's neighbors means scanning it all, since u's edges can be anywhere. Traversals ask this for every vertex, so they cost O(n · m). Kruskal's algorithm, which sorts edges by weight and never asks for neighbors, is where the edge list shines (14.5.3).

14.2.2The adjacency matrix

An undirected edge (i, j) goes into both matrix[i][j] and matrix[j][i], so the matrix is symmetric about the diagonal: matrix[i][j] == matrix[j][i]. A directed graph's matrix is not.

The matrix's strength is direct access: a Java array cell is read or written in constant time, so three operations are O(1):

• Testing for edge i–j reads matrix[i][j].
• Adding an edge writes 1 into one cell (two if undirected).
• Removing it writes 0 there.

It has two weaknesses. Listing neighbors scans all n cells of a row, O(n) even for a single neighbor. And the matrix takes n² cells regardless of edges; in a sparse graph nearly all are 0, memory spent on edges that do not exist.

14.2.3Adjacency matrices: three examples

Here are the matrices of three graphs on the vertices A–E: undirected, directed, and weighted. Rows and columns run A, B, C, D, E.

Each undirected edge fills two cells: six edges, twelve 1s, symmetric about the diagonal (row A, column E and row E, column A are both 1). Row sums are degrees: row B has three 1s (A, C, E), so deg(B) = 3. Without self-loops, the diagonal is 0.

Each arrow fills one cell: nine arrows, nine 1s. Rows are sources and columns destinations, so there is no symmetry: A → B sets m[A][B] = 1, but m[B][A] = 0. Row sums are out-degrees, column sums in-degrees: D's out-degree is 3; row C is all 0s, since nothing leaves C; column C has two 1s (from B and D), so C's in-degree is 2.

Weighted cells hold weights: the 4 at row A, column B weighs A → B. Missing edges hold ∞; the diagonal holds 0, a vertex's distance to itself. This suits shortest paths: ∞ means “no direct route” and behaves in sums, since ∞ plus anything is ∞.

14.2.4The adjacency list

An undirected edge (v, w) goes into two lists: w into v's and v into w's. A directed edge goes only into its source's list. Since only existing edges are stored, memory is n list heads plus the entries: 2m entries if undirected, m if directed, O(n + m) either way.

Lists are strong at traversal: visiting a vertex's neighbors reads its list in O(deg(v)), never touching non-neighbors as the matrix does. Adding an edge appends: amortized O(1) for a dynamic array, O(1) for a linked list.

They are weak at edge queries. Unless sorted, u's list must be scanned for v: O(deg(u)), or O(min(deg u, deg v)) if an undirected graph scans the shorter list. For high-degree vertices this is slow next to the matrix's O(1).

14.2.5Adjacency lists: three examples

Here are the adjacency lists of the three graphs of Figure 14.13, neighbors in alphabetical order.

• Undirected. Six edges make 12 entries, each edge written twice. A list's length is the vertex's degree: B's list has three items, and deg(B) = 3.
• Directed. Only outgoing edges: nine arrows, nine entries; C's list is empty. Length is the out-degree; in-degrees need a scan of every list, a drawback for directed graphs.
• Weighted. Entries are (neighbor, weight) pairs; B's list is (C, 3), (D, 3). Java uses an int[]{v, w} or a small Edge class.

14.2.6What each representation costs

Choose by the graph's structure and its most frequent operation:

• Sparse graphs (m ≈ n), like road and social networks: a matrix's n² cells sit nearly empty, while a list keeps memory at O(n + m) and speeds traversal. Every traversal and shortest-path algorithm here runs in or near O(n + m) with lists.
• Dense graphs (m ≈ n²): few cells are wasted, and frequent edge queries favor the matrix's O(1).

14.2.7An adjacency list in Java

With vertices numbered 0 to n − 1, an adjacency list is a list of lists: item i of the outer list is the neighbor list of vertex i.

class Graph {
    private final int n;                                  // vertices: 0..n-1
    private final List<List<Integer>> adj = new ArrayList<>();
    Graph(int n) {
        this.n = n;
        for (int i = 0; i < n; i++)
            adj.add(new ArrayList<>());
    }
    void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);                    // omit this line in a directed graph
    }
    List<Integer> neighbors(int u) { return adj.get(u); }   // O(1)
    int degree(int u) { return adj.get(u).size(); }
}

• adj is a List<List<Integer>>: one inner ArrayList (dynamic array) per vertex.
• The constructor stores n and adds n empty lists in O(n). All vertices are known up front, so adj.get(u) is valid for every u.
• addEdge(u, v) puts v in u's list and u in v's; a directed graph drops the second line. Like ArrayList.add, it is amortized O(1).
• neighbors(u) returns the list itself, uncopied, in O(1); iterating over it costs the caller O(deg(u)).
• degree(u) is the list's size, O(1) since ArrayList stores it.

The matrix version is shorter: boolean[][] m = new boolean[n][n]; creates it, m[u][v] = m[v][u] = true; adds an edge, m[u][v] queries. With weights, a list item becomes an int[]{v, w} or a small Edge class, and the matrix an int[][] with Integer.MAX_VALUE for missing edges.

14.2.8Code trace: building an adjacency list

We build a five-vertex graph from six edges, in the order {0,1}, {0,4}, {1,2}, {1,4}, {2,3}, {3,4}. The traced code is the constructor, addEdge, and the main fragment that calls them.

Graph(int n) {
  this.n = n;
  for (int i = 0; i < n; i++)
    adj.add(new ArrayList<>());
}
void addEdge(int u, int v) {
  adj.get(u).add(v);
  adj.get(v).add(u);  // not if directed
}
// main:
Graph g = new Graph(5);
int[][] E = {{0,1}, {0,4}, {1,2},
             {1,4}, {2,3}, {3,4}};
for (int[] e : E) g.addEdge(e[0], e[1]);

First the constructor: new Graph(5) sets n = 5, and the loop runs i = 0 to 4, giving each vertex an empty list.

Then the edges. addEdge(0, 1) appends 1 to 0's list, then 0 to 1's; every call does the same. Lists keep insertion order: 1's list is [0, 2, 4] because 0–1, 1–2, and 1–4 arrived in that order.

Six edges produce 2 · 6 = 12 entries. The list lengths 2, 3, 2, 2, 3 sum to 12, the handshake lemma as it shows up in code; degree(1) is the size of 1's list, 3. Each addEdge takes constant time, and memory is O(n + m).

14.2.9Code trace: building an adjacency matrix

Now the same six edges go into a 5 × 5 boolean matrix.

boolean[][] m = new boolean[n][n];
void addEdge(int u, int v) {
  m[u][v] = true;
  m[v][u] = true;  // not in a directed graph
}
// main: the same 6 edges (n = 5)
for (int[] e : E) g.addEdge(e[0], e[1]);

new boolean[n][n] allocates 25 cells, which Java initializes to false: no edges yet. Even creating the matrix takes O(n²), since every cell must receive its initial value.

Each addEdge(u, v) writes two cells. addEdge(0, 1) sets m[0][1] = true (row 0, column 1) and then the symmetric cell m[1][0]. The six edges fill the cell pairs (0,1)–(1,0), (0,4)–(4,0), (1,2)–(2,1), (1,4)–(4,1), (2,3)–(3,2), (3,4)–(4,3).

Even here the difference shows. “Edge 2–4?” is one access to m[2][4] (false); the list must scan [1, 3]. But 2's neighbors cost five cells in the matrix and two items in the list. Thirteen of 25 cells carry nothing, and the ratio worsens fast as graphs grow and thin out.

14.3Traversal: BFS and DFS

Most graph algorithms rest on a systematic exploration of the graph: breadth-first or depth-first search. Both visit the same vertices, in orders that suit different problems. Four applications follow: connected components, bipartiteness, topological sorting, and directed cycle detection.

14.3.1Traversal and visited marks

There are two basic methods:

• Breadth-first search (BFS) visits all neighbors of the start, then their neighbors, level by level, using a queue (FIFO: first in, first out).
• Depth-first search (DFS) goes as deep as it can along one path, backs up at a dead end, and tries another branch, using a stack (LIFO: last in, first out) or recursion.

In a tree one path leads from the root to each node, so descending to children never reaches a node twice. A graph may have cycles and several routes to a vertex, so its traversal must record what it has seen, usually in a boolean[] visited array indexed by vertex.

14.3.2Breadth-first search

Drop a stone into water and the ripples spread in rings, near ones first, then farther ones. BFS works the same way: it finds the vertices one edge from the start, then those two edges away, then three. The vertices k edges from the start form level k.

A queue enforces this order: discovered vertices join the back, and processing takes from the front. All of level 1 enters before any of level 2, so all of level 1 is processed first.

The edges by which BFS discovers vertices form the BFS tree. In Figure 14.18, d is reachable from a or b; a comes first, so d enters along a–d and b–d stays out. Tree paths from the root have the fewest possible edges, the basis of unweighted shortest paths (14.4.1).

BFS finds unweighted shortest paths and discovers near vertices first: “friends of friends” is level 2, and a web crawler scans a site layer by layer. Its weakness is memory: a whole level may wait in the queue, which grows large in wide graphs.

14.3.3The BFS algorithm and code

First the pseudocode, then the Java.

BFS(start):
  queue.add(start)
  mark start visited
  while queue is not empty:
    w = queue.remove()
    for each unvisited
        neighbor u of w:
      mark u visited
      queue.add(u)

void bfs(int s) {
  boolean[] visited = new boolean[n];
  Queue<Integer> q = new ArrayDeque<>();
  visited[s] = true;  q.add(s);
  while (!q.isEmpty()) {
    int w = q.poll();
    System.out.print(w + " ");
    for (int u : adj.get(w))
      if (!visited[u]) {
        visited[u] = true;
        q.add(u);
      }
  }
}

The method belongs to the Graph class of 14.2.7 and uses its fields n and adj:

• boolean[] visited = new boolean[n]; allocates one mark per vertex, all false.
• Queue<Integer> q = new ArrayDeque<>(); creates an empty queue; add appends at the back, poll removes the front, both O(1).
• visited[s] = true; q.add(s); marks and enqueues the start.
• Until the queue empties, each round removes and prints the front vertex w.
• The inner loop marks and enqueues each unvisited neighbor u of w.

The subtle point is when to mark: on entering the queue, not on leaving. A vertex on several lists then enters once; marking on removal would let another neighbor enqueue it again while it waits.

Cost. Each vertex enters and leaves the queue once, O(n), and its list is scanned once; the lists total 2m entries, O(m). So BFS takes O(n + m) with lists and O(n²) with a matrix, whose rows have n cells. visited and the queue take O(n) extra memory.

14.3.4Code trace: bfs(A)

We trace bfs(A) on a graph with nine vertices, numbered A = 0, B = 1, …, I = 8, and 11 edges. Neighbor lists are alphabetical: A: B, F, I · B: A, C, E · C: B, D, E · D: C, G, H · E: B, C, G · F: A, G · G: D, E, F · H: D · I: A.

A is marked and enqueued. Round 1 removes and prints A and enqueues its unvisited neighbors B, F, I: level 1.

Round 2 removes B. Its neighbor A is marked and skipped (without the mark, A would re-enter the queue); C and E join the back, giving [F, I, C, E], level 1 in front, level 2 behind. The queue keeps levels apart by itself.

Round 3 removes F and adds G; round 4 removes I and adds nothing, ending level 1. Round 5 removes C and adds D (level 3). E and G find every neighbor marked. Round 8 has D add H (level 4), and removing H empties the queue.

The output A B F I C E G D H shows the levels as consecutive blocks: {A}, {B, F, I}, {C, E, G}, {D}, {H}. The BFS tree has the eight edges A–B, A–F, A–I, B–C, B–E, F–G, C–D, D–H, as nine vertices require. Each vertex was enqueued once; the scans covered 2m = 22 entries.

14.3.5Depth-first search

In a maze, you walk a corridor to its end; at a dead end you return to the last fork and try a new corridor. That is DFS: it goes as deep as it can, and at a vertex with no unvisited neighbors it backtracks to try another branch.

Compare Figure 14.18: same graph, different order. BFS visits all of s's neighbors a, b, c next; DFS descends s, a, d, b, finds b's neighbors all seen, backs up to s, and descends to c, then e.

DFS stores only the current path, so on wide, shallow graphs it needs less memory than BFS, and it suits problems where a path is followed to its end (mazes, game trees). But its paths need not be shortest: it reached b by s → a → d → b, three edges, though s–b exists. Its main uses are mazes, cycle detection, connected components, and topological sorting of DAGs.

14.3.6DFS code: recursive and with an explicit stack

The shortest way to write DFS is recursively.

void dfs(int v, boolean[] visited) {
  visited[v] = true;
  System.out.print(v + " ");
  for (int u : adj.get(v))
    if (!visited[u])
      dfs(u, visited);
}

The method marks and prints v, then calls itself on each unvisited neighbor in turn. The loop waits for each call to return, so everything below the first neighbor is finished before the second: “deepest first.” When the neighbors run out, the method returns and the caller resumes; that return is backtracking.

Recursion keeps the stack for us as the call stack: the active dfs frames, in order, are the path from the start to the current vertex. An explicit stack works too:

void dfsStack(int s) {
  boolean[] visited = new boolean[n];
  Deque<Integer> stack = new ArrayDeque<>();
  stack.push(s);  visited[s] = true;
  while (!stack.isEmpty()) {
    int v = stack.peek();
    Integer next = null;
    for (int u : adj.get(v))
      if (!visited[u]) { next = u; break; }
    if (next == null) stack.pop(); // back up
    else { visited[next] = true;
           stack.push(next); }
  }
}

This imitates the recursion step by step. The top (peek) is the current vertex; each round seeks its first unvisited neighbor. Found, it is marked and pushed, like a recursive call; not found (next == null), the top is popped, like a return. The break makes the search descend at the first suitable neighbor.

An explicit stack also avoids StackOverflowError: Java's call stack is limited, and recursive DFS on a path of hundreds of thousands of vertices can overflow it, while an explicit stack lives on the heap.

Cost. Recursive DFS calls dfs once per vertex and walks each list once: O(n + m). The explicit-stack version rescans a list from the start at every peek, skipping marked neighbors again each time a vertex resurfaces, at most its degree plus one times; the worst case approaches Σ deg(v)². A per-list “where I left off” index restores O(n + m). The code favors simplicity; for small degrees the difference is negligible.

14.3.7Code trace: recursive dfs(A)

We trace dfs(A, visited) on the graph of Figure 14.19, neighbors again in alphabetical order.

Steps 1–6 only go forward, the stack growing a frame each step: A → B → C → D → G → E. At E every neighbor is marked, and the first backtrack returns to G, which resumes its list: D and E are done, F is next.

A caller resumes where it left off, not from the start. In step 12 the search returns to C, whose list B, D, E has only E left, already marked below G. Each list is walked exactly once.

The order is A B C D G E F H I; the DFS tree edges are A–B, B–C, C–D, D–G, G–E, G–F, D–H, A–I; the stack peaks at six frames. The DFS tree is longer and thinner than the BFS tree: five edges from root to E, against two.

14.3.8Code trace: dfsStack(A)

Now the explicit-stack version: each round peeks, seeks the first unvisited neighbor, and pushes or pops.

The loop runs 17 rounds: 8 pushes (every vertex but A) and 9 pops (every vertex). Pushes visit vertices in the order A B C D G E F H I, as in the recursive version, and the stack always matches the call stack of Table 14.11. One algorithm; only the keeper of the stack differs.

14.3.9BFS versus DFS

Both take O(n + m): each vertex is processed once and each adjacency entry scanned once. An undirected graph has 2m entries, but the constant vanishes in big-O.

Both need O(n) extra memory at worst, in different worst cases: BFS suffers on wide graphs, where many neighbors enter the queue at once; DFS on deep ones, where the stack grows as long as the longest chain.

The traces assume alphabetical lists. Other list orders change the visiting order but not the visited set or the cost: from H, BFS gives H D C G B E F A I and DFS H D C B A F G E I. And replacing the stack of explicit-stack DFS with a queue, adding all neighbors at once, turns it into BFS: the searches differ in which end of the helper structure they read.

14.3.10Connected components

A traversal visits only its start's component. To find them all, restart from each unassigned vertex; each restart is a new component.

int components(int[] comp) {
  Arrays.fill(comp, -1);
  int count = 0;
  for (int s = 0; s < n; s++)
    if (comp[s] == -1) dfs(s, count++, comp);
  return count;
}
void dfs(int v, int c, int[] comp) {
  comp[v] = c;
  for (int u : adj.get(v))
    if (comp[u] == -1) dfs(u, c, comp);
}

comp holds component numbers, −1 meaning “unassigned,” and doubles as the visited mark. The outer loop scans vertices 0 to n − 1, calling dfs(s, count++, comp) at each −1. The post-increment passes the old value, so the first component is 0. dfs writes the number into every vertex it reaches.

Inside dfs(0, 0): 0 is colored, then its neighbor 1, whose only neighbor 0 is done, so the call returns; then 2, likewise. The method returns 3: components {0, 1, 2}, {3, 4}, {5}.

The cost is O(n + m): n outer rounds, each vertex colored once with its list walked once, each edge seen once from each end. Afterward, “same component?” is the O(1) test comp[u] == comp[v], instead of an O(n + m) traversal per query.

14.3.11Testing whether a graph is bipartite

Matching problems produce bipartite graphs: students on one side, projects on the other, an edge meaning “this student wants this project.” Two-shift scheduling and conflict-free grouping look the same.

Think of the groups as two colors, every neighbor of a vertex having the other color. BFS tests this: color the start 0 and each newly discovered vertex the opposite of its discoverer. A colored neighbor with the current vertex's color means the graph is not bipartite.

// color[] starts at -1; BFS from s
color[s] = 0;  q.add(s);
while (!q.isEmpty()) {
  int w = q.poll();
  for (int u : adj.get(w))
    if (color[u] == -1) {
      color[u] = 1 - color[w];  q.add(u);
    } else if (color[u] == color[w]) return false;
}
return true;

color starts at −1 (“uncolored”); 1 - color[w] flips 0 and 1. It is BFS plus a color check at colored neighbors.

The general rule: a graph is bipartite if and only if it has no odd-length cycle. Colors alternate around a cycle, and returning to the start with its original color requires an even number of edges; so C₅ is not bipartite and C₆ is. The test costs O(n + m), like BFS; a disconnected graph is handled by restarting at each uncolored vertex.

14.3.12Topological sorting and Kahn's algorithm

A student must take courses in an order where each follows all its prerequisites. With an arrow u → v when u is a prerequisite of v, this is a directed graph, and the order is a topological order.

Why cycles rule it out: given a → b → c → a, a must precede b, b precede c, and c precede a, so a precedes itself. Each course on the cycle waits for another, and none can start.

The order need not be unique: courses ready at the same time can go in any order, so the DAG 0 → 1, 0 → 2, 1 → 3, 2 → 3 allows 0 1 2 3 and 0 2 1 3. Uses include course plans, task dependencies, build order, and workflows.

Kahn's algorithm: a vertex of in-degree 0 has no prerequisites and can go first. Once output, its arrows count as deleted, lowering their heads' in-degrees; vertices reaching 0 become ready and wait in a queue.

Kahn(G):
  q = vertices with inDegree 0
  result = []
  while q is not empty:
    u = remove from q
    append u to result
    for each edge (u, v) leaving u:
      inDegree[v]--
      if inDegree[v] == 0:
        add v to q
  if result.size < n:
    there is a cycle
  return result

List<Integer> kahn(List<List<Integer>> adj) {
  int n = adj.size();
  int[] indeg = new int[n];
  for (List<Integer> l : adj)
    for (int v : l) indeg[v]++;
  Queue<Integer> q = new ArrayDeque<>();
  for (int v = 0; v < n; v++)
    if (indeg[v] == 0) q.add(v);
  List<Integer> result = new ArrayList<>();
  while (!q.isEmpty()) {
    int u = q.poll();
    result.add(u);
    for (int v : adj.get(u))
      if (--indeg[v] == 0) q.add(v);
  }
  return result;  // size < n → cycle
}

The Java code has three phases:

1. Counting. Nested loops increment indeg at each arrow's head, in O(n + m).
2. Initialization. Vertices of in-degree 0 are enqueued.
3. Main loop. Dequeue u, append it to the result, and run --indeg[v] for each arrow's head; the prefix decrement yields the new value, and at 0, v is enqueued.

If the result has n vertices when the queue empties, it is a topological order; fewer means a directed cycle, whose vertices each wait for their predecessor, never reach in-degree 0, and are never enqueued.

14.3.13Code trace: kahn()

Six courses have the arrows 0 → 3, 1 → 3, 1 → 4, 2 → 0, 2 → 4, 3 → 5, 4 → 5; the lists are 0: [3] · 1: [3, 4] · 2: [0, 4] · 3: [5] · 4: [5] · 5: [].

Counting. 0's list sets indeg[3] to 1; 1's raises indeg[3] to 2 and indeg[4] to 1; 2's raises indeg[0] to 1 and indeg[4] to 2; those of 3 and 4 raise indeg[5] to 2. The result is [1, 0, 0, 2, 2, 2], and 1 and 2 enter the queue.

Removing 1 lowers 3 and 4 but not to 0: 3 waits for 0, 4 for 2. Removing 2 readies 0 and 4; removing 0 readies 3. indeg[5] drops to 1 when 4 leaves and to 0 when 3 does.

The result 1 2 0 4 3 5 has size 6 = n: no cycle, and every arrow's source comes first (for 2 → 0, 2 is second, 0 third). One enqueue per vertex, one decrement per arrow: O(n + m).

DFS also sorts topologically: a vertex's call finishes after those of everything reachable from it, so reverse finishing order is a topological order, with cycles caught by the back-edge check of the next section.

14.3.14Detecting cycles in a directed graph

In an undirected graph, DFS meeting a marked neighbor other than its parent means a cycle. In a directed graph an arrow to a marked vertex is not enough: the vertex must lie on the current DFS path. Three colors tell the cases apart:

• white (0): not yet visited;
• gray (1): visited and on the current DFS path; its call has not finished;
• black (2): visited and finished; everything reachable from it has been examined.

// color: 0 white, 1 gray (on path), 2 black
boolean hasCycle(int v, int[] color) {
  color[v] = 1;
  for (int u : adj.get(v)) {
    if (color[u] == 1) return true;  // back edge
    if (color[u] == 0 && hasCycle(u, color))
      return true;
  }
  color[v] = 2;
  return false;
}

A gray head means the DFS path leads from it to the current vertex, and the arrow closes a cycle: a back edge. A black head has no path back, or the current vertex would have been visited during its call, so it closes no cycle.

Step 7 shows the subtlety: 3 → 2 leads to a visited vertex, and asking only “visited?” would report a false cycle, but 2 is black, with no path back to 3. In step 9, 0 is gray: 0 → 3 → 4 is still on the call stack, and 4 → 0 closes the cycle 0 → 3 → 4 → 0. true returns at once through every level.

The cost is that of DFS: each vertex turns gray and black once, each arrow is examined once. If some vertices are unreachable from 0, hasCycle restarts at each white one, still O(n + m).

14.4Shortest paths

A map app's route, a router's fastest packet path, a game character's way to its goal: one graph problem. Without weights, length is the edge count and BFS solves it; with weights, length is the weight sum and Dijkstra's algorithm solves it.

14.4.1The unweighted shortest-path problem

Without weights, each edge counts 1, and BFS solves the problem: a vertex on level k has distance exactly k.

Two three-edge paths reach 7: 1 → 4 → 6 → 7 and 1 → 3 → 8 → 7. BFS finds one, depending on list order, but the length is 3 either way: shortest paths need not be unique, shortest lengths are.

14.4.2Algorithm and code

dist[every v] = ∞
dist[s] = 0
queue.add(s)
while queue is not empty:
  w = queue.remove()
  for each neighbor u of w:
    if dist[u] == ∞:
      dist[u] = dist[w] + 1
      queue.add(u)
return dist

This is BFS with a distance array as the visited array, “distance = ∞” meaning “unvisited.” A newly discovered vertex gets its discoverer's distance plus one, which by Theorem 14.2 is final.

Map<Integer, Integer> shortestPath(int s) {
  final int INF = Integer.MAX_VALUE;  // ∞
  Map<Integer, Integer> dist =
      new HashMap<>();
  for (int v : graph.keySet())
    dist.put(v, INF);
  dist.put(s, 0);
  Queue<Integer> q = new ArrayDeque<>();
  q.offer(s);
  while (!q.isEmpty()) {
    int w = q.poll();
    for (int u : graph.get(w))
      if (dist.get(u) == INF) {
        dist.put(u, dist.get(w) + 1);
        q.offer(u);
      }
  }
  return dist;
}

Here the graph is a Map<Integer, List<Integer>> named graph, from vertex to neighbor list; vertices start at 1, hence a map rather than an array.

• INF stands for ∞ as Integer.MAX_VALUE.
• Every distance starts at INF; the source gets 0 and is enqueued (offer appends, like add).
• The main loop is BFS: each neighbor still at INF gets dist.get(w) + 1 and is enqueued.

The cost is BFS's, O(n + m), with HashMap operations O(1) on average.

14.4.3Code trace: shortestPath(1)

Let the source be 1 in the graph of Figure 14.28, with neighbor lists in increasing order: 1: [2, 3, 4] · 2: [1, 5] · 3: [1, 8] · 4: [1, 6] · 5: [2, 8] · 6: [4, 7] · 7: [6, 8] · 8: [3, 5, 7].

Three points stand out. When 2 leaves, neighbor 1 keeps distance 0: in BFS the first distance found is shortest. When 5 leaves, neighbor 8 already has 2; via 5 it would be 2 + 1 = 3, and the code does not even look, since 8 is no longer INF.

And 8, enqueued before 6, writes 7's distance, so the path found is 1 → 3 → 8 → 7; another list order might give 1 → 4 → 6 → 7, still 3. The final row matches Figure 14.28.

The code returns distances, not paths; for paths, store each vertex's discoverer in a prev array. Dijkstra does the same, and 14.4.8 traces rebuilding a path backward from the target.

14.4.4The weighted shortest-path problem

With weights the problem is the same, but length is the sum of edge weights: distances, times, or costs.

The solution is the algorithm Edsger W. Dijkstra devised in 1956 and published in 1959. It has one requirement: edge weights must not be negative, for reasons that emerge in its correctness proof (14.4.9).

14.4.5Dijkstra's algorithm: idea and pseudocode

Dijkstra's algorithm keeps a tentative distance for each vertex, the length of the shortest path found so far: 0 for the source, ∞ for the rest. Each step:

1. picks, among vertices not yet settled, the one with the smallest tentative distance, whose distance is now final;
2. updates its neighbors' distances by relaxation.

The name pictures an upper bound loosening like a spring. A tentative distance never drops below the true distance; each relaxation either leaves it alone or moves it closer.

Dijkstra(G, s):
  for each vertex v:
    dist[v] = ∞
    prev[v] = undefined
  dist[s] = 0
  Q = all vertices  // priority queue
  while Q is not empty:
    u = Q.removeMin()   // smallest dist[u]
    for each neighbor v of u in Q:
      alt = dist[u] + weight(u, v)
      if alt < dist[v]:
        dist[v] = alt
        prev[v] = u
        // decrease v's priority in Q

Q is a priority queue of unsettled vertices keyed by tentative distance; Q.removeMin() returns the closest. When relaxation lowers a distance, the vertex's priority must drop too. prev[] records each vertex's predecessor on its shortest path, and paths are read backward from it.

14.4.6Dijkstra in Java

long[] dijkstra(List<List<int[]>> adj, int s, int[] prev) { // weights ≥ 0
    long[] d = new long[adj.size()];
    Arrays.fill(d, Long.MAX_VALUE);  d[s] = 0;  Arrays.fill(prev, -1);
    PriorityQueue<long[]> pq =                     // {vertex, distance}
        new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
    pq.add(new long[]{s, 0});
    while (!pq.isEmpty()) {
        long[] e = pq.poll();  int u = (int) e[0];
        if (e[1] > d[u]) continue;                   // stale entry: skip
        for (int[] k : adj.get(u)) {
            int v = k[0];  long alt = d[u] + k[1];
            if (alt < d[v]) { d[v] = alt; prev[v] = u; pq.add(new long[]{v, alt}); }
        }
    }
    return d;
}

• Input. adj.get(u) lists u's neighbors as int[]{v, w} pairs, neighbor and weight. The caller allocates prev; dijkstra fills it.
• Setup. The long array d is filled with Long.MAX_VALUE, standing for ∞; d[s] = 0; prev is filled with −1, “no predecessor.”
• Queue. Entries are {vertex, distance} pairs; the comparator Long.compare(a[1], b[1]) orders by distance, so poll returns the closest.
• Stale check. if (e[1] > d[u]) continue; skips an entry whose distance exceeds the vertex's current one.
• Relaxation. For each neighbor, alt = d[u] + k[1]; if alt < d[v], the distance and prev are updated and a new {v, alt} entry is added.

Java's PriorityQueue has no decrease-key, so the code adds a new entry for v and leaves the old one. When the old entry surfaces, its distance exceeds the since-lowered d[v]: a stale entry, skipped by continue. This is lazy deletion: ignore old entries when they surface instead of removing them.

14.4.7Code trace: dijkstra(adj, A)

Give the nine-vertex traversal graph weights: A–B: 4, A–F: 7, A–I: 3, B–C: 1, B–E: 2, C–D: 7, C–E: 3, D–G: 3, D–H: 5, E–G: 2, F–G: 2. The graph is undirected, each edge in both lists, and the source is A.

Each row below is one poll. The queue column shows the entries left after that row's relaxations, sorted by distance.

The critical row is G's. D stands at 12, via C (A → B → C → D: 4 + 1 + 7). Settling G relaxes D–G to 8 + 3 = 11 < 12: D drops to 11, prev[D] = G, and {D, 11} joins the queue beside the old {D, 12}. {D, 11} surfaces first and settles D; {D, 12} follows, stale since 12 > 11, and is skipped.

Vertices settle in distance order, A (0), I (3), B (4), C (5), E (6), F (7), G (8), D (11), H (16), the property behind Dijkstra's correctness. There were 10 polls, 10 insertions (1 initial, 9 successful relaxations), and 22 relaxation attempts, 2m = 22.

prev holds the shortest-path tree: from H, H ← D ← G ← E ← B ← A, so A → B → E → G → D → H, five edges of length 4 + 2 + 2 + 3 + 5 = 16. The four-edge A → F → G → D → H has length 7 + 2 + 3 + 5 = 17.

14.4.8Reconstructing the path

To get the path from s to t, follow prev from t until −1. The chain runs backward, so each vertex goes to the front of the list.

List<Integer> path(int[] prev, int s, int t) {
  LinkedList<Integer> p = new LinkedList<>();
  for (int v = t; v != -1; v = prev[v])
    p.addFirst(v);
  if (p.getFirst() != s) return List.of();
  return p;                 // s ... t
}

Starting at v = t, each round prepends v and steps back with v = prev[v], stopping after the source, whose prev is −1. LinkedList.addFirst is constant time, so the cost is O(path length), at most O(n).

The final check catches unreachable targets: prev[t] = −1 stops the chain at once, leaving t first, and a first item other than s yields an empty list.

14.4.9Dijkstra: analysis and correctness

Time. Two implementations are common:

With a heap, each successful relaxation adds an entry, at most m + 1 in all, each insertion or removal O(log m). As m ≤ n², log m ≤ 2 log n, giving O((n + m) log n).

Sparse graphs (m ≈ n) favor the heap, O(n log n) against the array scan's O(n²); on very dense ones (m ≈ n²) the heap rises to O(n² log n) and the O(n²) scan can win.

Non-negativity is used once: “length ≥ 0.” A negative edge could later shorten a settled vertex's distance, and the pseudocode then errs. The stale-entry Java version may recover by reprocessing vertices, but loses its time bound, and a negative cycle makes it run forever. Negative weights call for the Bellman-Ford algorithm.

14.5Minimum spanning trees

A municipality wants water in every village; pipe between any two villages has a cost, and water need only reach each village by some route. Which network costs least? This minimum spanning tree problem also arises in power and communication networks, clustering, and inside other algorithms.

14.5.1Spanning trees and the MST

Why no cycles? With positive weights, dropping a cycle edge lowers the total while the rest of the cycle keeps its endpoints connected, so the cheapest connected subgraph is a tree. The n − 1 is the lower bound of 14.1.7, met exactly by acyclic connected graphs.

The edges weigh 62 in all; the MST takes nine of them, weighing 14. Spanning trees are far too many to try, so the classic algorithms, Kruskal's and Prim's, are greedy: each step takes the best-looking choice and never revisits it. Greed works here thanks to this property.

Kruskal and Prim apply this theorem in two ways. In Prim, one group is the tree built so far; in Kruskal, the groups are the trees containing the two endpoints of the chosen edge.

14.5.2Disjoint sets (Union-Find)

Kruskal tries edges from lightest to heaviest, asking of each whether it closes a cycle, that is, whether chosen edges already connect its endpoints. Disjoint sets (union-find) answer this quickly, managing non-overlapping sets with two operations:

• find(x) returns the representative of x's set; two items are in the same set exactly when find gives them the same representative.
• union(u, v) merges the sets of u and v and returns true if they differ; if they are already the same set, it does nothing and returns false.

The slides use only this behavior; the class below is an implementation that reproduces the parent arrows of their trace.

class UnionFind {
    private final int[] parent, size;
    UnionFind(int n) {                       // each vertex its own set
        parent = new int[n];  size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }
    int find(int x) {                        // find the root, compress the path
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    boolean union(int u, int v) {
        int a = find(u), b = find(v);
        if (a == b) return false;            // same set: would close a cycle
        if (size[a] > size[b]) { int t = a; a = b; b = t; }
        parent[a] = b;  size[b] += size[a];      // smaller tree under the larger
        return true;
    }
}

Each set is a tree: parent[x] is x's parent, and the root, its own parent, represents the set. Initially there are n one-vertex trees. Two refinements give speed:

• Union by size. The smaller tree's root goes under the larger's, keeping heights at most log n; on a tie, u's root goes under v's.
• Path compression. find links every vertex on its way directly to the root, so repeat queries take one step.

Together they make each operation cost O(α(n)) over a sequence, where α, the inverse Ackermann function, stays ≤ 4 even for n the number of atoms in the universe: in practice, constant time.

14.5.3Kruskal's algorithm

Kruskal(G):
  T = ∅          // chosen edges
  for each vertex v: makeSet(v)
  sort the edges by weight
  for each (u, v), lightest first:
    if find(u) != find(v): // no cycle
      T.add((u, v))
      union(u, v)
    if |T| == n − 1: break
  return T  // MST (if disconnected: forest)

Kruskal's rule: pick the lightest edge that closes no cycle. Starting from n one-vertex sets, it tries edges by increasing weight; an edge joining different sets enters T and merges them, one inside a set is skipped. After n − 1 edges the tree is done.

Midway, the chosen edges form a forest whose trees merge into one. A disconnected graph never reaches n − 1; every edge is tried, giving a minimum spanning forest, one tree per component.

Sorting dominates: as log m ≤ 2 log n, O(m log m) = O(m log n), and the nearly linear Union-Find work changes nothing. A DFS per edge for cycle checks would cost O(m · n).

14.5.4Kruskal step by step

We run Kruskal on the graph of Figure 14.34, trying equal-weight edges in the order of its caption.

C–J is rejected because C–I and I–J already connect C and J; it would close C–I–J–C. Likewise A–D, with A–E–D in place. Accepting B–C makes |T| = 9 = n − 1, total 0 + 1 + 1 + 1 + 1 + 2 + 2 + 2 + 4 = 14, and the other seven edges (C–H, G–I, A–B, D–F, H–I, F–G, D–G) are never examined.

14.5.5Code trace: kruskal() and Union-Find

List<int[]> kruskal(int n, List<int[]> E) {
  E.sort((a, b) ->          // {u, v, w}
      Integer.compare(a[2], b[2]));
  UnionFind uf = new UnionFind(n);
  List<int[]> T = new ArrayList<>();
  for (int[] e : E) {
    if (uf.union(e[0], e[1]))  // no cycle
      T.add(e);
    if (T.size() == n - 1) break;
  }
  return T;
}

Edges are {u, v, w} arrays, sorted by weight; Java's object sort is stable, so ties keep input order. uf.union(e[0], e[1]) checks and merges in one call, a true adding the edge; break ends the loop at |T| = n − 1.

Inside Union-Find, with A = 0, …, J = 9, the “linked” column shows which root union attaches to which.

For C–J, find(C) follows C → J and find(J) returns J: same root, false, skipped. In the last step find(B) follows B → D → E, path compression links B to E, and J's tree (3 vertices) goes under E's (7). The single root E is reached by I and C through J, by G through H.

Nine edges of weight 14 are returned; eleven of eighteen edges were tried, but sorting, the dominant cost, covers all eighteen.

14.5.6A second example: airports

Goodrich, Tamassia, and Goldwasser give nine U.S. airports and 19 routes, weighted in miles; we want the shortest network connecting them all.

The total is 144 + 184 + 187 + 337 + 621 + 802 + 946 + 1235 = 4456 miles. Thirteen routes are tried; the six longest (1258, 1391, 1464, 1846, 2342, 2704) never are. Short routes group nearby airports, and long ones enter only as bridges between groups: LAX–DFW, the shortest bridge between west and east, must be in the MST by the cut property.

14.5.7Prim's algorithm

Prim(G, s):
  tree = {s}, T = ∅
  add s's edges to the queue
  while |T| < n − 1:
    (u, v) = lightest edge  // u in tree
    if v in tree: skip       // cycle
    add v to tree, (u, v) to T
    add v's edges leaving the tree
      to the queue
  return T

Prim grows one tree from a single vertex, adding each step the lightest edge to a vertex outside it. The cut property makes this safe: the tree must connect to the rest somehow, and this is the cheapest connection.

Like Dijkstra, Prim starts at a vertex and repeatedly takes a priority queue's smallest item, but the key differs: Dijkstra's is the total distance from the source, Prim's the weight of the single edge to the tree. Unlike Kruskal, there is always one tree, so “is the head in the tree?” detects cycles without Union-Find.

14.5.8Prim in Java

The Java version in the slides is the lazy version, built on a priority queue.

List<int[]> prim(List<List<int[]>> adj, int s) {
  int n = adj.size();                 // adj.get(u): {v, w}
  boolean[] inTree = new boolean[n];
  PriorityQueue<int[]> pq = new PriorityQueue<>(
      (a, b) -> Integer.compare(a[2], b[2]));  // {u, v, w}
  List<int[]> T = new ArrayList<>();
  inTree[s] = true;
  for (int[] e : adj.get(s)) pq.add(new int[]{s, e[0], e[1]});
  while (!pq.isEmpty() && T.size() < n - 1) {
    int[] e = pq.poll();               // lightest candidate
    if (inTree[e[1]]) continue;       // stale: would close a cycle
    inTree[e[1]] = true;
    T.add(e);
    for (int[] f : adj.get(e[1]))
      if (!inTree[f[0]]) pq.add(new int[]{e[1], f[0], f[1]});
  }
  return T;
}

Entries are {u, v, w}: tree endpoint, candidate, weight (the comparator's only concern). inTree marks members.

1. The start s joins, and its edges are enqueued.
2. Until the queue empties or n − 1 edges are chosen, take the lightest entry.
3. If candidate e[1] is in the tree, the entry is stale (it would close a cycle), and continue skips it.
4. Otherwise the candidate joins, the edge enters T, and the new vertex's edges leaving the tree are enqueued.

“Lazy”: when v joins, old entries to it stay queued and are skipped on removal, as with Dijkstra's stale entries.

Cost. Each edge is enqueued at most once, from the endpoint that joins first; later, !inTree[f[0]] blocks it. At most m insertions and removals at O(log m) give O(m log n) time and O(m) queue memory. With a matrix and an array scan, Prim takes O(n²), better for very dense graphs.

14.5.9Prim step by step

Start Prim at A on Figure 14.34, breaking ties alphabetically by tree endpoint, then candidate.

When D joins in step 3, the entries A–D 4 and F–D 5 go stale but stay queued. In step 7, A–D leads the weight-4 entries alphabetically, is skipped as stale, and B–C is chosen. In step 9, J joins with n − 1 = 9 edges, leaving eight entries unexamined.

Prim's tree, A–E, E–F, E–D, D–B, D–H, H–G, B–C, C–I, I–J, has Kruskal's edges in another order: Kruskal began with I–J (weight 0), which Prim reaches last.

Alphabetical ties are a hand-tracing rule. The Java code takes tied entries in PriorityQueue's internal order, which guarantees nothing and depends on insertion order, hence on the lists. With alphabetical lists it picks G–I instead of B–C in step 7, then I–J and I–C: A–E, E–F, E–D, D–B, D–H, H–G, G–I, I–J, I–C. With edges listed in the order of the caption of Figure 14.34, it picks H–C in step 7. Each tree is an MST of weight 14: ties allow several MSTs, all of equal weight.

14.5.10Kruskal versus Prim

Both are greedy, rest on the cut property, and find the same total (14 here), though ties may yield different trees. The data's form also matters: edges read as a list suit Kruskal; adjacency lists with a natural start vertex suit Prim.

14.6Summary

• A graph G = (V, E) has n vertices and m edges. Unlike a tree, it has no root, may have cycles, and may offer several routes to a vertex. Edges may be directed or not, weighted or not.
• A vertex's degree counts its incident edges. By the handshake lemma Σ deg(v) = 2m; directed in- and out-degrees each sum to m. Simple undirected graphs have m ≤ n(n − 1)/2, connected ones m ≥ n − 1.
• A path is a sequence of vertices joined by edges; a cycle ends where it starts. A graph with paths between all vertex pairs is connected; a largest mutually reachable group is a connected component.
• An adjacency matrix takes O(n²) memory, with O(1) edge queries and O(n) neighbor visits; an adjacency list takes O(n + m), with O(deg v) neighbor visits. Lists suit sparse graphs; matrices suit dense ones with frequent edge queries.
• BFS goes level by level with a queue, DFS deepest first with a stack or recursion, both O(n + m) with lists. Vertices are marked on entering the queue or stack; without marks, cycles trap the traversal.
• Three applications follow. Connected components: a new traversal from each uncolored vertex. Bipartiteness: 2-coloring by BFS, possible exactly without odd cycles. Directed cycle detection: three-color DFS, where an arrow to a gray vertex is a back edge.
• Topological orders exist only for DAGs. Kahn's algorithm dequeues in-degree-0 vertices and deletes their arrows, in O(n + m); fewer than n results reveal a cycle.
• BFS finds unweighted shortest paths, the first distance found being shortest. For non-negative weights, Dijkstra settles the closest unsettled vertex and relaxes its neighbors, in O((n + m) log n) with a heap or O(n²) by array scan; paths are read backward through prev.
• A minimum spanning tree connects all vertices with n − 1 edges of least total weight. Kruskal sorts edges and keeps those closing no cycle, via Union-Find; Prim grows one tree by its lightest outgoing edge. Both are O(m log n) and rest on the cut property.

The table shows the chapter's lesson: the data structure shapes the algorithm. One traversal skeleton becomes BFS with a queue, DFS with a stack, Dijkstra with a priority queue keyed by distance, and Prim with one keyed by edge weight.

14.7Key terms

The glossary gives each term's Turkish equivalent and its use in other chapters.

• graph
• vertex, node
• edge
• adjacent
• degree
• in-degree
• out-degree
• directed graph (digraph)
• weighted graph
• path
• cycle
• connected component
• complete graph
• edge list
• adjacency list
• adjacency matrix
• traversal
• breadth-first search (BFS)
• depth-first search (DFS)
• bipartite graph
• directed acyclic graph (DAG)
• topological sort
• relaxation
• priority queue
• spanning tree
• minimum spanning tree (MST)
• disjoint sets (union-find)
• path compression
• Kruskal's algorithm
• Prim's algorithm

14.8Test Yourself

1. What are the fewest and the most edges a simple, undirected, connected graph on 8 vertices can have?

   Answer

   At least n − 1 = 7 (the graph is then a tree), at most n(n − 1)/2 = 8 · 7 / 2 = 28 (the complete graph K₈).

2. How many cells are 1 in the adjacency matrix of the directed graph with arrows 0 → 1, 0 → 2, 2 → 1, 3 → 0? How do you read 0's out-degree and 1's in-degree from the matrix?

   Answer

   Each arrow fills one cell: 4 cells. 0's out-degree is the sum of row 0, m[0][1] + m[0][2] = 2; 1's in-degree is the sum of column 1, m[0][1] + m[2][1] = 2.

3. On the nine-vertex traversal graph (neighbors alphabetical), what does bfs(E) print? How many edges is A from E?

   Answer

   E B C G A D F I H. E's neighbors B, C, G form level 1; A (from B), D (from C), and F (from G) form level 2; I (from A) and H (from D) form level 3. A is on level 2, two edges from E (E → B → A).

4. On the same graph, what does recursive dfs(F) print?

   Answer

   F A B C D G E H I. From F the search descends to A, then A's first unvisited neighbor B, then C, D, G, and G's neighbor E. It backs up from E and G and visits H below D; finally, back at A, it visits A's last neighbor, I.

5. What order does kahn() return for the DAG with lists 0: [1, 2] · 1: [4] · 2: [4] · 3: [1] · 4: []?

   Answer

   The in-degrees are [0, 2, 1, 0, 2], so the queue starts with 0, 3. Removing 0 gives indeg[1] = 1 and indeg[2] = 0, enqueuing 2; removing 3 gives indeg[1] = 0, enqueuing 1; removing 2 gives indeg[4] = 1; removing 1 gives indeg[4] = 0, enqueuing 4. The result is 0 3 2 1 4; its size is 5 = n, so there is no cycle.

6. On the graph with arrows 0 → 1, 1 → 2, 2 → 3, 3 → 1, while examining which arrow does hasCycle(0, color) return true? What is color at that moment?

   Answer

   0, 1, 2, 3 turn gray in turn: color = [1, 1, 1, 1]. When 3 → 1 is examined, 1 is gray, on the current path; the arrow is a back edge, and the cycle found is 1 → 2 → 3 → 1.

7. Run the Java Dijkstra from A on the undirected graph A–B 1, A–C 4, B–C 2, B–D 6, C–D 3. What are the final d and prev? How many stale entries leave the queue?

   Answer

   d = [0, 1, 3, 6] (A, B, C, D) and prev = [–, A, B, C]. Processing A sets C to 4 and B to 1; processing B lowers C to 3 (adding {C, 3}) and sets D to 7; processing C lowers D to 6 (adding {D, 6}). The old entries {C, 4} and {D, 7} come out stale and are skipped: 2 stale entries.

8. On the graph A–B 3, A–C 1, B–C 3, B–D 2, C–D 4, C–E 5, D–E 6, which edges does Kruskal choose, and what is the total weight? What changes if the tied edges A–B and B–C are tried in the other order?

   Answer

   In order: A–C 1 (accept), B–D 2 (accept), A–B 3 (accept, merging {A, C} and {B, D}), B–C 3 (reject), C–D 4 (reject), C–E 5 (accept). Four edges are chosen and D–E is never examined; the total is 1 + 2 + 3 + 5 = 11. Trying B–C first accepts B–C and rejects A–B: a different tree (A–C, B–D, B–C, C–E), still totaling 11.

9. On the graph of the previous question, in what order does lazy Prim from A choose edges (ties alphabetical), and how many stale entries does it skip?

   Answer

   A–C 1, A–B 3, B–D 2, C–E 5. After A–B is chosen, C–B 3 remains queued and is stale, since B is in the tree; when D joins, C–D 4 goes stale too. Both come out before C–E and are skipped: 2 stale entries. The total is again 11.

10. In a graph whose edges all weigh 5, which algorithm can replace Dijkstra for single-source shortest paths, and why?

    Answer

    BFS. With equal weights a path's length is 5 × number of edges, so the path with the fewest edges is also the shortest; multiply BFS's distances by 5. BFS runs in O(n + m), saving the log n factor of heap-based Dijkstra.

14.9Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Chapter 14: the graph ADT, representations, DFS and BFS, topological sorting, Dijkstra, Kruskal, and Prim, with Java code; the airport example comes from this chapter.
• R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Chapter 4: undirected and directed graphs, MSTs, and shortest paths in separate sections, with a comparison of the lazy and eager versions of Prim.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapters 20–22: formal correctness proofs for BFS and DFS, the cut property, and the Bellman-Ford algorithm; the analysis of disjoint sets is in Chapter 19.

14.10References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
2. E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, 1, 269–271, 1959.
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
4. A. B. Kahn, “Topological sorting of large networks,” Communications of the ACM, 5(11), 558–562, 1962.
5. J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings of the American Mathematical Society, 7(1), 48–50, 1956.
6. R. C. Prim, “Shortest connection networks and some generalizations,” Bell System Technical Journal, 36(6), 1389–1401, 1957.
7. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.

Related pages: Chapter 14 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.