Fundamental Graph Algorithms

Introduction

Graphs are mathematical structures for representing relationships among entities. In an AI and machine-learning system, vertices may represent users, documents, locations, states, or computational tasks, while edges may represent similarity, communication, dependency, distance, or probability. Graph algorithms provide systematic methods for exploring these relationships, detecting structure, optimizing routes, and supporting inference.

A graph is written as G = (V, E), where V is a finite set of vertices and E is a set of edges. For a directed graph, an edge is an ordered pair (u, v); for an undirected graph, {u, v} indicates a symmetric relationship. A weighted graph associates a numerical weight w(u, v) with each edge.

This chapter develops the principal graph algorithms used in algorithm design: graph representations, breadth-first search, depth-first search, topological sorting, connected components, strongly connected components, minimum spanning trees, and shortest-path algorithms. The emphasis is on correctness, complexity, design assumptions, and practical selection.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Model computational problems using directed, undirected, weighted, and unweighted graphs.
2. Select an appropriate graph representation and analyze its space requirements.
3. Apply BFS and DFS and explain their invariants.
4. Compute topological orderings and strongly connected components.
5. Construct minimum spanning trees using Kruskal’s and Prim’s algorithms.
6. Choose among Dijkstra’s, Bellman–Ford, Floyd–Warshall, and DAG shortest-path methods.
7. Prove or justify correctness using invariants, cut properties, and relaxation.
8. Evaluate graph algorithms for large-scale AI and engineering applications.

1. Graph Models and Terminology

The degree of a vertex in an undirected graph is the number of incident edges. In a directed graph, indegree counts incoming edges and outdegree counts outgoing edges. A path is a sequence of vertices connected by edges; its length is the number of edges in an unweighted graph or the sum of edge weights in a weighted graph. A cycle is a path that begins and ends at the same vertex without repeating internal vertices.

A graph is connected if every pair of vertices is joined by a path. A directed graph is strongly connected if every vertex is reachable from every other vertex. A tree is a connected, undirected, acyclic graph. A forest is a collection of trees. A spanning tree of a connected graph contains all vertices and exactly |V| − 1 edges.

For a weighted path P, its cost is:

Here, P is a path and w(u,v) is the weight of edge (u,v). The formula applies when path cost is additive. Negative edge weights are mathematically permitted, although they create restrictions for some algorithms.

A graph is sparse when |E| is close to |V|; it is dense when |E| is close to |V|². This distinction strongly affects representation and running time.

2. Graph Representations

Adjacency Matrix

An adjacency matrix A has |V| rows and columns. For an unweighted graph, A[u][v] is 1 when (u,v) exists and 0 otherwise. For a weighted graph, it stores the edge weight, with infinity representing no edge. Matrix storage requires Θ(|V|²) space and permits constant-time edge lookup. It is appropriate for dense graphs or algorithms based on matrix operations.

Adjacency List

An adjacency list stores, for each vertex, its neighboring vertices and, when necessary, edge weights. It requires Θ(|V| + |E|) space and supports efficient iteration over existing edges. It is generally preferred for sparse graphs.

Edge List

An edge list stores each edge as a record such as (u, v, w). It is compact and useful for sorting edges, as in Kruskal’s algorithm, but less efficient for finding all neighbors of a vertex.

In implementation, graph data structures should also account for parallel edges, self-loops, vertex identifiers, missing values, and numerical precision in weights.

3. Breadth-First Search

Breadth-first search (BFS) explores vertices in layers according to their distance from a source s. It uses a queue. When a vertex is first discovered, it is assigned a distance and its predecessor.

BFS(G, s)
    for each vertex u in V:
        color[u] ← WHITE
        distance[u] ← ∞
        predecessor[u] ← NIL
    color[s] ← GRAY
    distance[s] ← 0
    enqueue(Q, s)
    while Q is not empty:
        u ← dequeue(Q)
        for each v adjacent to u:
            if color[v] = WHITE:
                color[v] ← GRAY
                distance[v] ← distance[u] + 1
                predecessor[v] ← u
                enqueue(Q, v)
        color[u] ← BLACK

The key invariant is that when a vertex is removed from the queue, all vertices at smaller distance from s have already been processed. Therefore BFS computes shortest-path distances in an unweighted graph, where every edge has unit cost.

