9. Graph Structures and Algorithms

Introduction and Context

Many computational problems are concerned not with isolated objects but with relationships among objects. A road network connects locations, a computer network links devices, a social network represents interactions, and a software system expresses dependencies among modules. Graphs provide a general mathematical and computational model for such relationships.

A graph consists of vertices and edges. Its algorithms support traversal, reachability analysis, ordering of dependent tasks, network design, routing, resource allocation, and flow optimization. In computer science, graphs are particularly important because the same abstract structure can represent highly different domains. The quality of a graph solution depends not only on choosing a correct algorithm but also on selecting an appropriate representation, handling exceptional cases, and understanding the algorithm's computational cost.

This chapter develops graph representations in C and examines breadth-first search (BFS), depth-first search (DFS), topological sorting, connectivity, minimum spanning trees, shortest-path algorithms, and the foundations of network flow. The discussion emphasizes the relationship between graph properties, algorithmic assumptions, and practical implementation decisions.

Learning Objectives

After completing this chapter, the learner should be able to:

1. Distinguish directed, undirected, weighted, unweighted, connected, and cyclic graphs.

2. Select and implement adjacency-matrix and adjacency-list representations in C.

3. Apply BFS and DFS to traversal, reachability, cycle detection, and connectivity problems.

4. Explain and implement topological sorting for directed acyclic graphs.

5. Construct minimum spanning trees using Prim's and Kruskal's algorithms.

6. Select suitable shortest-path algorithms according to edge-weight conditions.

7. Explain the residual-network idea underlying maximum-flow algorithms.

8. Analyze time and space complexity and identify common implementation errors.

The Graph Model and Its Terminology

A graph is written as G = (V, E), where V is a finite set of vertices and E is a set of edges. In an undirected graph, an edge {u, v} has no direction; adjacency is symmetric. In a directed graph, an edge (u, v) goes from u to v and need not permit movement in the reverse direction.

A weighted graph associates a numerical weight with each edge. The weight may represent distance, cost, delay, risk, or capacity. A path is a sequence of vertices connected by edges. Its length in an unweighted graph is usually the number of edges; in a weighted graph it is the sum of edge weights. A cycle is a path that begins and ends at the same vertex, subject to the relevant definition for directed or undirected graphs. A simple graph has no self-loops or parallel edges.

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 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; it is weakly connected when connectivity exists after ignoring edge directions.

A tree is a connected, undirected, acyclic graph. A spanning tree of a connected graph includes every vertex 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: the former minimizes total network construction cost, whereas the latter minimizes distances from a specified source.

Representing Graphs in C

The two standard representations are the adjacency matrix and adjacency list. The choice affects memory use and the efficiency of common operations.

An adjacency matrix uses a two-dimensional array `A`, where `A[i][j]` indicates whether an edge from i to j exists. For a weighted graph, it stores the weight, while a special value such as `INF` represents no edge. An undirected edge appears symmetrically. The matrix requires Θ(V²) space and provides constant-time edge lookup. It is appropriate for dense graphs or algorithms that repeatedly inspect every possible pair of vertices.

An adjacency list stores, for each vertex, a list of its neighbors. It requires Θ(V + E) space and is generally preferable for sparse graphs. A basic C structure is:

```c

typedef struct Edge {

int dest;

int weight;

struct Edge *next;

} Edge;

typedef struct {

Edge *head;

} Vertex;

```

For an undirected graph, inserting `(u, v)` requires inserting both `v` in `u`'s list and `u` in `v`'s list. Forgetting the second insertion is a frequent error. For weighted graphs, the weight must be stored in each directed list entry.

An edge-list representation stores records such as `(source, destination, weight)` in an array. It is especially convenient for Kruskal's algorithm, which sorts edges by weight, although adjacency lists are normally better for traversal.

A robust implementation should define clearly whether vertices are numbered from 0 or 1, how absent edges are represented, whether duplicate edges are permitted, and how memory is released. If weights can be negative or very large, ordinary integer arithmetic may overflow; a sufficiently wide type and guarded addition are safer.

Traversal as a General Problem-Solving Pattern

Traversal systematically visits vertices reachable from a starting vertex. Both BFS and DFS maintain a visited set, but they differ in the order in which the frontier is explored. A traversal of a disconnected graph must be initiated from every unvisited vertex if the goal is to process the entire graph.

Breadth-First Search

BFS explores vertices in layers according to their distance from the source. It uses a first-in, first-out queue. When a vertex is removed from the queue, each unvisited neighbor is marked and enqueued.

