Graphs and Network Algorithms

Introduction

Graphs are mathematical and computational models for relationships. A road map, a social network, a computer network, a course prerequisite system, and a dependency graph in a software build can all be represented as graphs. Unlike linear structures such as arrays, stacks, and linked lists, graphs allow one element to connect to many others in arbitrary patterns.

A graph is written as G = (V, E), where V is a set of vertices (also called nodes) and E is a set of edges. In a directed graph, an edge has an orientation, such as u → v. In an undirected graph, the connection is symmetric: {u, v} means that u is connected to v and v is connected to u. A weighted graph associates a value, such as distance, cost, or time, with each edge.

This chapter develops practical representations and algorithms for graph traversal, ordering, path finding, cycle detection, minimum spanning trees, and connected-component management. The algorithms are presented in language-independent pseudocode and illustrated with Java and Python techniques.

Learning Objectives

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

1. Distinguish directed, undirected, weighted, unweighted, cyclic, and acyclic graphs.
2. Select and implement adjacency lists or adjacency matrices appropriately.
3. Perform breadth-first search (BFS) and depth-first search (DFS).
4. Detect cycles in directed and undirected graphs.
5. Produce a topological ordering of a directed acyclic graph.
6. Compute shortest paths using BFS, Dijkstra’s algorithm, and Bellman–Ford where appropriate.
7. Construct a minimum spanning tree using Kruskal’s or Prim’s algorithm.
8. Implement disjoint-set union (DSU) with path compression and union by rank or size.
9. Evaluate algorithmic complexity and select an algorithm suitable for a practical problem.

1. Fundamental Graph Concepts

Important terminology includes:

• Vertex: An entity represented in the graph.
• Edge: A relationship between two vertices.
• Degree: In an undirected graph, the number of incident edges. In a directed graph, indegree counts incoming edges and outdegree counts outgoing edges.
• Path: A sequence of vertices connected by edges.
• Walk: A sequence that may repeat vertices or edges.
• Cycle: A path that begins and ends at the same vertex, usually with no repeated internal vertex.
• Connected graph: An undirected graph in which every pair of vertices has a path between them.
• Component: A maximal connected subgraph.
• Dense graph: A graph containing relatively many edges.
• Sparse graph: A graph containing relatively few edges.
• DAG: A directed acyclic graph.

For a simple undirected graph with n vertices, the maximum number of edges is n(n − 1)/2. For a simple directed graph without self-loops, the maximum is n(n − 1). These are structural bounds, not requirements for a graph to be useful.

A tree is a connected, undirected, acyclic graph. A tree with n vertices has exactly n − 1 edges. A spanning tree of a connected graph includes every vertex and has n − 1 edges. A minimum spanning tree (MST) is a spanning tree whose total edge weight is minimum.

2. Graph Representations

2.1 Adjacency list

An adjacency list stores, for each vertex, the vertices directly reachable from it. For a weighted graph, each entry stores a neighbour and a weight.

For example, edges A → B, A → C, and B → D may be stored as:

A: (B, 4), (C, 2)
B: (D, 7)
C:
D:

An adjacency list requires Θ(V + E) space and is normally the best representation for sparse graphs. Iterating through all neighbours takes time proportional to the degree of the selected vertex.

Python representation:

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 7)],
    'C': [],
    'D': []
}

Java representation using records (Java 16 or later):

record Edge(int to, int weight) {}
List<List<Edge>> graph = new ArrayList<>();

2.2 Adjacency matrix

An adjacency matrix is a V × V table. Entry matrix[u][v] indicates whether an edge exists or stores its weight. It provides constant-time edge lookup, Θ(1), but requires Θ(V²) space. It is suitable for dense graphs or applications that frequently test whether a particular edge exists.

For weighted graphs, a value such as infinity can represent the absence of an edge. Care is required: infinity must not be added to another value without checking for it, and zero-weight edges must not be confused with missing edges.

2.3 Edge list

