Graphs and Network Models

Introduction

A graph is a mathematical and computational model for representing relationships. Unlike a linear data structure, in which elements usually have one predecessor and one successor, a graph allows an object to be connected to many other objects. This makes graphs suitable for modelling road systems, computer networks, social relationships, web pages, project dependencies, airline routes, and communication infrastructure.

In application development, graphs are valuable because they separate the structure of a problem from the particular algorithm used to solve it. Once a network has been represented as a graph, developers can search it, determine whether locations are reachable, find efficient routes, detect disconnected components, and analyse dependencies.

This chapter introduces graph terminology, representations, traversal algorithms, shortest-path concepts, and connectivity analysis. Examples use concepts transferable to both Python and Java.

Learning Objectives

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

• define vertices, edges, paths, cycles, degree, and connectivity;
• distinguish directed, undirected, weighted, and unweighted graphs;
• represent graphs using adjacency matrices and adjacency lists;
• apply depth-first search (DFS) and breadth-first search (BFS);
• select an appropriate shortest-path method;
• analyse time and space complexity;
• solve a practical network problem using graph techniques; and
• identify limitations, data-quality risks, and responsible uses of network models.

1. Graph Fundamentals

A graph is commonly written as G = (V, E), where:

• V is a finite set of vertices, also called nodes;
• E is a set of edges connecting pairs of vertices.

For an undirected graph, an edge connects two vertices symmetrically. If an edge joins A and B, movement is possible from A to B and from B to A. In a directed graph, an edge has an origin and a destination. A directed edge from A to B does not necessarily permit movement from B to A.

An edge may have a weight representing distance, time, cost, capacity, risk, or another measurable quantity. A graph without edge weights is unweighted. In an unweighted graph, each edge is normally treated as having equal cost.

Important terminology

A vertex is adjacent to another vertex if an edge directly connects them. The degree of an undirected vertex is the number of incident edges. In a directed graph, in-degree counts incoming edges and out-degree counts outgoing edges.

A walk is a sequence of vertices in which consecutive vertices are connected by edges. A path is a walk in which vertices are not repeated, although definitions sometimes allow a repeated endpoint for a closed path. A cycle is a path that returns to its starting vertex. A self-loop is an edge from a vertex to itself. Parallel edges are multiple edges joining the same pair of vertices.

A graph is simple if it has no self-loops or parallel edges. A connected undirected graph contains a path between every pair of vertices. A connected component is a maximal connected subgraph. In a directed graph, strong connectivity means every vertex can reach every other vertex following edge directions; weak connectivity ignores directions when testing connection.

A graph is sparse when it contains relatively few edges compared with the maximum possible number. It is dense when it contains many edges. For a simple undirected graph with n vertices, the maximum number of edges is:

This formula assumes that there are no self-loops, no parallel edges, and that each unordered pair of vertices can have at most one edge. For a simple directed graph without self-loops, the corresponding maximum is n(n − 1).

2. Common Graph Models

A tree is a connected, undirected, acyclic graph. A tree with n vertices has exactly n − 1 edges. This property is useful in file systems, organisational hierarchies, and spanning-network design. A forest is a collection of disjoint trees.

A directed acyclic graph (DAG) is a directed graph with no directed cycle. DAGs are especially useful for course prerequisites, build systems, workflow scheduling, and version-control dependencies. A topological ordering of a DAG is an ordering in which every directed edge points from an earlier vertex to a later vertex.

3. Representing Graphs in Programs

Adjacency matrix

An adjacency matrix is a two-dimensional array. For vertices numbered 0 through n − 1, entry A[i][j] records whether an edge from vertex i to vertex j exists. In a weighted graph it may contain the edge weight; a special value such as infinity indicates no edge.

The matrix requires O(n²) storage and tests whether a particular edge exists in O(1) time. It is appropriate for dense graphs or applications that frequently ask whether two specific vertices are directly connected. Its main disadvantage is wasted space when the graph is sparse.

Adjacency list

An adjacency list stores, for each vertex, a collection of its neighbours. For a weighted graph, each neighbour is stored with its weight. The storage requirement is O(V + E), where V = |V| and E = |E|. This is normally the preferred representation for sparse real-world networks.

A Python representation might be:

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("D", 5)],
    "C": [("A", 2), ("D", 1)],
    "D": [("B", 5), ("C", 1)]
}

For an undirected graph, each edge must normally be inserted twice. For example, an edge A–B is represented in both A's and B's neighbour lists. In Java, equivalent structures can be implemented with Map<String, List<Edge>>, where Edge stores a destination and weight.