For an adjacency-list representation, BFS runs in Θ(|V| + |E|), because every vertex is enqueued at most once and every adjacency-list entry is examined at most once. Its auxiliary space is Θ(|V|).

BFS is used for reachability, shortest paths in unweighted networks, bipartite testing, level construction, and social-network search. A graph is bipartite if its vertices can be divided into two sets such that every edge joins different sets. BFS can test this by assigning alternating colors to adjacent vertices; a conflict indicates an odd cycle.

4. Depth-First Search

Depth-first search (DFS) explores one path as far as possible before backtracking. It may be implemented recursively or with an explicit stack. Each vertex receives a discovery time d[u] and finishing time f[u].

DFS(G)
    for each vertex u in V:
        color[u] ← WHITE
        predecessor[u] ← NIL
    time ← 0
    for each vertex u in V:
        if color[u] = WHITE:
            DFS-Visit(u)

DFS-Visit(u)
    color[u] ← GRAY
    time ← time + 1
    d[u] ← time
    for each v adjacent to u:
        if color[v] = WHITE:
            predecessor[v] ← u
            DFS-Visit(v)
    color[u] ← BLACK
    time ← time + 1
    f[u] ← time

DFS also runs in Θ(|V| + |E|) with adjacency lists. The parent pointers form a DFS forest. The parenthesis theorem states that for two vertices u and v, their discovery and finishing intervals are either disjoint or one contains the other. This property supports structural reasoning about reachability.

In a directed graph, an edge from a vertex to one of its ancestors in the DFS forest is a back edge and proves the presence of a cycle. Thus DFS can detect cycles. In an undirected graph, a cycle exists when an explored edge leads to a previously discovered vertex that is not the current vertex’s parent.

DFS is the foundation for topological sorting, articulation-point detection, bridge detection, and strongly connected components.

5. Topological Sorting

A topological ordering of a directed graph is a linear ordering of vertices such that for every edge (u, v), u appears before v. Such an ordering exists if and only if the graph is a directed acyclic graph (DAG).

One DFS method inserts a vertex at the front of a list when it finishes. If a back edge is detected, the graph contains a cycle and no topological ordering exists. An alternative is Kahn’s algorithm: repeatedly remove vertices of indegree zero and decrement the indegree of their successors.

For a DAG, shortest paths can be computed by processing vertices in topological order. Initialize d[s] = 0 and all other distances to infinity. For each vertex u in order, relax every outgoing edge:

The relaxation operation is valid when d[u] is already the shortest known distance to u. A DAG shortest-path algorithm runs in Θ(|V| + |E|), even when edge weights are negative, because a DAG cannot contain a negative cycle.

Typical applications include course prerequisites, build systems, project scheduling, and neural-computation pipelines.

6. Connected and Strongly Connected Components

In an undirected graph, a connected-component algorithm runs BFS or DFS from every unvisited vertex. Each search labels one component. The total complexity is Θ(|V| + |E|).

In a directed graph, a strongly connected component (SCC) is a maximal set of vertices with mutual reachability. Kosaraju’s algorithm performs DFS on G, records decreasing finishing times, reverses every edge, and performs DFS in that order. Each search and reversal is linear, so the total complexity is Θ(|V| + |E|).

Tarjan’s algorithm finds SCCs in one DFS using discovery indices, low-link values, and a stack. A vertex u is the root of an SCC when low[u] = index[u]. Tarjan’s method also runs in Θ(|V| + |E|) and is often attractive when avoiding an explicit transposed graph.

SCC condensation compresses each SCC into a single vertex. The resulting condensation graph is always a DAG, which is useful for dependency analysis and recursive state-space reduction.

7. Minimum Spanning Trees

For a connected, undirected, weighted graph, a minimum spanning tree (MST) is a spanning tree with minimum total edge weight:

The standard MST theory assumes an undirected graph and additive edge weights. Negative weights are allowed, but the graph must remain connected if a spanning tree over all vertices is required.

Cut Property

For any cut dividing the vertices into two sets, a light edge crossing the cut belongs to at least one MST. If the lightest crossing edge is unique, it belongs to every MST. This cut property justifies greedy algorithms.

Kruskal’s Algorithm

