Graphs and Network Algorithms

Introduction

Graphs provide a general model for relationships, dependencies, routes, and flows. A web application may represent links between pages, a social platform may represent friendships, and a delivery system may represent roads connecting warehouses and customers. Unlike linear data structures, graphs can express many-to-many relationships and complex connectivity.

A graph is written as G = (V, E), where V is a set of vertices (or nodes) and E is a set of edges (or links). An edge specifies a relationship between two vertices. Graph algorithms are central to full-stack development because they support navigation, dependency management, recommendation systems, network monitoring, routing, and distributed services.

Learning Objectives

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

• distinguish directed, undirected, weighted, unweighted, cyclic, and acyclic graphs;
• select and implement adjacency lists and adjacency matrices;
• perform breadth-first search (BFS) and depth-first search (DFS);
• use topological sorting on directed acyclic graphs;
• apply Dijkstra’s and Bellman–Ford algorithms appropriately;
• construct minimum spanning trees using Kruskal’s and Prim’s algorithms;
• explain strongly connected components and the foundations of network flow;
• analyze complexity, limitations, and practical engineering trade-offs.

1. Graph Foundations

A vertex represents an entity, such as a user, city, service, or task. An edge represents a relationship or transition. In a directed graph, an edge has an orientation: (u, v) means that movement is permitted from u to v. In an undirected graph, the relationship is reciprocal, so {u, v} connects both vertices.

A graph may be unweighted or weighted. In a weighted graph, each edge has a value such as distance, cost, latency, or capacity. Edge weights need not represent physical distance, but the meaning must be consistent with the algorithm being used.

Important terminology includes:

• Adjacent vertices: vertices joined by an edge.
• Degree: number of incident edges in an undirected graph. In a directed graph, in-degree counts incoming edges and out-degree counts outgoing edges.
• Path: a sequence of vertices connected by edges.
• Simple path: a path containing no repeated vertex.
• Cycle: a path that begins and ends at the same vertex, with at least one edge.
• Connected graph: an undirected graph in which every pair of vertices has a path between them.
• Strongly connected directed graph: every vertex can reach every other vertex following edge directions.
• Subgraph: a graph formed from subsets of vertices and edges.
• Tree: a connected undirected graph with no cycles.
• Forest: a collection of disjoint trees.

For an undirected graph with n vertices and m edges, the sum of all vertex degrees is 2m, because every edge contributes two to the total. For a directed graph, the sum of all in-degrees and the sum of all out-degrees are each m.

A dense graph has close to the maximum possible number of edges, while a sparse graph has relatively few edges. For a simple undirected graph, the maximum number of edges is:

Here n is the number of vertices. For a simple directed graph without self-loops, the maximum is n(n − 1). These bounds help determine the most appropriate representation.

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 list entry also stores the edge weight.

For example, edges A → B, A → C, and B → C produce lists such as:

A: (B), (C)
B: (C)
C:

An adjacency list requires O(V + E) space and is efficient for sparse graphs. Iterating over the neighbors of a vertex takes time proportional to its degree.

2.2 Adjacency matrix

An adjacency matrix is a V × V table. Entry M[i][j] indicates whether an edge exists, or stores its weight. For an unweighted graph, a Boolean value is suitable. For a weighted graph, absent edges require a special representation such as infinity, not zero, because zero may be a valid weight.

The matrix uses O(V²) space. Testing whether a particular edge exists takes O(1) time, making matrices useful for dense graphs or applications requiring frequent edge queries.

2.3 Engineering considerations

A production implementation should define whether parallel edges, self-loops, missing vertices, and duplicate edges are permitted. It should also clarify whether weights may be negative and whether graph updates occur concurrently. These choices affect correctness as well as performance.

3. Breadth-First and Depth-First Search

Graph traversal visits vertices systematically. A visited set is essential in graphs containing cycles; without it, a traversal may continue indefinitely.

3.1 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] = undefined
        parent[v] = null
    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] is false:
                visited[v] = true
                distance[v] = distance[u] + 1
                parent[v] = u
                enqueue(Q, v)

For an adjacency-list graph, BFS runs in O(V+E) time and uses O(V) auxiliary space. In an unweighted graph, BFS produces shortest paths measured by number of edges. It does not generally produce minimum-cost paths when edge weights differ.

Worked example. Suppose the edges are A−B, A−C, B−D, and C−E. Starting at A, BFS visits A first, then B and C, then D and E. The shortest edge-count distances are 0 for A, 1 for B and C, and 2 for D and E.

Typical uses include level-order exploration, finding connected components, testing reachability, and determining whether an undirected graph is bipartite by assigning alternating levels.

3.2 Depth-first search

DFS follows one path as deeply as possible before backtracking. It can be implemented recursively or with an explicit stack.

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

