Graph Structures and Fundamental Graph Algorithms

Introduction

Graphs provide a general model for relationships among entities. A communication network, road system, social network, dependency structure, recommendation system, and workflow can all be represented as graphs. In a graph, entities are represented by vertices and relationships by edges. Unlike linear structures such as arrays and linked lists, graphs express many-to-many relationships and may contain cycles, alternative routes, hierarchical dependencies, and disconnected regions.

This chapter develops the principal representations and algorithms used to process graphs. It covers graph traversal, topological ordering, strongly connected components, minimum spanning trees, and shortest paths. The emphasis is not only on implementation, but also on selecting an appropriate algorithm, proving correctness, and evaluating time and space complexity.

Learning Objectives

After studying this chapter, you should be able to:

1. Model directed, undirected, weighted, and unweighted networks.
2. Select and implement adjacency-list and adjacency-matrix representations.
3. Apply breadth-first search and depth-first search.
4. Explain cycle detection and topological sorting.
5. Compute strongly connected components in directed graphs.
6. Construct minimum spanning trees using Kruskal’s and Prim’s algorithms.
7. Select an appropriate shortest-path algorithm according to graph properties.
8. Justify algorithmic correctness and analyze complexity.
9. Evaluate practical limitations involving scale, negative weights, disconnected graphs, and changing networks.

1. Graph Foundations

A graph is written as G = (V, E), where V is a finite set of vertices and E is a set of edges. An edge may be represented as an unordered pair {u, v} in an undirected graph or an ordered pair (u, v) in a directed graph.

Important terminology includes:

• Order: the number of vertices, |V|.
• Size: the number of edges, |E|.
• Degree: the number of incident edges at a vertex in an undirected graph.
• Indegree: the number of incoming edges to a vertex.
• Outdegree: the number of outgoing edges from a vertex.
• Path: a sequence of vertices connected by edges.
• Simple path: a path containing no repeated vertex.
• Cycle: a closed path whose first and last vertices are identical.
• Connected graph: an undirected graph in which every pair of vertices has a path between them.
• Strongly connected graph: a directed graph in which every vertex can reach every other vertex.
• Component: a maximal connected subgraph.
• Weight: a numerical cost, distance, time, capacity, or preference assigned to an edge.

A graph is sparse when |E| is close to |V|, and dense when |E| is close to |V|². This distinction strongly influences representation choice.

1.1 Common Graph Classes

An undirected graph models reciprocal relationships, such as physical links. A directed graph models one-way relationships, such as hyperlinks or prerequisite dependencies. A weighted graph assigns values to edges; an unweighted graph treats every edge as having equal cost. A simple graph contains neither self-loops nor parallel edges, whereas a multigraph may contain multiple edges between the same pair of vertices.

A tree is a connected, undirected, acyclic graph. A tree with |V| vertices has exactly |V| − 1 edges. A forest is a collection of disjoint trees. A directed acyclic graph (DAG) is a directed graph containing no directed cycle.

2. Graph Representations

2.1 Adjacency Matrix

An adjacency matrix A is a |V| × |V| array. For an unweighted graph, A[u][v] is 1 when an edge exists and 0 otherwise. For a weighted graph, it stores the edge weight, while a special value such as infinity represents no edge.

The matrix requires Θ(V²) space and tests whether an edge exists in Θ(1) time. It is effective for dense graphs and algorithms that repeatedly inspect every possible pair of vertices. Its main disadvantage is the cost of scanning all |V| possible neighbors of a vertex, even when few edges exist.

2.2 Adjacency List

An adjacency list stores, for each vertex, a collection of its neighbors. For a directed weighted graph, each entry may contain a pair (neighbor, weight). The representation requires Θ(V+E) space and is usually the preferred representation for sparse graphs. Iterating over all neighbors takes time proportional to the degree of the vertex.

2.3 Edge List

An edge list stores edges as records such as (u, v, w). It is particularly useful for Kruskal’s algorithm and for algorithms that repeatedly process every edge. It supports compact storage but is inefficient for finding all neighbors of a specific vertex unless additional indexing is used.

3. Breadth-First and Depth-First Search

Graph traversal systematically visits reachable vertices. A visited structure is essential because graphs may contain cycles.

3.1 Breadth-First Search

Breadth-first search (BFS) explores vertices in layers according to their number of edges from a source. It uses a queue.