Kruskal’s algorithm sorts all edges by nondecreasing weight and repeatedly adds the next edge that joins two different components. A disjoint-set union structure supports find and union operations. With path compression and union by rank, the total time is O(|E| log |V|), dominated by sorting; more precisely, sorting costs O(|E| log |E|), which is O(|E| log |V|) for simple graphs.

Prim’s Algorithm

Prim’s algorithm grows one tree from an initial vertex. At each step it selects the minimum-weight edge connecting the current tree to a vertex outside it. With adjacency lists and a binary heap, the complexity is O(|E| log |V|). With a Fibonacci heap, the theoretical bound is O(|E| + |V| log |V|), although practical constants and implementation complexity may favor binary heaps.

Kruskal is often convenient for edge-oriented data and naturally produces a forest during execution. Prim is often effective when adjacency access is efficient and a connected graph is given.

8. Shortest-Path Algorithms

The single-source shortest-path problem seeks the minimum distance from source s to every reachable vertex. The algorithms differ mainly in graph structure and edge-weight assumptions.

Relaxation

For an edge (u, v), relaxation tests whether reaching v through u improves its current estimate:

Here d[x] is an upper-bound estimate of the shortest distance from s to x. The operation is meaningful when d[u] is finite. Predecessor pointers reconstruct paths.

Dijkstra’s Algorithm

Dijkstra’s algorithm repeatedly selects the unsettled vertex with minimum tentative distance and relaxes its outgoing edges. It is correct when every edge weight is nonnegative. With a binary heap and adjacency lists, its complexity is O((|V| + |E|) log |V|), commonly written O(|E| log |V|) for connected graphs.

The nonnegative-weight condition is essential: once a vertex is selected, a later path cannot improve it only because all remaining edge extensions add nonnegative cost. Negative edges invalidate this argument.

Bellman–Ford Algorithm

Bellman–Ford relaxes every edge |V| − 1 times. After these passes, it performs one additional pass; if an edge can still be relaxed, a reachable negative-weight cycle exists. Its complexity is O(|V||E|), but it supports negative edges and detects reachable negative cycles.

Floyd–Warshall Algorithm

Floyd–Warshall solves all-pairs shortest paths using dynamic programming. Let D⁽ᵏ⁾[i][j] be the shortest distance from i to j using only vertices 1 through k as internal vertices. The recurrence is:

It requires Θ(|V|³) time and Θ(|V|²) space. It tolerates negative edges but not negative cycles for meaningful finite shortest paths. A negative cycle can be identified when some diagonal entry D[i][i] becomes negative.

9. Correctness and Algorithm Selection

Graph algorithms should be selected from explicit assumptions rather than superficial similarity. A useful decision process is:

1. Is the graph directed or undirected?
2. Is the task reachability, ordering, connectivity, spanning, or shortest path?
3. Are weights absent, nonnegative, negative, or possibly cyclically negative?
4. Is the graph sparse or dense?
5. Is the required output single-source, single-pair, or all-pairs?
6. Are dynamic updates, parallel execution, or distributed storage required?

Correctness arguments commonly use invariants. BFS maintains the fact that assigned distances are shortest unweighted distances. Dijkstra maintains that settled distances are final under nonnegative weights. Kruskal relies on the cut property and cycle avoidance. Dynamic-programming algorithms use a recurrence whose subproblems cover all feasible solutions.

10. Worked Example: Choosing a Shortest-Path Method

Consider a road-like directed network with five vertices and edges:

A→B with weight 4, A→C with weight 2, C→B with weight 1, B→D with weight 2, C→D with weight 5, and D→E with weight 1.

All weights are nonnegative, so Dijkstra’s algorithm applies. Initialize d(A)=0 and all other estimates as infinity. After processing A, d(B)=4 and d(C)=2. Processing C improves d(B) to 3 and sets d(D)=7. Processing B improves d(D) to 5. Processing D sets d(E)=6. Thus the shortest distance from A to E is 6, along A→C→B→D→E.

The predecessor chain reconstructs the route. Notice that choosing the locally cheapest outgoing edge from A alone would be insufficient: A→C is cheaper than A→B, but the algorithm must compare complete tentative routes.

11. Applied Case: Dependency Analysis in an ML Pipeline

Background

