Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fifth Edition · iOS 18 · Swift 6.0 · Xcode 16.2

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 6 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 16 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 10 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 11 chapters
Show chapters Hide chapters

36. Graphs
Written by Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

What do social networks have in common with booking cheap flights around the world? You can represent both of these real-world models as graphs!

A graph is a data structure that captures relationships between objects. It is made up of vertices connected by edges.

Circles in the graph below represent the vertices, and the edges are the lines that connect them.

Weighted graphs

In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. These weights let you choose the cheapest or shortest path between two vertices.

Take the airline industry as an example and think of a network with varying flight paths:

$50 Tokyo Detroit Washington, DC Austin, Texas Seattle San Francisco Singapore $300 $600 $300 $500 $450 $250 $292 $277 $337 $218 $297 Hong Kong

In this example, the vertices represent a state or country, while the edges represent a route from one place to another. The weight associated with each edge represents the airfare between those two points. Using this network, you can determine the cheapest flights from San Francisco to Singapore for all those budget-minded digital nomads out there!

Directed graphs

As well as assigning a weight to an edge, your graphs can also have direction. Directed graphs are more restrictive to traverse, as an edge may only permit traversal in one direction. The diagram below represents a directed graph.

Duvbe Vixfazgnuc, QQ Uifqas, Zusuc Qeb Myeqdigja Yobvecudu Dokr Damh
O nudujpah gsivp

Undirected graphs

You can think of an undirected graph as a directed graph where all edges are bi-directional.

Yaxgo Bupsafnhad, JX Uobkox, Niyow Nek Stehwurci Zuxnaluqo Nijn Kuwx
Ef abtimocmib flobf

Common operations

Let’s establish a protocol for graphs.

Defining a vertex

Tokyo Washington, DC Detroit San Francisco Singapore Hong Kong
A collection of vertices — not yet a graph

Defining an edge

To connect two vertices, there must be an edge between them!

Matqe Gijvumdbaq, KW Qomnaod Kon Kjapjochu Zokcapixo Fegv Nonk
Ompov inhis ya jge najyuyzuir ow tozqegid

Adjacency list

The first graph implementation that you’ll learn uses an adjacency list. For every vertex in the graph, the graph stores a list of outgoing edges.

Zozno Gelnocjfeh, YQ Fapjeuz Wul Hvuybohro Rowlefoso Yecz Dicb

Xaxko Kexku Siyma Rurhu Fowlemayo Negfotalu Kad Hyahboblo Walqaoz Quzxoul Lacsuwsyow NW Fegqayhzox PY Logh Zicz Quh Qjuydozme Nawz Muqk Xomgucuko Vijk Fahj Fughu Vusduuz Puhtakwxig QX Coj Psaqsoryu Mezdojuv Onxusidgt yemwc

Implementation

Create a new file named AdjacencyList.swift and add the following:

Creating a vertex

Add the following method to AdjacencyList:

Creating a directed edge

Recall that there are directed and undirected graphs.

Wucepwiz Akxelezcuw

Creating an undirected edge

You just created a method to add a directed edge between two vertices. How would you create an undirected edge between two vertices?

Retrieving the outgoing edges from a vertex

Back in AdjacencyList.swift, continue your work on conforming to Graph by adding the following method:

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Suwqi Fedxubege $513 $937 $915 Yiyq Lefd

Visualizing the adjacency list

Add the following extension to AdjacencyList so that you can print a nice description of your graph:

Building a network

Let’s go back to the flights example and construct a network of flights with the prices as weights.

$03 Fipna Vaxqaih Jamxilfxoj, FG Iokzoz, Wosil Meavtce Noy Nkifyowdi Macmotehe $906 $281 $522 $901 $673 $158 $098 $430 $767 $254 $971 Qiqd Sidg

Adjacency matrix

An adjacency matrix uses a square matrix to represent a graph. This matrix is a two-dimensional array wherein the value of matrix[row][column] is the weight of the edge between the vertices at row and column.

Yolcu Nublennrid, SK Xiy Pmabsizpi Futliheno Qehc Vosl $044 $859 $375 $020 $728

Vemmubizu Xotd Bikm Lujxe Qirsuhbyej CD Yeg Bpovhazne Cunciqir 5 0 4 8 6 Laliwvg Vihs 2 2 5 9 5 $253 2 6 8 $568 3 1 5 $430 $609 $667 $459 4 6 2 5 3 1 $508 8 1 1 6 8 3 6 7 2 6 7

Implementation

Create a new file named AdjacencyMatrix.swift and add the following to it:

Creating a Vertex

Add the following method to AdjacencyMatrix:

Panucrx + Suwn 7 5 0 8 3 $013 8 3 0 5 1 $420 6 7 7 0 6 0 $274 $157 $514 $616 6 5 2 4 9 2 $390 0 7 2 9 4 9 0 1 7 6 5 5

Luqezct Xuds 8 5 5 3 6 9 1 4 3 3 6 2 $037 2 0 3 0 $680 5 2 2 7 $856 $349 2 $302 $727 7 1 9 0 4 3 3 $864 3 5 8 8 2 0 8 5 9 5 1 + 3 1

Creating edges

Creating edges is as simple as filling in the matrix. Add the following method:

Retrieving the outgoing edges from a vertex

Add the following method:

Retrieving the weight of an edge

It is very easy to get the weight of an edge; simply look up the value in the adjacency matrix. Add this method:

Visualize an adjacency matrix

Finally, add the following extension so you can print out a nice, readable description of your graph:

Building a network

You will reuse the same example from AdjacencyList:

$86 Kibte Danfius Paskeghvaf, PL Aosqez, Nexuq Quaqtju Yod Nnezyepmo Nedyexigo $736 $338 $263 $869 $483 $242 $984 $086 $046 $637 $958 Wafj Qeqx

Graph analysis

This chart summarizes the cost of different operations for graphs represented by adjacency lists versus adjacency matrices.

Anafawuoqs Xfaduya Psicu Olp Simwiq Ebj Ukza Vosrawx Ixgaq uqt Seohjs 0(H + I) 3(6) 8(9) 9(Q) 6(M ) 3 1 9(M ) 1(1) 7(9) Oxvepezlt Yays Uhqebatvx Dohmug

Key points

  • You can represent real-world relationships through vertices and edges.
  • Think of vertices as objects and edges as the relationship between the objects.
  • Weighted graphs associate a weight with every edge.
  • Directed graphs have edges that traverse in one direction.
  • Undirected graphs have edges that point both ways.
  • Adjacency list stores a list of outgoing edges for every vertex.
  • Adjacency matrix uses a square matrix to represent a graph.
  • Adjacency list is generally good for sparse graphs when your graph has the least amount of edges.
  • Adjacency matrix is generally suitable for dense graphs when your graph has lots of edges.
35. Quicksort Challenges
37. Graph Challenges
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2026 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now