An edge list stores edges as records such as (u, v, w). It is especially convenient for Kruskal’s algorithm and Bellman–Ford. Its space requirement is Θ(E), apart from storage for vertex identifiers.

2.4 Choosing a representation

For undirected graphs, each edge should normally be inserted in both adjacency lists. For directed graphs, it is inserted only in the list of its source vertex.

3. Breadth-First Search

Breadth-first search explores a graph in layers. It first visits the source, then all vertices at distance one edge, then all vertices at distance two edges, and so on. A queue controls the order.

BFS(G, source):
    mark source visited
    distance[source] = 0
    enqueue source
    while queue is not empty:
        u = dequeue
        for each neighbour v of u:
            if v is not visited:
                mark v visited
                distance[v] = distance[u] + 1
                predecessor[v] = u
                enqueue v

BFS runs in Θ(V + E) with an adjacency list. Each vertex is enqueued at most once and each adjacency-list entry is examined at most once. In an unweighted graph, the first distance assigned to a vertex is the minimum number of edges from the source, because vertices are processed in nondecreasing distance order.

Python implementation:

from collections import deque

def bfs(graph, start):
    distance = {v: None for v in graph}
    parent = {v: None for v in graph}
    distance[start] = 0
    q = deque([start])

    while q:
        u = q.popleft()
        for v in graph[u]:
            if distance[v] is None:
                distance[v] = distance[u] + 1
                parent[v] = u
                q.append(v)
    return distance, parent

BFS applications include shortest paths in unweighted networks, broadcasting, level-order exploration, bipartite testing, and finding connected components. To process a disconnected graph, run BFS from every unvisited vertex.

4. Depth-First Search

Depth-first search explores one branch as far as possible before backtracking. It can be implemented recursively or with an explicit stack.

DFS(u):
    mark u visited
    for each neighbour v of u:
        if v is not visited:
            predecessor[v] = u
            DFS(v)

With adjacency lists, DFS runs in Θ(V + E). Recursive DFS is conceptually simple, but a very deep graph may exceed a language’s call-stack limit. An explicit stack avoids that risk.

DFS supports connected-component discovery, cycle detection, topological sorting, reachability, strongly connected-component algorithms, and maze-like search. A useful classification in directed DFS is:

• A tree edge reaches an unvisited vertex.
• A back edge points to an active ancestor and indicates a directed cycle.
• A forward edge goes to a descendant that is not a tree edge.
• A cross edge connects unrelated DFS branches.

A three-state representation—0 for unvisited, 1 for active, and 2 for finished—makes directed cycle detection reliable. Encountering an edge to a state-1 vertex proves a cycle.

5. Topological Sorting

A topological ordering of a directed graph is a sequence in which every edge u → v places u before v. Such an ordering exists if and only if the graph is a DAG.

One method is Kahn’s algorithm:

1. Compute the indegree of every vertex.
2. Insert all zero-indegree vertices into a queue.
3. Remove one vertex, append it to the ordering, and reduce the indegree of its outgoing neighbours.
4. Insert any neighbour whose indegree becomes zero.
5. If fewer than V vertices are output, the graph contains a cycle.