```c

void bfs(Graph *g, int start) {

int visited[MAXV] = {0};

int queue[MAXV], front = 0, rear = 0;

visited[start] = 1;

queue[rear++] = start;

while (front < rear) {

int u = queue[front++];

printf("%d ", u);

for (Edge *p = g->adj[u]; p != NULL; p = p->next) {

int v = p->dest;

if (!visited[v]) {

visited[v] = 1;

queue[rear++] = v;

}

}

}

}

```

Marking a vertex when it is enqueued, rather than when it is removed, prevents multiple queue entries. In an unweighted graph, BFS produces shortest paths measured in number of edges. A `parent[]` array records the predecessor and permits reconstruction of a shortest route. With adjacency lists, BFS takes O(V + E) time; with a matrix it takes O(V²).

Depth-First Search

DFS follows one path as deeply as possible before backtracking. It may be implemented recursively or with an explicit stack. The recursive form is concise:

```c

void dfs(Graph *g, int u, int visited[]) {

visited[u] = 1;

printf("%d ", u);

for (Edge *p = g->adj[u]; p != NULL; p = p->next)

if (!visited[p->dest])

dfs(g, p->dest, visited);

}

```

DFS requires O(V + E) time with adjacency lists. Its recursion depth may reach V, so an explicit stack is safer for very deep or adversarial graphs. DFS supports connected-component discovery, cycle detection, topological ordering, articulation-point analysis, and strongly connected-component algorithms.

For an undirected graph, an edge from `u` to an already visited vertex is not automatically a cycle because it may simply be the edge to `u`'s parent. Cycle detection therefore tracks the parent vertex. For directed graphs, a three-state method is useful: unvisited, currently active, and completed. An edge to a currently active vertex identifies a directed cycle.

Topological Sorting and Dependency Structure

A topological ordering is a linear arrangement of vertices such that for every directed edge u → v, u appears before v. Such an ordering exists precisely for a directed acyclic graph (DAG). It is useful for course prerequisites, build systems, task scheduling, and package dependencies.

Kahn's algorithm repeatedly selects vertices of indegree zero. Their outgoing edges are removed conceptually, reducing the indegree of successors. If fewer than V vertices are output, the graph contains a cycle. The algorithm runs in O(V + E) time with adjacency lists and a queue. If several zero-indegree vertices exist, different valid orderings may result; a priority queue can impose a desired tie-breaking rule.

DFS provides another approach. A vertex is placed on a stack after all its descendants have been processed. Reversing the finishing order gives a topological order. DFS must detect a back edge to an active vertex; otherwise a cyclic graph could be incorrectly reported as a DAG.

Connectivity and Components

Running BFS or DFS from each unvisited vertex partitions an undirected graph into connected components. The component count is obtained by incrementing a counter whenever a new traversal begins. This procedure is used in image analysis, clustering, network fault diagnosis, and social-network analysis.

For directed graphs, reachability from one source is weaker than strong connectivity. Kosaraju's algorithm performs DFS on the original graph to obtain finishing order, reverses every edge, and performs DFS in decreasing finishing-time order. Each traversal in the reversed graph identifies one strongly connected component. Tarjan's algorithm finds the same components in one DFS using discovery indices and low-link values. These methods run in O(V + E), but their correctness depends on careful stack and state management.

A connected undirected graph with no articulation vertex remains connected after deletion of any one vertex. Similarly, a bridge is an edge whose deletion increases the number of connected components. Discovery times and low-link values allow DFS-based identification of articulation points and bridges, which is valuable in infrastructure reliability analysis.

Minimum Spanning Trees

Suppose a telecommunications company must connect all sites while minimizing cable cost. The relevant objective is an MST, not a shortest route from a particular headquarters. The graph must be undirected and connected for a spanning tree to exist.

Kruskal's algorithm sorts all edges in nondecreasing order and adds an edge when it joins two currently separate components. A disjoint-set union (DSU) structure supports this test efficiently. Its `find` operation identifies a component representative, while `union` merges components. Path compression and union by rank or size yield near-constant amortized performance. With sorting, Kruskal's complexity is O(E log E).

Prim's algorithm grows one tree. Starting from any vertex, it repeatedly selects the minimum-weight edge connecting the current tree to an outside vertex. With an adjacency matrix and a simple array, it takes O(V²). With adjacency lists and a binary heap, it takes O(E log V). Prim's and Kruskal's algorithms are greedy, and their correctness follows from the cut property: a minimum-weight edge crossing a cut is safe when it is uniquely light, and an appropriate light edge can be selected without destroying optimality.

