Graph Theory Fundamentals

Modeling Relationships

At their core, graphs are structures used to model connections. Think of a social network: people are the points, and their friendships are the lines connecting them. In computer science, we call these points vertices (or nodes) and the connecting lines edges.

This simple model is incredibly powerful. It can represent anything from city roadmaps to the dependencies in a software project. To work with these relationships in code, we need a way to represent them. Let's look at how you'd build a graph structure in Swift.

Graph Representations in Swift

There are two main ways to represent a graph in code: an adjacency list or an adjacency matrix. Each has its own strengths and is suited for different kinds of problems.

An adjacency list is often the go-to choice in Swift because of its flexibility and memory efficiency for many real-world scenarios.

An adjacency list typically uses a dictionary. Each key in the dictionary is a vertex, and its value is an array of the vertices it's connected to. It's like a phone's contact list, where each person has a list of their friends.

// Using an Adjacency List
struct Graph<T: Hashable> {
    var adjacencyList: [T: [T]] = [:]

    mutating func addVertex(_ vertex: T) {
        if adjacencyList[vertex] == nil {
            adjacencyList[vertex] = []
        }
    }

    mutating func addEdge(from source: T, to destination: T) {
        // Assuming a directed graph for now
        adjacencyList[source]?.append(destination)
    }
}

var socialNetwork = Graph<String>()
socialNetwork.addVertex("Alice")
socialNetwork.addVertex("Bob")
socialNetwork.addEdge(from: "Alice", to: "Bob") 
// Alice is connected to Bob

The other method is an adjacency matrix. This uses a two-dimensional array. If you have $N$ vertices, you create an $N \times N$ matrix. A value of 1 at matrix[i][j] means there's an edge from vertex i to vertex j. A 0 means there isn't.

// Adjacency Matrix requires mapping vertices to indices
enum Node: Int {
    case Alice = 0
    case Bob = 1
    case Charlie = 2
}

let vertexCount = 3
var adjacencyMatrix = Array(repeating: Array(repeating: 0, count: vertexCount), count: vertexCount)

// Add an edge from Alice (0) to Bob (1)
adjacencyMatrix[Node.Alice.rawValue][Node.Bob.rawValue] = 1

Choosing between them involves a trade-off. Adjacency lists are great for —graphs with many vertices but relatively few edges. Adjacency matrices shine when you need to check for an edge between two specific vertices instantly, but they can use a lot of memory for large, sparse graphs.

Feature	Adjacency List	Adjacency Matrix
Memory Usage	Proportional to vertices + edges	Proportional to vertices squared ( $V^2$ )
Add a vertex	Efficient	Inefficient (requires resizing the matrix)
Add an edge	Efficient	Efficient
Check for an edge	Less efficient (must scan a list)	Very efficient (direct lookup)

One-Way and Two-Way Streets

Edges can have a direction. A friendship on Facebook is a two-way street: if you're friends with someone, they're friends with you. This is an undirected graph. But on Twitter, you can follow someone without them following you back. That's a directed graph.

This distinction matters for your implementation. In an undirected graph, adding an edge from A to B means you must also add one from B to A in your adjacency list or matrix to represent the two-way relationship.

Directed Acyclic Graphs (DAGs)

One of the most useful types of graphs in software development is the Directed Acyclic Graph, or DAG. The name tells you everything: its edges are directed (one-way), and it's acyclic, meaning there are no paths that loop back to the starting vertex. You can't start at one point, follow the arrows, and end up where you began.

DAGs are perfect for modeling dependencies or sequences of steps. Think about getting dressed: you have to put on your socks before your shoes. This is a dependency. A build system in Xcode works the same way; it compiles source files before linking them into an app. These workflows are naturally modeled as DAGs.

Because they have a clear start and finish with no loops, DAGs allow us to determine a valid order for performing tasks. This process is known as a and is fundamental to task scheduling and dependency resolution.

Connectivity and Pathfinding

Once you've represented a system as a graph, you can start asking interesting questions. Is there a path from vertex A to vertex B? What is the shortest path? These are questions of connectivity and pathfinding.

For example, in a network of computers, pathfinding helps find the most efficient route for data to travel. In a dependency graph, checking for connectivity can tell you if changing one module will affect another.

This area of graph theory is where many famous algorithms live. Algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS) are used to explore a graph and find paths. More advanced methods, like , are used to find the shortest path in a graph where edges have different "weights" or costs.

Quiz Questions 1/6

In graph theory, what are the two fundamental components that make up a graph?

Quiz Questions 2/6

You are modeling a large social network with millions of users, but where the average user has only a few hundred connections. Which graph representation is generally most memory-efficient for this scenario?

Understanding these fundamental graph concepts is the first step. By translating these abstract ideas into Swift types, you gain a powerful toolkit for modeling and solving a wide range of complex problems.

Applied Discrete Mathematics for Software Engineering