def topological_sort(graph):
    indegree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    from collections import deque
    q = deque([u for u in graph if indegree[u] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)

    if len(order) != len(graph):
        raise ValueError("graph contains a cycle")
    return order

The time complexity is Θ(V + E), and the additional space is Θ(V). Topological ordering is used for course prerequisites, package installation, task scheduling, and compilation dependencies. If several vertices have indegree zero, more than one valid ordering may exist.

6. Shortest-Path Algorithms

A shortest path minimizes the sum of edge weights along a path. Let d[v] represent the currently known distance from a source s to vertex v. The relaxation operation tests whether reaching v through u is better:

if d[v] > d[u] + w(u, v):
    d[v] = d[u] + w(u, v)
    predecessor[v] = u

This assumes that d[u] is finite and that the edge weight is represented consistently.

6.1 BFS for unweighted graphs

When every edge has equal cost, BFS gives shortest paths measured in number of edges. It must not be used for arbitrary positive weights because a path with fewer edges may have a larger total weight.

6.2 Dijkstra’s algorithm

Dijkstra’s algorithm repeatedly selects the unsettled vertex with the smallest tentative distance and relaxes its outgoing edges. With a binary heap and adjacency lists, its typical complexity is O((V + E) log V), often written O(E log V) for connected graphs. With an array-based implementation, it is O(V²).

The essential condition is that all edge weights are nonnegative. Dijkstra’s greedy choice is not valid when negative edges exist.

import heapq

def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph}
    parent = {v: None for v in graph}
    dist[source] = 0
    heap = [(0, source)]

    while heap:
        d, u = heapq.heappop(heap)
        if d != dist[u]:
            continue
        for v, w in graph[u]:
            if w < 0:
                raise ValueError("Dijkstra requires nonnegative weights")
            candidate = d + w
            if candidate < dist[v]:
                dist[v] = candidate
                parent[v] = u
                heapq.heappush(heap, (candidate, v))
    return dist, parent

6.3 Bellman–Ford

Bellman–Ford relaxes every edge repeatedly, up to V − 1 times. A shortest simple path contains at most V − 1 edges, so further improvement after these passes indicates a reachable negative-weight cycle. Its complexity is O(VE), but it supports negative edge weights and can detect such cycles.

6.4 All-pairs shortest paths

Floyd–Warshall computes shortest distances between every pair in O(V³) time and O(V²) space. It is useful for relatively small, dense graphs. Its update rule is:

Here D[i][j] is the best known distance from i to j while allowing intermediate vertices from a selected set, and k is the newly permitted intermediate vertex. The method permits negative edges but not negative cycles for meaningful finite shortest distances.

7. Minimum Spanning Trees

An MST applies to a connected, undirected, weighted graph. It connects all vertices without cycles and minimizes the sum of selected edge weights. An MST is not a shortest-path tree: an MST minimizes total network connection cost, whereas a shortest-path tree minimizes distances from a specified source.

7.1 Kruskal’s algorithm

Kruskal’s algorithm sorts all edges by nondecreasing weight and adds an edge when it connects two currently different components. A DSU structure makes this test efficient.

sort edges by weight
create one DSU set for each vertex
for each edge (u, v, w):
    if FIND(u) != FIND(v):
        add edge to MST
        UNION(u, v)

Sorting dominates the complexity: O(E log E). The DSU operations are almost constant amortized time, formally O(α(V)) each, where α is the extremely slowly growing inverse Ackermann function.

7.2 Prim’s algorithm

Prim’s algorithm grows one tree. It begins with any vertex and repeatedly adds the minimum-weight edge joining the current tree to an outside vertex. With an adjacency list and binary heap, the complexity is O(E log V). Prim is often convenient when the graph is already represented by adjacency lists.

Both algorithms are greedy. Their correctness follows from the cut property: for any cut separating vertices into two groups, a lightest edge crossing that cut is safe to include in some MST. If edge weights are distinct, the MST is unique; with equal weights, multiple MSTs may exist, although their minimum total weight is the same.

8. Disjoint-Set Union

Disjoint-set union maintains a partition of elements into nonoverlapping sets. It supports:

• MAKE-SET(x): create a singleton set;
• FIND(x): return the representative of x’s set;
• UNION(x, y): merge the sets containing x and y.

A forest representation stores a parent pointer for each element. Path compression makes nodes point directly to the representative during FIND. Union by rank or union by size attaches the smaller tree beneath the larger one.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

DSU is useful for Kruskal’s algorithm, dynamic connectivity, clustering, and detecting cycles in undirected edge streams.

9. Cycle Detection

For an undirected graph, DFS can track the parent of each vertex. If an already visited neighbour is not the current vertex’s parent, a cycle exists. Alternatively, process edges with DSU: if an edge joins two vertices already in the same set, it creates a cycle.

