Graph Structures and Algorithms

Introduction

Graphs provide a general model for representing relationships among objects. A computer network, road system, social network, prerequisite structure, recommendation system, and workflow can all be represented as graphs. Unlike linear structures such as arrays, stacks, and queues, graphs allow an element to be connected to any number of other elements.

A graph consists of vertices (also called nodes) and edges (also called links or arcs). Algorithms on graphs answer questions such as:

• Which objects are reachable from a starting object?
• Are all locations connected?
• What is the least-cost route between two locations?
• Can tasks be arranged in a valid dependency order?
• Does a network contain a cycle?
• What is the cheapest set of links connecting all locations?

Graph algorithms are therefore central to software engineering, cybersecurity, databases, artificial intelligence, geographic information systems, and operations research.

Learning Objectives

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

1. Define and classify directed, undirected, weighted, and labeled graphs.
2. Select and implement adjacency-list and adjacency-matrix representations.
3. Apply breadth-first search and depth-first search.
4. Determine reachability, connectivity, and cycle existence.
5. Compute shortest paths using appropriate algorithms.
6. Construct minimum spanning trees.
7. Produce a topological ordering for a directed acyclic graph.
8. Evaluate algorithmic complexity and practical limitations.

1. Fundamental Graph Concepts

A graph is commonly written as G = (V, E), where V is the set of vertices and E is the set of edges. Let n = |V| denote the number of vertices and m = |E| the number of edges.

In an undirected graph, an edge connects two vertices symmetrically. If an edge joins A and B, movement is possible in both directions. In a directed graph, an edge has an origin and destination. The edge A → B does not imply that B → A exists.

A weighted graph associates a numerical value with each edge. The value may represent distance, cost, time, bandwidth, risk, or energy. A labeled graph assigns descriptive information to vertices or edges, such as a city name, road type, account category, or relationship type. Graphs may be directed and weighted simultaneously.

Important terminology includes:

• Adjacent vertices: vertices joined by an edge.
• Incident edge: an edge connected to a vertex.
• Degree: number of incident edges in an undirected graph.
• In-degree: number of incoming edges to a vertex.
• Out-degree: number of outgoing edges from a vertex.
• Path: a sequence of vertices connected by edges.
• Simple path: a path that does not repeat vertices.
• Cycle: a closed path that begins and ends at the same vertex.
• 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 of another graph.

For an undirected graph, the sum of all vertex degrees equals twice the number of edges:

This is the handshaking theorem. Each edge contributes one incidence to each endpoint. For a directed graph, the sum of in-degrees equals the sum of out-degrees, and both equal the number of directed edges:

A graph with an edge from every vertex to every other distinct vertex is a complete graph. An undirected complete graph with n vertices has:

This formula applies only to simple undirected graphs, meaning that loops and duplicate edges are not permitted.

2. Graph Representations

The representation should reflect the graph’s density, operations, and memory constraints.

2.1 Adjacency Matrix

An adjacency matrix is an n × n table. For an unweighted graph, entry A[i][j] is 1 if an edge from vertex i to vertex j exists and 0 otherwise. For a weighted graph, the entry stores the edge weight; a special value such as infinity represents no edge.

For an undirected graph, the matrix is symmetric: A[i][j] = A[j][i]. A matrix uses O(n²) memory, regardless of the number of edges. Testing whether an edge exists takes O(1) time, while listing all neighbors of one vertex takes O(n).

Matrices are effective for dense graphs and algorithms that repeatedly test arbitrary pairs of vertices. They are inefficient for sparse graphs because most entries may contain no edge.

2.2 Adjacency List

An adjacency list stores, for each vertex, a collection of its neighbors. A weighted list stores pairs such as (neighbor, weight). For a directed graph, only outgoing neighbors are normally stored; an additional reverse list can be maintained when incoming-neighbor queries are common.

An adjacency list uses O(n + m) memory. Iterating over the neighbors of vertex v takes O(degree(v)) time. Edge-existence testing is typically O(degree(v)) with an unsorted list, although hashing can improve expected performance.

Adjacency lists are generally preferred for sparse graphs and for traversal algorithms.

2.3 Edge List

An edge list stores edges explicitly, for example (A, B, 7). It is simple and compact, especially when the main operation is processing every edge. Kruskal’s minimum-spanning-tree algorithm and Bellman–Ford shortest paths commonly use edge lists.