This illustrative case concerns a machine-learning platform in which data ingestion, cleaning, feature generation, model training, validation, and deployment are represented as tasks.

Problem

Some tasks can run in parallel, but a task must not begin until all prerequisites are complete. The platform must detect circular dependencies, schedule tasks, and identify independent groups of services.

Analysis

Represent each task as a vertex and each prerequisite as a directed edge. A directed cycle indicates an impossible schedule. A topological sort produces a legal execution order when the graph is acyclic. If the system contains several disconnected workflows, connected-component analysis on an undirected representation identifies independent groups. For service-call dependencies, SCC analysis detects mutually recursive service clusters.

Approach and Solution

Kahn’s algorithm maintains indegrees. Tasks with indegree zero are placed in a queue and may execute immediately. When a task is removed, the indegrees of its successors are reduced. If fewer than |V| tasks are removed, a cycle exists. Complexity is Θ(|V| + |E|), making the approach suitable for large sparse pipelines.

If tasks also have execution durations, a longest-path computation on the DAG identifies the critical path. Unlike ordinary shortest paths, longest paths are generally difficult in arbitrary graphs, but they are tractable in DAGs by dynamic programming.

Outcome

The platform obtains a valid schedule, parallelizable task levels, and an early warning for cyclic configuration. The graph model also supports impact analysis: descendants of a changed preprocessing task are candidates for recomputation.

Learning Points

The case demonstrates that graph representation is not merely a coding choice. The meaning of edge direction determines whether topological order, reachability, SCCs, or critical-path analysis answers the operational question. It also shows why explicit assumptions—acyclicity, sparsity, and dependency semantics—must precede algorithm selection.

12. Limitations, Engineering Issues, and Contemporary Directions

Large graphs create challenges beyond asymptotic complexity. Memory locality can dominate running time; adjacency lists may cause irregular access patterns, while matrices can exploit vectorized hardware for dense graphs. Recursive DFS may overflow the call stack, requiring iterative implementations. Parallel graph traversal faces synchronization, load imbalance, and duplicate work.

Real data may contain noisy edges, missing vertices, duplicate records, temporal changes, and uncertain weights. In AI systems, graph construction can encode bias: a recommendation graph based on historical interactions may reproduce unequal exposure. Sensitive relationship graphs require access control, data minimization, and careful anonymization because graph structure itself can reveal identities.

Dynamic graphs require incremental maintenance rather than recomputation after every update. Distributed graph-processing systems partition vertices and edges across machines, but cross-partition communication can become the main cost. GPU implementations are effective for some frontier-based operations such as BFS, although irregular workloads reduce utilization.

Best practice is to document vertex and edge semantics, validate weights and directionality, select representations using measured density and workload, test disconnected and cyclic inputs, detect numerical anomalies, and report complexity under the actual data model. For safety-critical or high-impact applications, algorithmic output should be auditable and subject to domain review.

Chapter Summary

Graphs model entities and relationships through vertices and edges. Adjacency matrices provide constant-time edge lookup at quadratic space cost, whereas adjacency lists are efficient for sparse graphs. BFS explores in layers and computes shortest paths in unweighted graphs. DFS supports cycle detection, topological sorting, component analysis, and structural decompositions.

Topological ordering exists exactly for DAGs. Connected components and SCCs reveal the organization of undirected and directed networks. Kruskal’s and Prim’s algorithms construct minimum spanning trees using greedy cut-based reasoning. Relaxation is the central operation in shortest-path algorithms: BFS handles unit costs, DAG methods handle arbitrary weights in acyclic graphs, Dijkstra requires nonnegative weights, Bellman–Ford permits negative edges and detects reachable negative cycles, and Floyd–Warshall solves all-pairs problems in cubic time.

Effective graph-algorithm design depends on matching the problem’s semantics and assumptions to the algorithm. In professional AI and data systems, correctness, scalability, privacy, bias, dynamic updates, and implementation behavior are as important as asymptotic bounds.

Key Terms

Graph: A structure consisting of vertices and edges.

Vertex: An entity or node in a graph.

Edge: A relationship connecting two vertices.

Directed graph: A graph whose edges have orientation.

Weighted graph: A graph whose edges carry numerical values.

Path: A sequence of connected vertices.

Cycle: A closed path with repeated start and end vertices.