For a directed graph, use DFS states. An edge from an active vertex to another active vertex is a back edge and proves a directed cycle. Kahn’s topological algorithm provides another test: failure to remove all vertices means that a cycle exists.

Self-loops are cycles in both directed and undirected interpretations. Parallel edges require careful treatment: two parallel edges between the same undirected vertices form a cycle under the usual multigraph definition, although some simple-graph implementations disallow them.

10. Worked Application: Delivery Network Design

Illustrative case. A delivery company has five depots: A, B, C, D, and E. Possible undirected links have costs:

Problem

The company wants a minimum-cost infrastructure connecting every depot. It also wants the least-cost route from A to E after the infrastructure is built.

Kruskal analysis

Sort the edges: B–C (1), A–C (2), D–E (2), A–B (4), B–D (5), B–E (7), C–D (8), C–E (10).

• Add B–C: no cycle.
• Add A–C: no cycle; A, B, C are connected.
• Add D–E: no cycle.
• A–B would create a cycle among A, B, and C, so reject it.
• Add B–D: joins the two components.

Four edges now connect five vertices, so the MST is complete. Its cost is 1 + 2 + 2 + 5 = 10.

The selected links are B–C, A–C, D–E, and B–D. This is the least total infrastructure cost, but it does not necessarily give the shortest route between every pair. The route A → C → B → D → E has cost 2 + 1 + 5 + 2 = 10. In the original network, Dijkstra’s algorithm could find a different shortest route if additional links were available; therefore network design and route optimization are separate objectives.

Outcome and learning points

The DSU efficiently prevented cycles during Kruskal’s process. The case also demonstrates why an MST should not be described as a collection of individually shortest routes. In professional systems, edge weights must be defined carefully: cost, latency, reliability, and capacity may lead to different optimization models.

11. Complexity and Engineering Considerations

Practical implementations should validate vertex identifiers, define behaviour for disconnected graphs, avoid integer overflow when adding large distances, and use suitable numeric types for weights. A priority queue may contain stale entries; checking whether a removed distance equals the current best distance prevents incorrect processing. For very large graphs, iterative traversal, compact identifiers, streaming edge processing, and memory profiling are important.

Graph data may also contain sensitive information, such as social relationships, user locations, or communication patterns. Systems should apply access control, data minimization, anonymization where appropriate, and careful retention policies. Algorithmic results can reproduce bias in the underlying data; a graph algorithm is not ethically neutral merely because its implementation is mathematically correct.

Chapter Summary

Graphs model entities and relationships through vertices and edges. Directedness, weights, density, and acyclicity determine which representation and algorithm are appropriate. Adjacency lists are generally efficient for sparse graphs, while matrices support constant-time edge lookup in dense graphs. BFS explores by layers and finds shortest paths in unweighted graphs. DFS supports reachability, cycle detection, and structural analysis. Topological sorting orders dependencies only when the graph is acyclic. Dijkstra handles nonnegative weighted edges, Bellman–Ford handles negative edges and detects reachable negative cycles, and Floyd–Warshall computes all-pairs distances for suitable graph sizes. Kruskal and Prim construct minimum spanning trees, while DSU efficiently maintains components and supports cycle testing. Correct algorithm selection requires attention to graph type, weight assumptions, complexity, memory, data quality, and the distinction between local route optimization and global network design.

Key Terms

Graph: A structure consisting of vertices and edges.

Vertex: A node or entity in a graph.

Edge: A relationship connecting two vertices.

Directed graph: A graph whose edges have orientations.

Weighted graph: A graph whose edges carry values such as cost or distance.

Adjacency list: A collection of neighbours stored for each vertex.

Adjacency matrix: A V × V table representing edge relationships.

Path: A sequence of connected vertices.

Cycle: A closed path containing a repeated starting vertex.

Connected component: A maximal connected subgraph.