3. Graph Traversal

Traversal systematically visits vertices while avoiding repeated work. A traversal normally maintains a visited set. Without it, a cyclic graph can cause infinite repetition.

3.1 Breadth-First Search

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

Algorithm: BFS

1. Mark the start vertex visited and enqueue it.
2. While the queue is not empty, remove its front vertex u.
3. For each unvisited neighbor v of u, mark v visited, record u as its predecessor, and enqueue v.
4. Continue until the queue is empty or the target is found.

With an adjacency list, BFS runs in O(n + m) time because every vertex and edge is processed at most a constant number of times. Its space complexity is O(n), excluding the graph itself.

In an unweighted graph, BFS produces shortest paths measured by number of edges. If the predecessor of each vertex is recorded, the path can be reconstructed by following predecessors backward from the target.

Worked example. Suppose the edges are A–B, A–C, B–D, C–E, and D–F. BFS from A visits A first, then B and C, then D and E, and finally F. The distance from A to F is 3 edges. A predecessor chain is F ← D ← B ← A.

3.2 Depth-First Search

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

Algorithm: DFS

1. Mark the current vertex visited.
2. For each unvisited neighbor, recursively perform DFS on that neighbor.
3. Return when all neighbors have been explored.

DFS also runs in O(n + m) time with adjacency lists and O(n) auxiliary space. It is useful for connected components, cycle detection, topological sorting, articulation analysis, and maze exploration.

The order produced by DFS depends on the order in which neighbors are stored. Therefore, traversal order is not necessarily unique.

4. Connectivity and Cycle Detection

4.1 Connected Components

For an undirected graph, run DFS or BFS from every unvisited vertex. Each search identifies one connected component. The total time is O(n + m). A graph is connected if exactly one component is found.

For directed graphs, ordinary reachability is directional. A graph is strongly connected if every vertex can reach every other vertex. Strongly connected components can be found using algorithms such as Kosaraju’s or Tarjan’s algorithm, both of which run in O(n + m) time.

4.2 Cycle Detection in Undirected Graphs

During DFS, an edge from the current vertex to an already visited vertex may indicate a cycle. However, the edge leading back to the current vertex’s parent must be ignored because undirected edges appear in both adjacency lists.

An alternative is a disjoint-set union structure. Process each edge (u, v): if u and v are already in the same set, the edge creates a cycle; otherwise, union their sets. With path compression and union by rank, a sequence of operations has near-constant amortized cost, commonly expressed as O(m α(n)), where α is the very slowly growing inverse Ackermann function.

4.3 Cycle Detection in Directed Graphs

DFS detects a directed cycle by tracking three states:

• unvisited,
• currently being explored,
• completely explored.

An edge to a currently explored ancestor, called a back edge, proves the existence of a directed cycle. This method runs in O(n + m).

5. Shortest-Path Algorithms

The shortest-path problem seeks a path with minimum total weight. For a path containing edges with weights w₁, w₂, …, wₖ, its total cost is:

This additive model assumes that path costs can be summed and that the objective is minimization.

5.1 Choosing an Algorithm

5.2 Dijkstra’s Algorithm

Dijkstra’s algorithm maintains the best currently known distance from a source s. Initially, distance(s) = 0 and every other distance is infinity. Repeatedly select the unprocessed vertex with the smallest tentative distance and relax its outgoing edges.

For an edge u → v with weight w(u, v), relaxation applies:

Here d[x] is the current best distance from the source to x. If a priority queue implemented with a binary heap is used, the complexity is O((n + m) log n). With an adjacency matrix and simple selection, it is O(n²).

Dijkstra is correct when every edge weight is nonnegative. It must not be used with negative edge weights, even if no negative cycle exists.

Worked example. Consider edges A → B (4), A → C (1), C → B (2), B → D (1), and C → D (5). Starting at A:

• Initially: d(A)=0, d(B)=4, d(C)=1, d(D)=∞.
• Select C: update B to 3 and D to 6.
• Select B: update D to 4.
• Select D: no improvement.

The shortest distance from A to D is 4, through A → C → B → D.

5.3 Bellman–Ford Algorithm