DFS also runs in O(V+E) time with adjacency lists. Its applications include cycle detection, topological sorting, connected-component discovery, articulation-point analysis, and strongly connected components.

For directed cycle detection, a three-state scheme is useful: unvisited, active, and finished. Encountering an edge from a vertex to an active vertex identifies a back edge and therefore a directed cycle.

Recursive DFS is conceptually simple, but a very deep graph can exceed the programming language’s call-stack limit. An explicit stack is safer for untrusted or very large input.

4. Directed Acyclic Graphs and Topological Sorting

A directed acyclic graph (DAG) is a directed graph containing no directed cycle. DAGs model prerequisite relationships, build systems, course dependencies, and data-processing pipelines.

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

4.1 Kahn’s algorithm

Kahn’s algorithm repeatedly removes vertices with in-degree zero.

Kahn(G):
    compute indegree[v] for every vertex v
    place every vertex with indegree 0 in queue Q
    order = empty list

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

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

The time complexity is O(V+E) with adjacency lists. If several vertices have in-degree zero, multiple valid orders may exist. A queue gives one valid order; a priority queue can produce a lexicographically smallest order according to a chosen vertex ordering.

Topological sorting is not itself scheduling optimization. It enforces precedence constraints, but additional durations, resources, and deadlines are required for resource-constrained scheduling.

5. Shortest-Path Algorithms

A shortest-path problem seeks a minimum-cost path from a source to one or more destinations. For a path P, its total cost is the sum of its edge weights:

This additive model assumes that path costs are compatible and that traversing an edge contributes independently to total cost. Negative cycles create a special problem: repeatedly traversing such a cycle can reduce the path cost without bound, so no finite shortest path exists for vertices reachable from that cycle.

5.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 finalizes the unsettled vertex with the smallest tentative value.

Dijkstra(G, s):
    dist[v] = infinity for every v
    parent[v] = null for every v
    dist[s] = 0
    priority queue contains (0, s)

    while queue is not empty:
        (d, u) = extract minimum
        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 usual complexity is O((V+E) log V). With a simple array, it is O(V²). The algorithm is invalid when negative edge weights are present, even if no negative cycle exists.

Worked example. Consider S→A with cost 4, S→B with cost 1, B→A with cost 2, and A→T with cost 3. Dijkstra initially assigns A=4 and B=1. Processing B improves A to 3. Processing A then gives T=6. Thus the least-cost path from S to T is S→B→A→T with cost 1+2+3=6.

5.2 Bellman–Ford algorithm

Bellman–Ford supports negative edge weights and can detect reachable negative cycles. It relaxes every edge repeatedly. After at most V−1 complete passes, all finite shortest simple paths have been considered; a further improvement indicates a reachable negative cycle.

Its time complexity is O(VE), making it slower than Dijkstra in many nonnegative-weight cases. Its value is correctness under broader weight conditions.

5.3 Choosing a shortest-path method

Floyd–Warshall uses dynamic programming and runs in O(V³) time with O(V²) space. It is useful for all-pairs distances but is unsuitable for very large sparse graphs.

6. Minimum Spanning Trees

For a connected, undirected, weighted graph, a spanning tree includes every vertex, contains no cycle, and has exactly V−1 edges. A minimum spanning tree (MST) is a spanning tree with minimum total edge weight.

An MST is not a shortest-path tree. A shortest-path tree minimizes distances from a selected source; an MST minimizes the sum of all selected connection edges.

6.1 Kruskal’s algorithm

Kruskal’s algorithm sorts edges by nondecreasing weight and adds an edge when it connects two previously separate components. A disjoint-set union (DSU) structure efficiently supports this test.

Kruskal(G):
    sort edges by increasing weight
    create one DSU set for each vertex
    T = empty set
    for edge (u, v, w) in sorted edges:
        if FIND(u) ≠ FIND(v):
            add edge to T
            UNION(u, v)
    return T

Sorting dominates the complexity: O(E log E). With path compression and union by rank or size, DSU operations are nearly constant amortized time.

6.2 Prim’s algorithm

Prim’s algorithm grows one tree. Beginning at any vertex, it repeatedly selects the cheapest edge joining the current tree to an unvisited vertex. With a binary heap and adjacency lists, its complexity is O(E log V). Both Kruskal and Prim are correct because of the cut property: a minimum-weight edge crossing a cut is safe to include when it is uniquely minimum, and an appropriate minimum crossing edge is always safe more generally.

If the graph is disconnected, these algorithms produce a minimum spanning forest rather than a single MST.

7. 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 reveal mutually dependent services, circular module relationships, and recurring states in transition systems.