BFS(G, s):
    for each vertex v:
        visited[v] ← false
        distance[v] ← ∞
    visited[s] ← true
    distance[s] ← 0
    enqueue(Q, s)

    while Q is not empty:
        u ← dequeue(Q)
        for each neighbor v of u:
            if visited[v] = false:
                visited[v] ← true
                distance[v] ← distance[u] + 1
                parent[v] ← u
                enqueue(Q, v)

With adjacency lists, BFS runs in O(V+E) time and O(V) auxiliary space. It computes shortest paths measured by number of edges in an unweighted graph. It does not generally compute minimum-weight paths.

Correctness idea. When a vertex is removed from the queue, all vertices at smaller distance have already been processed. Every newly discovered vertex is reached through a path one edge longer than its parent’s path. Therefore, the first assigned distance is the minimum number of edges from the source.

3.2 Depth-First Search

Depth-first search (DFS) follows one path as deeply as possible before backtracking. It can be implemented recursively or with an explicit stack.

DFS(G):
    for each vertex u:
        visited[u] ← false
    for each vertex u:
        if visited[u] = false:
            DFS-VISIT(u)

DFS-VISIT(u):
    visited[u] ← true
    for each neighbor v of u:
        if visited[v] = false:
            parent[v] ← u
            DFS-VISIT(v)

DFS runs in O(V+E) time with adjacency lists. Recursive implementations require stack space proportional to the maximum depth; in production systems, an explicit stack may avoid recursion limits.

DFS supports cycle detection, topological sorting, connected-component discovery, articulation-point analysis, and strongly connected-component algorithms. In directed graphs, recording discovery and finishing times helps classify edges. An edge to a currently active ancestor is a back edge and proves the existence of a directed cycle.

4. Topological Sorting

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

4.1 Kahn’s Algorithm

Kahn’s algorithm repeatedly removes vertices with indegree zero.

TOPOLOGICAL-SORT(G):
    compute indegree[v] for every vertex v
    place all vertices with indegree 0 in queue Q
    ordering ← empty list

    while Q is not empty:
        u ← dequeue(Q)
        append u to ordering
        for each edge u → v:
            indegree[v] ← indegree[v] − 1
            if indegree[v] = 0:
                enqueue(Q, v)

    if length(ordering) ≠ |V|:
        report a directed cycle
    else:
        return ordering

The algorithm runs in O(V+E) time and uses O(V) additional space. If several zero-indegree vertices are available, different valid orderings may result. A priority queue can produce a deterministic order, at the cost of O((V+E) log V) time.

4.2 DFS-Based Ordering

A DFS-based method appends each vertex when its exploration finishes and then reverses the resulting list. This is valid only if no back edge is encountered. Both methods are useful: Kahn’s algorithm makes dependency availability explicit, while DFS integrates naturally with other depth-first analyses.

5. Strongly Connected Components

A strongly connected component (SCC) of a directed graph is a maximal set of vertices in which every vertex can reach every other vertex. SCCs condense naturally into a DAG: each component becomes one vertex, and edges between components are retained.

5.1 Kosaraju’s Algorithm

Kosaraju’s algorithm uses two DFS phases:

1. Run DFS on the original graph and record vertices by decreasing finishing time.
2. Reverse every edge.
3. Process vertices in the recorded order on the reversed graph. Each DFS tree is one SCC.

The running time is O(V+E) because each phase scans vertices and edges a constant number of times. The method is conceptually simple and works well with adjacency lists.

5.2 Tarjan’s Algorithm

Tarjan’s algorithm finds all SCCs in one DFS. It maintains discovery indices, low-link values, and a stack. The low-link value of a vertex records the smallest discovery index reachable from that vertex through DFS-tree edges followed by at most one back edge. When a vertex’s low-link value equals its discovery index, it is the root of an SCC.

Tarjan’s algorithm also runs in O(V+E) time and uses linear space. Its one-pass design is efficient, although its implementation requires careful stack and low-link management.

6. Minimum Spanning Trees

For a connected, weighted, undirected graph, a spanning tree connects every vertex without cycles. A minimum spanning tree (MST) is a spanning tree with minimum total edge weight. If T is a spanning tree, its weight is:

Here, w(e) is the weight of edge e. The formula assumes additive edge costs and an undirected graph. An MST is not a shortest-path tree: it minimizes total network connection cost, not the distance from one chosen source to every destination.