BFS: Layer-by-layer graph traversal using a queue.

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

DAG: Directed acyclic graph.

Topological ordering: An ordering that places each edge’s source before its destination.

Relaxation: An attempt to improve a known shortest-path distance.

Minimum spanning tree: A least-weight spanning tree of an undirected weighted graph.

Disjoint-set union: A data structure for maintaining nonoverlapping sets.

Path compression: A DSU optimization that shortens parent paths during FIND.

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

Review Questions

Short Answer Questions

1. What is the difference between an adjacency list and an adjacency matrix?
2. Why does BFS find shortest paths in an unweighted graph?
3. State the condition under which Dijkstra’s algorithm is valid.
4. What does a topological ordering represent?
5. What are the purposes of path compression and union by size in DSU?

Long Answer Questions

1. Explain BFS and DFS, including their data structures, applications, and time complexity.
2. Describe Kahn’s topological-sorting algorithm and explain how it detects a cycle.
3. Compare Dijkstra’s algorithm, Bellman–Ford, and Floyd–Warshall with respect to assumptions and complexity.
4. Explain Kruskal’s and Prim’s algorithms and distinguish an MST from a shortest-path tree.
5. Discuss how graph representation affects memory use and algorithm performance.

Analytical / Application Questions

1. A network has 10,000 vertices and 12,000 edges. Recommend a representation and justify your choice in terms of space and traversal cost.
2. A directed project-dependency graph fails to produce a complete topological ordering. Explain what this implies and describe how you would locate the problematic cycle.
3. Given a weighted graph containing one negative edge but no negative cycle, choose a shortest-path algorithm and justify why Dijkstra would be unsafe.

Multiple Choice Questions with Answers

Question 1

Which representation usually requires Θ(V + E) space for a sparse graph?

A. Adjacency list

B. Adjacency matrix

C. V × V distance table

D. Complete edge-pair table

Correct Answer: A. Adjacency list

Question 2

Which data structure controls the standard breadth-first search order?

A. Stack

B. Queue

C. Priority queue ordered by weight

D. Disjoint-set forest

Correct Answer: B. Queue

Question 3

Dijkstra’s algorithm requires which condition on edge weights?

A. All weights must be equal

B. All weights must be negative

C. No edge may have a negative weight

D. The graph must be acyclic

Correct Answer: C. No edge may have a negative weight

Question 4

A directed graph has a topological ordering only if it is what type of graph?

A. Complete graph

B. Directed acyclic graph

C. Undirected weighted graph

D. Bipartite matrix graph

Correct Answer: B. Directed acyclic graph

Question 5

What does encountering an edge to an active vertex during directed DFS indicate?

A. A minimum spanning tree

B. A negative edge

C. A directed cycle

D. A disconnected component

Correct Answer: C. A directed cycle

Question 6

Which algorithm is designed to construct a minimum spanning tree by sorting edges?

A. Kruskal’s algorithm

B. Bellman–Ford algorithm

C. Floyd–Warshall algorithm

D. BFS

Correct Answer: A. Kruskal’s algorithm

Question 7

In DSU, what does FIND(x) return?

A. The shortest path from x

B. The representative of x’s set

C. The degree of x

D. The largest edge incident to x

Correct Answer: B. The representative of x’s set

Question 8

A tree containing 8 vertices has how many edges?

A. 7

B. 8

C. 16

D. 64

Correct Answer: A. 7

Question 9

Which algorithm can detect a reachable negative-weight cycle while computing single-source distances?

A. Prim’s algorithm

B. Bellman–Ford algorithm

C. BFS

D. Kruskal’s algorithm

Correct Answer: B. Bellman–Ford algorithm

Question 10

Why is an MST not generally a shortest-path tree?

A. An MST applies only to directed graphs

B. An MST minimizes total network weight, not distances from one source

C. An MST may contain cycles

D. An MST cannot contain weighted edges

Correct Answer: B. An MST minimizes total network weight, not distances from one source