The choice of representation is a design decision. A matrix offers predictable direct access, whereas a list supports efficient traversal of existing neighbours. Developers should also consider whether vertices are identified by integers, strings, database keys, or objects.

4. Graph Traversal

Traversal systematically visits vertices. A visited set is essential because a graph may contain cycles. Without it, an algorithm could revisit vertices indefinitely.

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. The recursive version is conceptually simple:

def dfs(graph, start):
    visited = set()
    order = []

    def visit(vertex):
        if vertex in visited:
            return
        visited.add(vertex)
        order.append(vertex)
        for neighbour, _ in graph.get(vertex, []):
            visit(neighbour)

    visit(start)
    return order

DFS is useful for connected-component detection, cycle detection, maze exploration, dependency analysis, and topological sorting. With an adjacency list, its time complexity is O(V + E) because each reachable vertex and edge is processed at most a constant number of times. Its auxiliary space is O(V) for the visited set and recursion or stack.

Recursive DFS has a practical limitation: a very deep graph may exceed a language's call-stack limit. An iterative implementation using an explicit stack avoids dependence on recursion depth.

Breadth-first search

Breadth-first search explores all vertices at distance one edge from the start, then all vertices at distance two, and so on. It uses a queue. Marking a vertex visited when it is enqueued prevents duplicate insertion.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        vertex = queue.popleft()
        order.append(vertex)
        for neighbour, _ in graph.get(vertex, []):
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return order

BFS also runs in O(V + E) time with adjacency lists and uses O(V) additional space. It is the correct basic method for finding a minimum-edge path in an unweighted graph. If each edge represents one bus stop, for example, BFS finds a route with the fewest stops, not necessarily the shortest physical distance.

DFS and BFS comparison

Traversal order is not always unique. It depends on the order in which neighbours appear in the representation. The set of reachable vertices is independent of neighbour ordering, but the reported sequence may differ.

5. Shortest-Path Concepts

A shortest path minimises the sum of edge weights among all paths between a source and a destination. For a path P with edges e₁, e₂, …, eₖ, its total cost is:

Here, w(eᵢ) is the weight of edge eᵢ. The sum is meaningful only when the weights measure a compatible quantity, such as minutes or kilometres. Combining minutes and monetary cost without a stated conversion is invalid.

Choosing an algorithm

• BFS: unweighted graphs or graphs in which every edge has equal cost.
• Dijkstra's algorithm: non-negative edge weights. It is unsuitable when negative edges exist.
• Bellman–Ford: permits negative edge weights and can detect a reachable negative cycle, but is slower.
• Floyd–Warshall: computes all-pairs shortest paths; useful for smaller dense graphs.
• A5: uses a heuristic and is common in route planning when a suitable, admissible heuristic is available.

Dijkstra's algorithm

Dijkstra's algorithm maintains the best currently known distance from the source to each vertex. It repeatedly selects the unsettled vertex with the smallest tentative distance and relaxes its outgoing edges. Relaxation tests whether reaching a neighbour through the selected vertex is cheaper:

Here, d[u] is the known distance to u, w(u,v) is the weight from u to v, and d[v] is the current estimate for v. The method assumes every edge weight is non-negative. With a binary heap and adjacency list, its typical complexity is O((V + E) log V).

The algorithm should also store a predecessor for each updated vertex. Following predecessors backward from the destination reconstructs the actual route. A priority queue may contain outdated entries; therefore, an implementation should ignore an entry whose distance is greater than the current recorded distance.

Worked shortest-path example

Consider four locations and travel times: A–B = 4 minutes, A–C = 2 minutes, C–D = 1 minute, and B–D = 5 minutes. The candidate route A–B–D costs 9 minutes. The route A–C–D costs 3 minutes. Therefore, the shortest route from A to D is A–C–D with total cost 3 minutes.

This conclusion depends on the assumptions that travel times are additive, fixed during the analysis, and non-negative. If traffic changes over time, a static weighted graph may no longer represent the system accurately.

6. Connectivity and Network Analysis

Connectivity analysis asks whether and how parts of a network are linked. Running DFS or BFS from one vertex in an undirected graph visits exactly its connected component. To find all components, repeatedly start a traversal from an unvisited vertex. The number of traversal starts is the number of components.

In directed graphs, reachability is directional. A website may link to another website without receiving a link back. Strongly connected components identify maximal groups in which every vertex can reach every other vertex. Algorithms such as Kosaraju's and Tarjan's can find them in O(V + E) time, although their full implementation is beyond the essential requirements of this certificate course.