6.1 Kruskal’s Algorithm

Kruskal’s algorithm sorts all edges by nondecreasing weight and adds an edge whenever it joins two currently separate components. A disjoint-set union (DSU) structure supports this test using find and union operations.

KRUSKAL(G):
    T ← empty set
    make-set(v) for every vertex v
    sort edges by nondecreasing weight
    for each edge (u, v):
        if find(u) ≠ find(v):
            add (u, v) to T
            union(u, v)
    return T

Sorting dominates the running time: O(E log E). With path compression and union by rank, DSU operations are almost constant amortized time, formally O(α(V)), where α is the inverse Ackermann function. Kruskal’s algorithm can produce a minimum spanning forest when the graph is disconnected.

6.2 Prim’s Algorithm

Prim’s algorithm begins with one vertex and repeatedly adds the minimum-weight edge connecting the current tree to a vertex outside it. With a binary heap and adjacency lists, its complexity is O(E log V). With an adjacency matrix and a simple array, it is O(V²), which can be preferable for dense graphs.

Cut property. For any cut dividing the vertices into two sets, a minimum-weight edge crossing that cut is safe for some MST. Both Kruskal’s and Prim’s algorithms are justified by repeatedly applying this property. If edge weights are distinct, the MST is unique; with equal weights, multiple MSTs may exist, although their total weight is the same.

7. Shortest-Path Algorithms

A shortest-path problem seeks a path of minimum total weight. For a path P, its length is:

Weights must represent additive costs. The appropriate algorithm depends on whether the graph is weighted, whether negative edges exist, and whether one needs a single-source, single-pair, or all-pairs result.

7.1 Dijkstra’s Algorithm

Dijkstra’s algorithm solves the single-source shortest-path problem when all edge weights are nonnegative. It maintains a tentative distance and repeatedly selects the unsettled vertex with the smallest tentative value.

DIJKSTRA(G, s):
    dist[v] ← ∞ for every v
    dist[s] ← 0
    priority queue ← (0, s)

    while priority queue is not empty:
        (d, u) ← extract-min()
        if d ≠ dist[u]: continue
        for each edge u → v with weight w:
            if dist[u] + w < dist[v]:
                dist[v] ← dist[u] + w
                parent[v] ← u
                insert (dist[v], v)

With a binary heap and adjacency lists, the common implementation runs in O((V+E) log V), often written as O(E log V) for connected graphs. It is invalid when negative-weight edges are present because a vertex considered final may later be improved.

7.2 Bellman–Ford Algorithm

Bellman–Ford supports negative edge weights and detects reachable negative cycles. It relaxes every edge repeatedly for |V| − 1 passes. A final additional pass identifies an improvement, proving a reachable negative cycle.

Its complexity is O(VE). Although slower than Dijkstra’s algorithm, it is appropriate when negative costs represent rebates, credits, or currency-exchange effects. A negative cycle makes the shortest-path value undefined because the cycle can be repeated indefinitely to reduce total cost.

7.3 Floyd–Warshall Algorithm

Floyd–Warshall computes all-pairs shortest paths using dynamic programming. Let Dᵏ[i][j] be the shortest distance from i to j using only the first k intermediate vertices. The recurrence is:

The method assumes additive edge weights and permits negative edges, but not negative cycles. It runs in O(V³) time and O(V²) space. A negative diagonal entry after completion indicates a negative cycle.

7.4 Algorithm Selection

8. Worked Example: Network Design and Routing

Consider an undirected network with vertices A, B, C, D, and E and weighted links: AB = 2, AC = 5, BC = 1, BD = 4, CD = 2, CE = 3, and DE = 1.

8.1 Minimum Spanning Tree

Kruskal’s algorithm sorts the edges:

BC(1), DE(1), AB(2), CD(2), CE(3), BD(4), AC(5).

Add BC, then DE, then AB. At this point, {A, B, C} and {D, E} are separate. Add CD, which connects the two components. Four edges have been selected for five vertices, so the process stops. The MST is {BC, DE, AB, CD}, with total weight 1 + 1 + 2 + 2 = 6.

8.2 Shortest Paths from A

Using Dijkstra’s algorithm:

• Initial distances: A = 0; B = 2; C = 5; D = ∞; E = ∞.
• Settle B. Through B, C improves to 3 and D becomes 6.
• Settle C. Through C, D improves to 5 and E becomes 6.
• Settle D. Through D, E improves to 6, equal to its current value.
• Settle E.