Bellman–Ford relaxes every edge repeatedly, up to n − 1 times. If any edge can still be relaxed after that, a reachable negative-weight cycle exists. Its time complexity is O(nm).

The algorithm is slower than Dijkstra but supports negative edges. A negative cycle makes the shortest-path problem undefined for vertices reachable from that cycle because a path can be made arbitrarily cheap by circling repeatedly.

5.4 Floyd–Warshall Algorithm

Floyd–Warshall computes shortest paths between every pair of vertices. It progressively permits intermediate vertices. Its recurrence is:

At stage k, d[i][j] is the best distance from i to j using only permitted intermediate vertices among the first k vertices. The time complexity is O(n³) and the usual space complexity is O(n²). Negative edges are allowed, but a negative cycle can be detected when some diagonal entry d[i][i] becomes negative.

6. Minimum Spanning Trees

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

MST algorithms apply to connected, undirected, weighted graphs. They do not solve the shortest route from one source to every destination; an MST minimizes the total cost of selected network links, not each individual route.

6.1 Kruskal’s Algorithm

Kruskal’s algorithm sorts edges by nondecreasing weight. It repeatedly adds the next edge if that edge connects two different components. A disjoint-set structure efficiently tests whether an edge would create a cycle.

With sorting, the complexity is O(m log m), usually written O(m log n) for simple graphs because m ≤ n².

6.2 Prim’s Algorithm

Prim’s algorithm begins with any vertex and repeatedly adds the cheapest edge connecting the growing tree to a vertex outside it. With an adjacency list and binary heap, its complexity is O((n + m) log n).

Worked example. Suppose a network has edges A–B=1, A–C=4, B–C=2, B–D=5, C–D=3. Kruskal selects A–B (1), B–C (2), and C–D (3), producing an MST of total weight 6. The edge A–C is rejected because it would create a cycle, and B–D is unnecessary.

7. Topological Ordering

A topological ordering is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every edge u → v, u appears before v. It represents prerequisite or dependency relationships.

A topological ordering exists if and only if the directed graph has no cycle.

7.1 Kahn’s Algorithm

1. Compute the in-degree of every vertex.
2. Place all zero-in-degree vertices in a queue.
3. Remove one such vertex and append it to the ordering.
4. Decrease the in-degree of its outgoing neighbors.
5. Add any neighbor whose in-degree becomes zero.
6. If fewer than n vertices are output, the graph contains a cycle.

The complexity is O(n + m). If several zero-in-degree vertices exist, more than one valid ordering may be possible.

7.2 DFS-Based Ordering

DFS can produce a topological order by placing each vertex on a stack when its exploration finishes, then reversing the finish order. A recursion-stack check is required to reject cycles.

Example. For prerequisites A → C, B → C, and C → D, valid orders include A, B, C, D and B, A, C, D. The order A, C, B, D is invalid because B must precede C.

8. A Practical Application: Emergency-Routing Network

The following is an illustrative case study.

Background

A city emergency service operates stations, hospitals, and major intersections connected by roads. Each road has a travel-time estimate. Some roads may be temporarily unavailable, and dispatchers need both fast routing and resilient network design.

Problem

The service must answer three questions:

1. What is the fastest route from a station to an incident?
2. Can every important location still be reached if a road is unavailable?
3. What minimum set of communication links connects all stations for backup coordination?

Analysis

Intersections and facilities are represented as vertices. Roads are directed if traffic restrictions make travel one-way; otherwise they are represented as undirected edges. Travel times are nonnegative weights. Names, road classes, and emergency restrictions are labels.

An adjacency list is appropriate because a city map is usually sparse relative to the number of possible pairs of locations. BFS can provide minimum-hop routes when all roads are treated equally. Dijkstra’s algorithm provides minimum travel-time routes when all travel-time weights are nonnegative. DFS or BFS can identify disconnected areas after a road failure. Prim’s or Kruskal’s algorithm can design a low-cost backup communications network.

Approach and Solution

The system maintains:

• an adjacency list for current roads;
• a priority queue for Dijkstra’s algorithm;
• predecessor records for reconstructing routes;
• a disjoint-set structure for rapid connectivity checks during network design;
• edge and vertex labels for restrictions and operational categories.

When a road is closed, the system removes or disables that edge and recomputes affected routes. If road closures create separate components, dispatchers are warned that some locations are unreachable. For planned infrastructure, an MST minimizes total installation cost, while shortest-path calculations determine operational travel routes.