If edge weights are equal, multiple MSTs may exist with the same total cost. A disconnected graph produces a minimum spanning forest rather than a single MST. Negative edge weights do not invalidate MST algorithms, because the objective is a sum over selected edges and no cycle is permitted.

Shortest Paths: Choosing the Right Assumptions

Shortest-path algorithms differ mainly in the weight assumptions they require.

BFS is the correct method when every edge has equal cost, commonly unit cost. Dijkstra's algorithm handles nonnegative edge weights. It maintains a tentative distance for each vertex and repeatedly finalizes the unvisited vertex with minimum tentative distance. Once finalized, its distance cannot improve because all remaining extensions have nonnegative cost. With a binary heap, the usual complexity is O((V + E) log V); with a matrix it is O(V²).

A typical relaxation step is:

```c

if (dist[u] != INF && dist[u] + w < dist[v]) {

dist[v] = dist[u] + w;

parent[v] = u;

}

```

The guard against `INF` prevents invalid arithmetic. Dijkstra's algorithm is not correct when negative edges are present, even if no negative cycle exists.

Bellman-Ford handles negative edge weights. It relaxes every edge V - 1 times and then performs one additional pass. If any distance can still be reduced, a reachable negative cycle exists. Its complexity is O(VE), making it slower but more general. Negative cycles make the notion of a finite shortest path undefined for vertices reachable from those cycles.

The Floyd-Warshall algorithm computes all-pairs shortest paths using dynamic programming. It tests whether a path from i to j improves by passing through an intermediate vertex k:

`D[i][j] = min(D[i][j], D[i][k] + D[k][j])`.

It requires O(V³) time and O(V²) space, and is useful for relatively small dense graphs. Initialization must set diagonal entries to zero, direct edges to their weights, and absent edges to infinity. A negative value on `D[i][i]` after processing indicates a negative cycle.

Network Flow Foundations

A flow network is a directed graph with a source s, sink t, and nonnegative capacity c(u,v) on each edge. A feasible flow obeys capacity constraints and flow conservation: except at source and sink, inflow equals outflow. The value of a flow is the net amount leaving s.

The residual network records remaining capacity. If an edge carries flow, the residual graph includes a reverse edge, allowing the algorithm to cancel or reroute earlier decisions. This reverse-edge idea is essential; an implementation that only adds unused forward capacity may fail to find a maximum flow.

Ford-Fulkerson repeatedly finds an s-to-t augmenting path and sends the largest possible additional amount, called the bottleneck, along it. With integer capacities, each augmentation increases the flow by at least one, but the running time depends on capacity values and path selection. Edmonds-Karp uses BFS to select augmenting paths and has O(VE²) complexity. The max-flow min-cut theorem states that the maximum possible flow value equals the minimum capacity of an s-t cut. This links an optimization result to a structural bottleneck in the network.

Flow models support bipartite matching, assignment, transportation, bandwidth allocation, and evacuation planning. In a bipartite matching reduction, edges connect a source to left-side vertices, permissible pairings connect the two partitions, and right-side vertices connect to the sink, usually with capacity one.

An Illustrative Applied Case: Dependency-Aware Service Deployment

Background

A fictional cloud platform deploys services that depend on one another. For example, an application service may require authentication, a database schema, and a message broker. The platform must determine a safe deployment order, identify isolated services, and route requests through a low-latency network.

Situation and Analysis

The service dependency graph is directed: an edge A → B means A must be deployed before B. A cycle such as A → B → C → A indicates an unsatisfiable dependency configuration. The infrastructure network is a separate weighted undirected graph, where vertices are data-center components and edge weights are installation costs.

Approach

Engineers first use Kahn's algorithm on the dependency graph. If all services are output, the result is a valid deployment order; otherwise the remaining vertices reveal a cyclic dependency region requiring redesign. DFS is then used to identify unreachable services and strongly connected components, which may represent tightly coupled modules.

For infrastructure construction, Kruskal's algorithm produces a minimum spanning forest when some sites are temporarily disconnected. For request routing from a regional gateway, Dijkstra's algorithm is selected because measured link delays are nonnegative. BFS is retained for diagnostic networks in which every hop has equal cost. If a capacity-planning exercise asks how much traffic can move between two regions, the network is converted into a capacitated directed graph and solved using a maximum-flow method.

Outcome and Learning Points