Kosaraju’s algorithm performs DFS on the original graph to record finishing order, reverses every edge, and performs DFS in decreasing finishing order. Each second-pass traversal identifies one SCC. Its complexity is O(V+E). Tarjan’s algorithm finds SCCs in one DFS using discovery indices and low-link values, also in O(V+E).

Contracting each SCC into one super-vertex produces a condensation graph. This graph is always a DAG, which permits topological analysis of otherwise cyclic systems.

8. Network-Flow Foundations

A flow network is a directed graph with a source s, a sink t, and nonnegative capacities c(u,v). A feasible flow f(u,v) satisfies:

For every intermediate vertex, conservation requires inflow to equal outflow:

The value of the flow is the net flow leaving the source, equivalently the net flow entering the sink. The maximum-flow problem seeks the largest feasible flow from source to sink.

Residual capacity records how much additional flow can be sent forward and how much existing flow can be cancelled in reverse. Ford–Fulkerson repeatedly finds an augmenting path and sends the largest possible additional amount along it. Edmonds–Karp chooses augmenting paths using BFS and has complexity O(VE²). More advanced algorithms, such as Dinic’s algorithm, improve performance for many practical network structures.

The max-flow min-cut theorem states that the maximum flow value equals the minimum capacity of an s–t cut. A cut partitions vertices into sets S and T with s ∈ S and t ∈ T; its capacity is the sum of capacities on edges directed from S to T. This theorem supports bandwidth planning, bipartite matching reductions, and capacity bottleneck analysis.

9. Applied Case: Delivery-Route and Service Planning

Background. Consider an illustrative online retailer with fulfilment centres, local depots, and customer zones. Roads are directed because of one-way restrictions, and each road has a travel-time weight. The retailer also has a software deployment pipeline in which services depend on one another.

Problem. The system must answer four questions: which locations are reachable, what is the fastest route, in what order should services deploy, and where should limited network capacity be increased?

Analysis and approach. An adjacency list is selected because the road network is sparse. BFS checks whether a delivery zone is reachable when all roads are treated equally. Dijkstra computes fastest routes because travel times are nonnegative. If an unusual credit or adjustment creates negative costs, Bellman–Ford is required instead. Deployment dependencies are represented as a DAG and processed with Kahn’s algorithm. Finally, a flow network models warehouse capacity, road capacity, and customer demand; maximum flow identifies the achievable throughput and a minimum cut exposes the bottleneck.

Outcome. The organization obtains route plans, a valid deployment order, and a quantitative capacity limit. Importantly, the algorithms answer different questions: BFS minimizes edge count, Dijkstra minimizes additive travel time, topological sorting respects precedence, and maximum flow measures throughput.

Learning points. A graph model must reflect the meaning of relationships. Treating a directed road as undirected can produce impossible routes. Treating time-dependent or negative-valued data as ordinary nonnegative weights can invalidate Dijkstra. Separating graph construction, validation, algorithm selection, and result interpretation improves maintainability.

10. Correctness, Complexity, and Professional Practice

Algorithm selection should begin with assumptions, not implementation convenience. Document whether the graph is directed, whether weights are nonnegative, whether disconnected inputs are allowed, and whether changes can occur during computation.

Common failure modes include marking vertices visited too late, forgetting reverse edges in an undirected representation, using zero to mean both “no edge” and “zero cost,” applying topological sorting to cyclic data, and confusing an MST with a shortest-path tree. Integer overflow is also possible when many edge weights are added; sufficiently wide numeric types and explicit bounds are necessary.

For production systems, validate input, reject malformed endpoints, limit resource consumption, and avoid exposing internal graph data unnecessarily. Graphs can encode sensitive social, location, and behavioural relationships. Access control, data minimization, retention limits, and auditability are therefore important. Recommendation and routing systems may reproduce bias if edge construction or weights reflect discriminatory historical data. Explainable scoring and human review may be required in high-impact decisions.

Contemporary systems often use graph databases, distributed graph processing, and graph neural networks. These technologies do not replace classical algorithms: a graph neural network may learn representations, while BFS, shortest-path, flow, and connectivity algorithms provide deterministic structural operations and useful validation baselines.

Chapter Summary

Graphs model entities and relationships using vertices and edges. Directedness, weights, density, cycles, and connectivity determine both the representation and the appropriate algorithm. Adjacency lists are usually efficient for sparse graphs, while matrices provide constant-time edge lookup at quadratic space cost.

BFS uses a queue and finds minimum edge-count distances in unweighted graphs. DFS supports structural analysis such as cycle detection and SCC computation. Topological sorting orders dependencies in DAGs. BFS, Dijkstra, Bellman–Ford, and Floyd–Warshall solve shortest-path problems under different assumptions. Kruskal’s and Prim’s algorithms construct minimum spanning trees, which differ conceptually from shortest-path trees. SCC algorithms identify mutually reachable regions, and network-flow algorithms analyze capacity subject to edge limits and flow conservation. Reliable graph engineering requires explicit assumptions, complexity analysis, validation, and awareness of privacy and fairness risks.