A bridge is an edge whose removal increases the number of connected components. An articulation vertex is a vertex whose removal disconnects a connected graph. These concepts help identify single points of failure in communication, transport, and utility networks.

A network may remain connected while still being fragile. For example, if many routes pass through one articulation vertex, a local failure can have a large effect. Thus, connectivity is a structural property, not a complete measure of resilience, capacity, or service quality.

7. An Illustrative Case: Campus Shuttle Routing

Background

A college operates shuttle stops A, B, C, D, E, and F. The transport team wants to answer two questions: which stops can be reached from the administration building, and what route minimises travel time to the technology centre?

Problem

The road network is represented by weighted, undirected edges:

Suppose A is the administration building and F is the technology centre.

Analysis

A BFS traversal can establish reachability when the question is simply whether a route exists. Starting at A, all six stops are eventually visited, so the network is connected. However, BFS is not appropriate for minimum travel time because the edges have different weights.

Dijkstra's algorithm is appropriate because all travel times are non-negative. Important candidate totals include:

• A–C–D–E–F: 2 + 1 + 3 + 2 = 8 minutes;
• A–C–E–F: 2 + 7 + 2 = 11 minutes;
• A–B–D–E–F: 4 + 5 + 3 + 2 = 14 minutes.

The minimum identified route is A–C–D–E–F at 8 minutes. The predecessor map is sufficient to reconstruct this route in software.

Approach and solution

The application should store the network as an adjacency list. It should validate that each stop exists, reject negative travel times when using Dijkstra's algorithm, and distinguish an unreachable destination from a destination with a very large but finite cost. A priority queue should be used for efficient selection of the next stop.

If the application reports routes to passengers, it should also record the timestamp of the estimate. Travel times are not permanent facts; they may depend on traffic, weather, road closures, and service schedules.

Outcome and learning points

The case demonstrates that different questions require different algorithms. BFS answers minimum-hop questions in unweighted networks, whereas Dijkstra answers minimum-cost questions under non-negative, additive weights. Connectivity analysis alone does not identify the best route, and a shortest route may not be the safest, most accessible, or highest-capacity route.

8. Implementation and Engineering Practices

A robust graph application should:

1. define precisely what vertices and edges mean;
2. document whether edges are directed or undirected;
3. validate identifiers and reject malformed records;
4. select a representation appropriate to density and operations;
5. use a visited set in traversal algorithms;
6. choose shortest-path algorithms according to weight assumptions;
7. preserve predecessor information when users need an actual path;
8. test empty graphs, isolated vertices, cycles, duplicate edges, and unreachable destinations; and
9. measure performance using realistic graph sizes.

For large graphs, adjacency lists are usually more memory-efficient. For repeated shortest-path queries, preprocessing or specialised indexes may be worthwhile. For graphs whose edges change frequently, the application must define whether results are recomputed immediately or cached for a limited period.

Testing should include invariants. For example, every reported path should begin at the requested source, end at the requested destination, contain valid consecutive edges, and have a reported cost equal to the sum of its edge weights. Automated tests should verify both successful routes and failure conditions.

9. Limitations, Ethics, and Contemporary Use

A graph model is an abstraction. It omits information that is not represented in vertices, edges, attributes, or weights. A road graph may omit accessibility, congestion, safety, weather, or social conditions. A social graph may reduce complex human relationships to simplistic links.

Network data can contain personal information. Social, communication, and location graphs should be collected lawfully, minimised to the necessary purpose, protected through access controls, and retained only as long as justified. Analysts should consider consent, re-identification risk, discrimination, and the consequences of ranking or excluding individuals.

AI systems increasingly use graph data for recommendation, fraud detection, knowledge representation, and supply-chain analysis. Graph neural networks can learn from node features and relationships, but their predictions remain dependent on data quality and modelling assumptions. They do not eliminate the need for explainability, validation, bias assessment, and human oversight.

Shortest-path output should not automatically be treated as a recommendation. A route that minimises time might pass through a restricted area or expose a vulnerable person to risk. Professional systems should expose important assumptions and allow domain experts to review high-impact decisions.

Chapter Summary

Graphs model entities and relationships using vertices and edges. They may be directed or undirected, weighted or unweighted, sparse or dense. Adjacency matrices provide constant-time edge lookup but require quadratic storage; adjacency lists are generally efficient for sparse networks. DFS explores deeply using a stack or recursion, while BFS explores by levels using a queue. Both run in O(V + E) time with adjacency lists. BFS finds minimum-edge paths in unweighted graphs. Dijkstra's algorithm finds minimum-weight paths when all weights are non-negative; other algorithms are required for negative edges or all-pairs analysis. Connectivity, components, bridges, and articulation vertices help evaluate network structure and vulnerability. Effective graph applications depend not only on algorithms but also on valid modelling, appropriate assumptions, careful testing, privacy protection, and responsible interpretation.