Therefore, shortest distances from A are A = 0, B = 2, C = 3, D = 5, and E = 6. Notice that the MST and shortest-path tree are different objectives: the MST has total weight 6, while the shortest route from A to E has length 6 through A–B–C–E or A–B–C–D–E.

9. Applied Case: Cloud-Service Dependency and Network Planning

Background. A cloud platform contains services for authentication, billing, storage, analytics, and notification. Some services depend on others, while data centers are connected by links with installation costs and latency.

Problem. The engineering team must determine a safe deployment order, identify circular dependencies, design a low-cost redundant backbone, and route requests with minimum latency.

Analysis. Service dependencies are modeled as a directed graph. Kahn’s algorithm produces a deployment order if the graph is acyclic; failure to process all services identifies a dependency cycle requiring architectural review. SCC analysis groups mutually dependent services, revealing tightly coupled modules that may need to be deployed as a unit or refactored.

Data-center links form a weighted undirected graph. Kruskal’s algorithm produces a minimum-cost backbone, although operational requirements may require additional redundant links beyond the MST. Request routing uses Dijkstra’s algorithm when latency values are nonnegative. If the platform models credits or adjustments as negative weights, Bellman–Ford is required, together with explicit negative-cycle safeguards.

Outcome. The organization obtains four distinct analytical products: a valid deployment sequence, a set of dependency cycles or SCCs, a minimum-cost connecting backbone, and source-to-destination routes. These outputs should not be conflated: a dependency order is not a routing path, and an MST is not a set of minimum-delay routes.

Learning points. Correct modeling precedes algorithm selection. Network objectives must be stated precisely, and operational constraints such as resilience, capacity, security zones, and changing edge weights may require extensions beyond textbook algorithms.

10. Correctness, Complexity, and Engineering Practice

A proof of correctness should connect an algorithm’s invariant to its output. BFS maintains layer distances; Kahn’s algorithm maintains that every removed vertex has no remaining predecessor; Kruskal’s algorithm maintains an acyclic forest and uses safe crossing edges; Dijkstra’s algorithm relies on nonnegative weights to justify finalization.

Complexity should distinguish input representation from algorithmic logic. A matrix may make edge lookup constant time but force traversal to inspect V possible neighbors. A list reduces storage for sparse graphs but may require more work for direct edge queries. Space analysis should include auxiliary arrays, queues, stacks, priority queues, and recursion depth.

Best practices include validating vertex identifiers, explicitly handling disconnected graphs, documenting weight assumptions, detecting overflow in large distance calculations, using immutable edge records where possible, and testing empty, singleton, cyclic, disconnected, duplicate-edge, and negative-weight cases. For production systems, deterministic tie-breaking improves reproducibility, while instrumentation can expose unexpectedly dense regions or pathological degree distributions.

11. Limitations and Contemporary Directions

Classical graph algorithms assume a static graph and exact edge data. Real networks may evolve continuously, contain uncertain weights, or impose multiple constraints such as latency, cost, capacity, and reliability. An MST may be inadequate when resilience requires two or more independent paths. Dijkstra’s algorithm may be insufficient when travel times depend on departure time or congestion.

Large-scale systems use parallel graph processing, compressed sparse representations, external-memory algorithms, and incremental methods that update results after local changes. Graph databases provide query languages for traversals and pattern matching. Machine-learning systems use graph neural networks for prediction, but learned methods do not replace algorithmic guarantees: a model may estimate link risk, while a classical optimization algorithm enforces connectivity or resource constraints.

Graph analytics also raises governance concerns. Social and communication graphs may expose sensitive relationships. Access controls, anonymization, retention limits, and audit trails are necessary. Biased or incomplete graph data can produce unfair recommendations or discriminatory risk scores. Engineers must therefore document data provenance, uncertainty, and the consequences of algorithmic decisions.

Chapter Summary

Graphs model relationships among entities through vertices and edges. Adjacency lists are generally efficient for sparse graphs, while matrices suit dense graphs and constant-time edge tests. BFS explores by distance layers and solves unweighted shortest paths; DFS supports cycle detection, ordering, and structural analysis. Topological sorting applies only to DAGs, and SCC algorithms identify mutually reachable regions of directed graphs.