Key Terms

Graph: A structure consisting of vertices and edges.

Vertex: An entity or node in a graph.

Edge: A relationship or connection between vertices.

Directed graph: A graph whose edges have orientations.

Weighted graph: A graph whose edges carry numerical values.

Degree: The number of incident edges at a vertex.

Path: A sequence of vertices connected by edges.

Cycle: A path that returns to its starting vertex.

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

Adjacency matrix: A two-dimensional table representing edge relationships.

BFS: Queue-based traversal that explores by layers.

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

DAG: A directed acyclic graph.

Topological ordering: An ordering that respects every directed edge.

Shortest path: A minimum-cost path under a specified weight model.

Minimum spanning tree: A least-total-weight spanning tree.

Strongly connected component: A maximal mutually reachable set in a directed graph.

Residual capacity: Remaining or reversible capacity in a flow network.

Minimum cut: A lowest-capacity partition separating source and sink.

Review Questions

5 Short Answer Questions

1. What is the difference between a directed and an undirected graph?
2. Why does BFS find shortest paths in an unweighted graph?
3. State the condition required for Dijkstra’s algorithm to be correct.
4. What property makes a graph suitable for topological sorting?
5. How does an adjacency list differ from an adjacency matrix?

5 Long Answer Questions

1. Explain BFS and DFS, including their data structures, applications, and complexities.
2. Compare Dijkstra’s algorithm and Bellman–Ford, including their assumptions and limitations.
3. Explain Kruskal’s and Prim’s algorithms and distinguish an MST from a shortest-path tree.
4. Describe strongly connected components and explain how Kosaraju’s algorithm finds them.
5. Define a flow network and explain capacity constraints, conservation, residual capacity, and the max-flow min-cut theorem.

3 Analytical / Application Questions

1. A graph contains negative edge weights but no negative cycle. Which shortest-path algorithm should be selected, and why?
2. A build system reports that no task has in-degree zero. What does this imply, and how should the system respond?
3. A delivery network has limited warehouse and road capacities. Explain how a maximum-flow model could identify the system’s throughput and bottleneck.

Multiple Choice Questions with Answers

Question 1

Which representation usually uses O(V+E) space for a graph?

A. Adjacency list

B. Adjacency matrix

C. Incidence table with every possible pair

D. Distance matrix

Correct Answer: A. Adjacency list

Question 2

Which data structure is fundamental to standard BFS?

A. Stack

B. Queue

C. Heap only

D. Disjoint-set structure

Correct Answer: B. Queue

Question 3

For which graph does a topological ordering exist?

A. Every connected graph

B. Every weighted graph

C. A directed acyclic graph

D. Every undirected tree only

Correct Answer: C. A directed acyclic graph

Question 4

What assumption is required by Dijkstra’s algorithm?

A. All edges have equal weight

B. All edge weights are nonnegative

C. The graph must be acyclic

D. The graph must be complete

Correct Answer: B. All edge weights are nonnegative

Question 5

A spanning tree of a connected graph with V vertices contains how many edges?

A. V−1

B. V

C. 2V

D. V²

Correct Answer: A. V−1

Question 6

Which algorithm is designed to detect reachable negative-weight cycles while finding single-source shortest paths?

A. Prim’s algorithm

B. Bellman–Ford algorithm

C. Kahn’s algorithm

D. BFS

Correct Answer: B. Bellman–Ford algorithm

Question 7

What does an SCC contain in a directed graph?

A. Vertices with identical edge weights

B. Vertices where every vertex can reach every other vertex

C. Only vertices with in-degree zero

D. All vertices at the same BFS level

Correct Answer: B. Vertices where every vertex can reach every other vertex

Question 8

What does flow conservation require at an intermediate vertex?

A. Inflow equals outflow

B. Outflow must be zero

C. Inflow must equal capacity

D. Every outgoing edge must have equal capacity

Correct Answer: A. Inflow equals outflow

Question 9

Which algorithm commonly uses a disjoint-set union structure?

A. Kruskal’s algorithm

B. Dijkstra’s algorithm

C. Floyd–Warshall algorithm

D. BFS

Correct Answer: A. Kruskal’s algorithm

Question 10

In an unweighted graph, BFS from a source assigns distance 2 to a vertex when the vertex is:

A. Two edges away along a shortest path

B. Connected by an edge of weight 2

C. Visited after exactly two total vertices

D. In the second connected component

Correct Answer: A. Two edges away along a shortest path