Degree: Number of incident edges at a vertex.

BFS: Layer-oriented graph traversal using a queue.

DFS: Depth-oriented graph traversal using recursion or a stack.

Topological ordering: An ordering respecting every directed dependency edge.

DAG: Directed acyclic graph.

Connected component: A maximal connected subgraph in an undirected graph.

Strongly connected component: A maximal mutually reachable subgraph of a directed graph.

Spanning tree: A tree containing every vertex of a connected graph.

Minimum spanning tree: A spanning tree of minimum total edge weight.

Relaxation: Updating a distance estimate when a shorter route is found.

Cut property: The lightest edge crossing a cut is safe for an MST.

Negative cycle: A cycle whose total edge weight is negative.

Review Questions

Short Answer Questions

1. What is the principal difference between an adjacency matrix and an adjacency list?
2. Why does BFS compute shortest paths in an unweighted graph?
3. State the condition under which a directed graph has a topological ordering.
4. What is the purpose of relaxation in shortest-path algorithms?
5. Why can Dijkstra’s algorithm fail when negative edges are present?

Long Answer Questions

1. Explain BFS and DFS, including their data structures, invariants, applications, and complexities.
2. Compare Kruskal’s and Prim’s algorithms and justify their correctness using the cut property.
3. Explain SCCs and compare Kosaraju’s and Tarjan’s algorithms.
4. Compare Dijkstra, Bellman–Ford, DAG shortest paths, and Floyd–Warshall with respect to assumptions and complexity.
5. Discuss graph representations and algorithm-engineering issues for large AI data systems.

Analytical / Application Questions

1. A dependency graph contains 12,000 tasks and 40,000 directed edges. Design an algorithm to test whether it can be scheduled and explain its complexity.
2. A transport graph has nonnegative weights and 2 million edges but only one source. Which shortest-path algorithm would you select, and what implementation choices would you consider?
3. A directed communication network contains several mutually recursive services. Explain how SCC condensation could support fault isolation and dependency analysis.

Multiple Choice Questions with Answers

Question 1

Which representation usually requires Θ(|V| + |E|) space?

A. Adjacency matrix

B. Adjacency list

C. Distance matrix

D. Incidence table containing every vertex pair

Correct Answer: B. Adjacency list

Question 2

What data structure is fundamental to standard BFS?

A. Stack

B. Priority queue

C. Queue

D. Disjoint-set forest

Correct Answer: C. Queue

Question 3

A topological ordering exists precisely when a directed graph is what?

A. Complete

B. Acyclic

C. Undirected

D. Weighted

Correct Answer: B. Acyclic

Question 4

Which algorithm is appropriate for shortest paths in a graph with nonnegative edge weights?

A. Dijkstra’s algorithm

B. Kruskal’s algorithm

C. Kosaraju’s algorithm

D. Floyd’s cycle algorithm

Correct Answer: A. Dijkstra’s algorithm

Question 5

What does a reachable negative cycle imply for shortest-path computation?

A. Every path has the same cost

B. No finite minimum distance exists for affected vertices

C. The graph must be disconnected

D. BFS becomes optimal

Correct Answer: B. No finite minimum distance exists for affected vertices

Question 6

For adjacency lists, the usual running time of BFS is:

A. Θ(|V|²)

B. Θ(log |V|)

C. Θ(|V| + |E|)

D. Θ(|E|²)

Correct Answer: C. Θ(|V| + |E|)

Question 7

Which algorithm constructs an MST by sorting edges and using disjoint sets?

A. Prim’s

B. Bellman–Ford

C. Kruskal’s

D. Floyd–Warshall

Correct Answer: C. Kruskal’s

Question 8

What is the central operation used by Dijkstra and Bellman–Ford?

A. Hashing

B. Relaxation

C. Topological reversal

D. Matrix inversion

Correct Answer: B. Relaxation

Question 9

What is the time complexity of Floyd–Warshall for |V| vertices?

A. Θ(|V|)

B. Θ(|E|)

C. Θ(|V| log |V|)

D. Θ(|V|³)

Correct Answer: D. Θ(|V|³)

Question 10

In the illustrative shortest-path example, what is the shortest distance from A to E?

A. 4

B. 5

C. 6

D. 7

Correct Answer: C. 6