The platform obtains a deployment order only when dependencies are acyclic, a low-cost infrastructure design through an MST, and shortest operational routes through Dijkstra's algorithm. The case demonstrates that “the graph algorithm” is not a single choice: the correct method follows from the graph's direction, weights, objective, and constraints. Confusing MST cost with route distance, or applying Dijkstra to negative edges, would produce technically plausible but invalid results.

Implementation Risks and Professional Practice

Several errors recur in graph programs. A traversal may fail on disconnected graphs if it starts only once. A directed edge may accidentally be inserted in both directions. A queue may overflow when its capacity is fixed incorrectly. Recursive DFS may exhaust the call stack. Sentinel values such as `INT_MAX` may overflow during addition. A topological sort may report success without checking that all vertices were output. Dijkstra may be used without verifying nonnegative weights.

Input validation is important in production systems: vertex identifiers must be within range, capacities and weights must be checked, and duplicate-edge semantics must be defined. Memory allocated for adjacency lists must be released. For large graphs, compact arrays and iterative algorithms often improve locality and reduce overhead. Deterministic tie-breaking can make tests reproducible, although any valid topological order or MST may be mathematically acceptable.

Graph data may encode sensitive relationships, such as social contacts, movement, or organizational dependencies. Access control, minimization of collected data, anonymization, and auditability are therefore relevant. Routing and allocation algorithms can also affect people unevenly when their weights represent risk, service priority, or resource access. Technical optimality should not automatically be treated as organizational or ethical optimality.

Current Directions

Modern graph processing increasingly uses compressed sparse representations, parallel traversal, distributed graph engines, and streaming algorithms for graphs that change continuously. Graph databases expose relationship-oriented queries, while graph analytics supports fraud detection, recommendation, knowledge representation, and supply-chain monitoring. Machine-learning systems also use graph neural networks, although these do not replace classical algorithms: BFS, shortest paths, connectivity, and flow remain essential components for constructing features, constraints, and reliable baselines.

A practical trend is hybrid problem solving. A system may use a graph database to store relationships, a classical algorithm to enforce hard constraints, and a learning model to estimate edge costs. Such systems require careful monitoring because changes in data quality or learned weights can alter algorithmic outcomes.

Best Practices

1. State the graph type, objective, and edge-weight assumptions before choosing an algorithm.

2. Prefer adjacency lists for sparse graphs and matrices for dense graphs or constant-time edge queries.

3. Maintain explicit visited, parent, distance, indegree, and component data as required.

4. Test empty graphs, single-vertex graphs, disconnected graphs, duplicate edges, cycles, and extreme weights.

5. Use BFS for unweighted shortest paths, Dijkstra for nonnegative weights, Bellman-Ford for possible negative weights, and Floyd-Warshall for manageable dense all-pairs problems.

6. Separate algorithmic logic from input/output and memory-management code.

7. Verify results with invariants: every MST has V − 1 edges when connected, a topological order respects every edge, and flow conservation holds at intermediate vertices.

Chapter Summary

Graphs model entities and relationships through vertices and edges. Their representation—matrix, adjacency list, or edge list—should reflect density and access requirements. BFS explores layers and solves unweighted shortest-path problems, while DFS supports reachability, components, cycle detection, and structural analyses. Topological sorting orders dependencies in DAGs and detects cycles. Prim's and Kruskal's greedy algorithms construct minimum spanning trees, whereas shortest-path algorithms require careful attention to edge weights: BFS handles unit costs, Dijkstra nonnegative costs, Bellman-Ford negative edges, and Floyd-Warshall all-pairs computation. Flow networks model capacity and routing through residual graphs, augmenting paths, and cuts. Correct graph programming depends on matching algorithm assumptions to the problem, validating data, handling disconnected and exceptional cases, and considering the ethical implications of relationship-based data.

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 orientation.

Weighted graph: A graph whose edges carry numerical values.

Adjacency matrix: A two-dimensional representation indicating edges between vertex pairs.

Adjacency list: A representation storing each vertex's neighboring vertices.

BFS: A queue-based traversal that explores vertices by increasing unweighted distance.

DFS: A depth-oriented traversal that explores a branch before backtracking.

Topological ordering: A vertex order respecting every directed dependency edge.

DAG: A directed acyclic graph.

Connected component: A maximal set of mutually reachable vertices in an undirected graph.

Strongly connected component: A maximal directed subgraph with mutual reachability.

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

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

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

Residual network: A flow graph representing remaining and reversible capacity.

Augmenting path: An s-to-t path along which additional flow can be sent.

Cut: A partition of vertices into two sets, often used to bound or characterize flow.

Disjoint-set union: A structure supporting efficient component merging and representative queries.