Outcome

The design distinguishes two objectives that are often confused: shortest paths minimize the cost of individual journeys, whereas an MST minimizes the total cost of connecting the entire network. Using the correct algorithm improves both response time and infrastructure planning.

Learning Points

1. Data representation affects memory use and performance.
2. Edge direction must reflect actual movement rules.
3. Nonnegative travel times justify Dijkstra’s algorithm.
4. Connectivity analysis is essential after failures.
5. A minimum spanning tree is not a replacement for route planning.

9. Implementation and Engineering Considerations

Input Validation

A graph implementation should validate vertex identifiers, reject malformed edges, define whether parallel edges are permitted, and state how self-loops are treated. For weighted graphs, units and allowable ranges must be documented.

Numerical Issues

Weights may be integers, floating-point values, or application-specific quantities. Infinity must be represented safely so that adding a finite weight to infinity does not overflow. Floating-point comparisons may require a documented tolerance when weights are computed rather than exact.

Scalability

For large sparse graphs, adjacency lists and priority queues are normally preferable. For dense graphs or repeated pair queries, matrices may be more suitable. External-memory and distributed graph systems may partition vertices and edges, but partition boundaries can create communication overhead.

Correctness and Testing

Tests should include empty graphs, isolated vertices, disconnected components, duplicate edges, self-loops, directed cycles, negative edges, equal weights, and unreachable destinations. For shortest paths, compare predecessor chains and total weights, not only final distances. For MSTs, verify that the output has n − 1 edges, is connected, and contains no cycle.

Ethical and Governance Issues

Graph algorithms can influence emergency dispatch, credit relationships, employment networks, and social recommendations. Graph data may expose personal relationships or sensitive locations. Systems should apply access controls, minimize unnecessary data collection, document decision criteria, and audit outcomes for unfair or discriminatory effects. An algorithmically shortest route may not be socially appropriate if it directs traffic through unsafe neighborhoods or violates access restrictions. Technical correctness does not remove the need for human oversight.

10. Contemporary Developments

Modern applications use graph databases, knowledge graphs, graph neural networks, and streaming graph analytics. Graph databases store relationships as first-class records and support queries involving paths and neighborhood patterns. Knowledge graphs connect entities with labeled, often directed relationships. Graph neural networks learn from both vertex attributes and graph structure.

These technologies do not replace fundamental algorithms. Traversal, connectivity, shortest paths, and cycle detection remain essential for interpreting data, designing query engines, validating models, and explaining results. In AI systems, graph-based explanations can help identify which relationships contributed to a prediction, although explanations must still be evaluated for completeness and fairness.

Best-Practice Checklist

• Define whether edges are directed or undirected.
• Specify the meaning and units of weights.
• Choose adjacency lists for most sparse graphs.
• Use BFS for unweighted shortest paths.
• Use Dijkstra only when edge weights are nonnegative.
• Use Bellman–Ford when negative edges may occur.
• Distinguish shortest-path problems from MST problems.
• Detect cycles before attempting topological ordering.
• Record predecessors when paths must be reconstructed.
• Test disconnected, cyclic, empty, and malformed inputs.
• Protect sensitive graph data and audit high-impact decisions.

Chapter Summary

Graphs model relationships using vertices and edges. They may be directed, undirected, weighted, labeled, sparse, or dense. Adjacency matrices provide constant-time edge tests but require quadratic memory; adjacency lists use memory proportional to vertices and edges and are usually best for sparse graphs.

BFS explores layers and finds shortest paths in unweighted graphs. DFS supports systematic exploration, component detection, cycle detection, and topological ordering. Dijkstra’s algorithm solves single-source shortest paths with nonnegative weights, Bellman–Ford permits negative edges, and Floyd–Warshall computes all-pairs shortest paths. Kruskal’s and Prim’s algorithms construct minimum spanning trees, which minimize total connection cost rather than individual route cost. Topological ordering applies only to directed acyclic graphs. Effective graph engineering also requires careful validation, complexity analysis, privacy protection, and awareness of application-specific constraints.

Key Terms

Graph: A structure consisting of vertices and edges.

Vertex: An individual node or object in a graph.

Edge: A connection between two vertices.

Directed graph: A graph whose edges have direction.