Kruskal’s and Prim’s algorithms construct minimum spanning trees for connected weighted undirected graphs, using the cut property for correctness. Dijkstra’s algorithm requires nonnegative edge weights, Bellman–Ford handles negative edges and detects reachable negative cycles, and Floyd–Warshall solves all-pairs problems in cubic time. Effective professional practice requires matching the algorithm to graph properties, proving relevant invariants, analyzing representation-dependent complexity, and addressing dynamic, ethical, and operational constraints.

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.

Adjacency matrix: A two-dimensional representation recording edge relationships.

Adjacency list: A representation listing each vertex’s neighbors.

Breadth-first search: A queue-based layer-by-layer traversal.

Depth-first search: A traversal that explores deeply before backtracking.

Topological ordering: A dependency-respecting linear order of a DAG.

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

Minimum spanning tree: A minimum-weight tree connecting all vertices of a connected undirected graph.

Disjoint-set union: A structure supporting dynamic component membership.

Shortest path: A minimum-weight route between vertices.

Relaxation: An operation that improves a tentative shortest-path distance.

Negative cycle: A cycle whose total weight is negative.

Sparse graph: A graph with relatively few edges.

Dense graph: A graph with a number of edges approaching the maximum possible.

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

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. Under what condition does a topological ordering exist?
4. What does a strongly connected component represent?
5. Why can Dijkstra’s algorithm fail with negative edge weights?

Long Answer Questions

1. Explain BFS and DFS, including their data structures, uses, and complexities.
2. Compare Kruskal’s and Prim’s algorithms in terms of strategy, data structures, and graph suitability.
3. Explain Kosaraju’s algorithm and justify its linear running time.
4. Compare Dijkstra, Bellman–Ford, and Floyd–Warshall for shortest-path problems.
5. Discuss how graph representation affects both memory consumption and algorithmic performance.

Analytical / Application Questions

1. Design an algorithmic workflow for deploying services represented by a dependency graph. Explain how cycles and SCCs should be handled.
2. A network contains negative edge weights but no known negative cycles. Select an appropriate shortest-path algorithm and justify your choice.
3. Explain why a minimum spanning tree should not automatically be used as the organization’s routing structure. Provide a network-planning example.

Multiple Choice Questions with Answers

Question 1

Which representation requires Θ(V²) space regardless of the number of edges?

A. Adjacency matrix

B. Adjacency list

C. Edge list

D. Disjoint-set forest

Correct Answer: A. Adjacency matrix

Question 2

Which algorithm computes shortest paths by number of edges in an unweighted graph?

A. Prim’s algorithm

B. Breadth-first search

C. Kruskal’s algorithm

D. Floyd–Warshall

Correct Answer: B. Breadth-first search

Question 3

A topological ordering exists exactly when a directed graph is:

A. Complete

B. Weighted

C. Acyclic

D. Undirected

Correct Answer: C. Acyclic

Question 4

What is the principal purpose of disjoint-set union in Kruskal’s algorithm?

A. To calculate indegrees

B. To detect whether an edge joins different components

C. To store shortest distances

D. To reverse graph edges

Correct Answer: B. To detect whether an edge joins different components

Question 5

Which condition is required by Dijkstra’s algorithm?

A. All edge weights are nonnegative

B. The graph must be acyclic

C. The graph must be complete

D. All vertices must have equal degree

Correct Answer: A. All edge weights are nonnegative

Question 6

For a graph with five vertices, how many edges does any spanning tree contain?

A. 4

B. 5

C. 10

D. 25

Correct Answer: A. 4

Question 7

Which algorithm can detect a reachable negative-weight cycle?

A. BFS

B. Prim’s algorithm

C. Bellman–Ford

D. Topological sorting only

Correct Answer: C. Bellman–Ford

Question 8

What is the standard adjacency-list complexity of BFS?

A. Θ(V²)

B. Θ(V + E)

C. Θ(E²)

D. Θ(log V)

Correct Answer: B. Θ(V + E)

Question 9

In the worked network, what was the total weight of the minimum spanning tree?

A. 4

B. 5

C. 6

D. 8

Correct Answer: C. 6

Question 10

Which algorithm is designed for all-pairs shortest paths with Θ(V³) time?

A. Floyd–Warshall

B. Kruskal

C. BFS

D. Prim

Correct Answer: A. Floyd–Warshall