Review Questions

Short Answer Questions

1. What is the difference between an adjacency matrix and an adjacency list?

2. Why does BFS find shortest paths in an unweighted graph?

3. What condition is necessary for a directed graph to have a topological ordering?

4. Distinguish a minimum spanning tree from a shortest-path tree.

5. Why are reverse edges required in a residual network?

Long Answer Questions

1. Explain BFS and DFS, including their data structures, applications, and complexities.

2. Describe Kahn's and DFS-based approaches to topological sorting and explain cycle detection.

3. Compare Prim's and Kruskal's algorithms, including the role of the cut property and DSU.

4. Compare BFS, Dijkstra, Bellman-Ford, and Floyd-Warshall according to their assumptions and complexity.

5. Explain the max-flow model, residual capacity, augmenting paths, and the max-flow min-cut theorem.

Analytical / Application Questions

1. A graph contains 10,000 vertices but only 25,000 edges. Which representation and traversal implementation would you choose, and why?

2. A dependency graph produces only 17 vertices in a topological ordering although it contains 20 vertices. What can be concluded, and how would you investigate it?

3. A routing graph contains one negative edge but no negative cycle. Which shortest-path method should be used, and why would Dijkstra be unsafe?

22. Multiple Choice Questions with Answers

Question 1

Which representation is generally most space-efficient for a sparse graph with V vertices and E edges?

A. Adjacency matrix using Θ(V²) space

B. Adjacency list using Θ(V + E) space

C. A Boolean array using Θ(E²) space

D. A stack using Θ(V² + E) space

Correct Answer: B. Adjacency list using Θ(V + E) space

Question 2

Why does BFS produce a shortest path in an unweighted graph?

A. It always selects the edge with the smallest stored weight

B. It explores vertices in nondecreasing order of number of edges from the source

C. It recursively examines every possible path

D. It removes cycles before traversal

Correct Answer: B. It explores vertices in nondecreasing order of number of edges from the source

Question 3

A directed graph has 12 vertices, but Kahn's algorithm outputs only 9. What is the most appropriate conclusion?

A. The graph must be disconnected

B. The graph contains a negative edge

C. The graph contains a directed cycle

D. The graph must have an MST

Correct Answer: C. The graph contains a directed cycle

Question 4

Which algorithm is appropriate for shortest paths when edge weights may be negative but no reachable negative cycle exists?

A. Dijkstra's algorithm

B. Bellman-Ford algorithm

C. Prim's algorithm

D. Kruskal's algorithm

Correct Answer: B. Bellman-Ford algorithm

Question 5

What is the principal objective of a minimum spanning tree?

A. Minimize the distance from one selected source to all vertices

B. Maximize the number of cycles in the graph

C. Connect all vertices with minimum total edge weight and no cycle

D. Order vertices according to their indegrees

Correct Answer: C. Connect all vertices with minimum total edge weight and no cycle

Question 6

In Kruskal's algorithm, what does a disjoint-set union structure help determine?

A. Whether adding an edge would connect vertices already in the same component

B. Whether a graph contains a negative cycle

C. The queue order for BFS

D. The residual capacity of a flow edge

Correct Answer: A. Whether adding an edge would connect vertices already in the same component

Question 7

Why can Dijkstra's algorithm give an incorrect result when a negative edge exists?

A. It cannot store weighted edges

B. It assumes a finalized minimum distance cannot later be improved

C. It requires the graph to be directed

D. It always ignores unreachable vertices

Correct Answer: B. It assumes a finalized minimum distance cannot later be improved

Question 8

What is the purpose of a reverse edge in a residual network?

A. To force every flow to be symmetric

B. To permit previously assigned flow to be cancelled or rerouted

C. To convert a directed graph into an MST

D. To identify all topological orderings

Correct Answer: B. To permit previously assigned flow to be cancelled or rerouted

Question 9

For an undirected graph, which additional information is needed to avoid falsely reporting the parent edge as a cycle during DFS?

A. The vertex degree only

B. The edge weight only

C. The parent of each visited vertex

D. The indegree of the source only

Correct Answer: C. The parent of each visited vertex

Question 10

A network must connect all sites at minimum construction cost, while a separate requirement asks for the fastest route from headquarters. Which pair of methods best matches these objectives?

A. MST algorithm for construction and shortest-path algorithm for routing

B. BFS for construction and DFS for routing regardless of weights

C. Topological sorting for both objectives

D. Maximum flow for construction and DSU for routing

Correct Answer: A. MST algorithm for construction and shortest-path algorithm for routing