Undirected graph: A graph whose edges represent two-way relationships.

Weighted graph: A graph whose edges have numerical values.

Labeled graph: A graph whose vertices or edges carry descriptive attributes.

Degree: The number of edges incident to an undirected vertex.

Path: A sequence of vertices connected by edges.

Cycle: A closed path that returns to its starting vertex.

Adjacency matrix: A two-dimensional table recording pairwise adjacency or weights.

Adjacency list: A collection of neighbor lists, one for each vertex.

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

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

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

Shortest path: A minimum-cost path between vertices.

Minimum spanning tree: A least-weight tree connecting every vertex of a connected undirected graph.

Topological ordering: A dependency-respecting order of a directed acyclic graph.

Relaxation: The operation of improving a tentative shortest-path distance.

Disjoint-set union: A structure for maintaining dynamically merging sets and detecting cycles.

Review Questions

Short Answer Questions

1. What is the difference between a directed and an undirected graph?
2. Why are adjacency lists usually suitable for sparse graphs?
3. What property of edge weights is required by Dijkstra’s algorithm?
4. What does a topological ordering represent?
5. State one difference between a shortest-path tree and a minimum spanning tree.

Long Answer Questions

1. Explain BFS and DFS, including their data structures, applications, and time complexities.
2. Compare adjacency matrices, adjacency lists, and edge lists for different graph densities and operations.
3. Describe Dijkstra’s, Bellman–Ford, and Floyd–Warshall algorithms and identify when each should be used.
4. Explain Kruskal’s and Prim’s minimum-spanning-tree algorithms and the role of cycle detection.
5. Explain how directed and undirected cycle detection differ.

Analytical / Application Questions

1. Design a graph model for a university course-prerequisite system. Identify the vertex and edge types, choose a representation, and explain how cycles would be detected.
2. A logistics network has nonnegative travel times but is sparse and contains thousands of locations. Select an algorithm for one-source routing and justify the representation and complexity.
3. A company wants both the cheapest total fiber installation plan and the fastest route between offices. Explain why these are different graph problems and recommend algorithms for each.

Multiple Choice Questions with Answers

Question 1

Which representation generally requires O(n²) memory for a graph with n vertices?

A. Adjacency matrix

B. Adjacency list

C. Edge list

D. Disjoint-set forest

Correct Answer: A. Adjacency matrix

Question 2

Which traversal finds minimum-edge paths from a source in an unweighted graph?

A. Depth-first search

B. Breadth-first search

C. Kruskal’s algorithm

D. Floyd–Warshall only

Correct Answer: B. Breadth-first search

Question 3

Dijkstra’s algorithm is guaranteed to be correct when edge weights are:

A. All negative

B. Nonnegative

C. All distinct

D. Equal to one

Correct Answer: B. Nonnegative

Question 4

What does an edge to a currently explored ancestor indicate during directed DFS?

A. A spanning tree

B. A negative edge

C. A directed cycle

D. A topological ordering

Correct Answer: C. A directed cycle

Question 5

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

A. n − 1

B. n

C. 2n

D. n²

Correct Answer: A. n − 1

Question 6

Which algorithm is designed to support negative edge weights, provided there is no reachable negative cycle?

A. BFS

B. Dijkstra’s algorithm

C. Bellman–Ford

D. Prim’s algorithm

Correct Answer: C. Bellman–Ford

Question 7

A topological ordering exists exactly when a directed graph is:

A. Complete

B. Acyclic

C. Undirected

D. Weighted

Correct Answer: B. Acyclic

Question 8

For edges A→B with weight 4, A→C with weight 1, and C→B with weight 2, what is the shortest distance from A to B?

A. 1

B. 2

C. 3

D. 4

Correct Answer: C. 3

Question 9

Which algorithm computes shortest paths between every pair using a three-level intermediate-vertex recurrence?

A. Floyd–Warshall

B. Kruskal

C. BFS

D. Kahn’s algorithm

Correct Answer: A. Floyd–Warshall

Question 10

What is the main purpose of a disjoint-set union structure in Kruskal’s algorithm?

A. To sort vertices alphabetically

B. To detect whether adding an edge creates a cycle

C. To calculate vertex labels

D. To store all-pairs distances

Correct Answer: B. To detect whether adding an edge creates a cycle