Key Terms

Graph: A structure consisting of vertices and edges.

Vertex: An entity or node in a graph.

Edge: A connection between two vertices.

Directed graph: A graph whose edges have origin and destination.

Undirected graph: A graph whose relationships are symmetric.

Weight: A numerical value attached to an edge.

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

Path: A sequence of connected vertices, normally without repetition.

Cycle: A path that returns to its starting vertex.

Connected component: A maximal connected part of an undirected graph.

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

Adjacency list: A representation storing each vertex's neighbours.

DFS: Depth-first search using a stack or recursion.

BFS: Breadth-first search using a queue.

Relaxation: Updating a distance estimate when a cheaper route is found.

Dijkstra's algorithm: A shortest-path algorithm for non-negative edge weights.

DAG: A directed acyclic graph.

Bridge: An edge whose removal increases the number of components.

Articulation vertex: A vertex whose removal disconnects a graph.

Reachability: The ability to travel from one vertex to another according to edge rules.

Review Questions

Short Answer Questions

1. What are the two fundamental components of a graph?
2. Why is a visited set required in DFS and BFS?
3. State one advantage of an adjacency list over an adjacency matrix.
4. Under what condition is BFS suitable for shortest-path calculation?
5. What restriction does Dijkstra's algorithm place on edge weights?

Long Answer Questions

1. Compare directed and undirected graphs, giving two practical examples of each.
2. Explain DFS and BFS, including their data structures, typical applications, and complexity.
3. Describe how Dijkstra's algorithm uses relaxation and predecessor information.
4. Compare adjacency matrices and adjacency lists for sparse and dense graphs.
5. Explain connected components, bridges, and articulation vertices in network analysis.

Analytical / Application Questions

1. A delivery network has non-negative travel times but several alternative routes. Which representation and shortest-path algorithm would you choose, and why?
2. A social network contains 100,000 users but relatively few relationships per user. Explain how you would represent it and identify disconnected groups.
3. A route planner reports the fewest road segments rather than the shortest travel time. Diagnose the likely algorithmic choice and propose a correction.

Multiple Choice Questions with Answers

Question 1

Which representation usually requires O(V + E) storage for a sparse graph?

A. Adjacency list

B. Adjacency matrix

C. Sorted array of all possible pairs

D. Two-dimensional bitmap

Correct Answer: A. Adjacency list

Question 2

Which data structure is normally used by breadth-first search?

A. Stack

B. Queue

C. Priority queue only

D. Hash table only

Correct Answer: B. Queue

Question 3

What does BFS guarantee in an unweighted graph?

A. A minimum-weight path when weights are negative

B. A path with the fewest edges

C. A path containing the fewest vertices in every weighted graph

D. A path that visits every vertex

Correct Answer: B. A path with the fewest edges

Question 4

Which condition is required for standard Dijkstra's algorithm?

A. All edge weights are negative

B. The graph must be complete

C. All edge weights are non-negative

D. The graph must be acyclic

Correct Answer: C. All edge weights are non-negative

Question 5

A simple undirected graph has 5 vertices. What is the maximum number of edges?

A. 5

B. 10

C. 15

D. 20

Correct Answer: B. 10

Question 6

What is the principal exploration pattern of DFS?

A. It explores one branch deeply before backtracking

B. It always selects the lowest-weight edge

C. It visits vertices in increasing numeric order

D. It explores all vertices simultaneously

Correct Answer: A. It explores one branch deeply before backtracking

Question 7

In the campus case, what is the travel time of route A–C–D–E–F?

A. 6 minutes

B. 7 minutes

C. 8 minutes

D. 11 minutes

Correct Answer: C. 8 minutes

Question 8

What is a bridge in an undirected graph?

A. A vertex with the largest degree

B. An edge whose removal increases the number of components

C. Any edge in a cycle

D. A directed edge with equal endpoints

Correct Answer: B. An edge whose removal increases the number of components

Question 9

Which graph structure is always connected and acyclic?

A. Tree

B. Complete graph

C. Directed cycle

D. Multigraph

Correct Answer: A. Tree

Question 10

Why should a shortest-path application store predecessor information?

A. To count the number of vertices in the graph

B. To reconstruct the actual route

C. To convert a directed graph into an undirected graph

D. To guarantee that all weights are positive

Correct Answer: B. To reconstruct the actual route