8 8 8

>>

Week 4: Graph Data Structures

61 61 61 61
-4Week 4 -4 -4 -4
31 You Should Know
Nerds 31 31 31
Graph6 2
Definitions 62 62 62
Graphs 91 91 91
28
Properties of Graphs 28 28
Exercise: Number of Edges
Graph Terminology
Graph Data Structures
Graph Representations
Array-of-edges Representation
61 Cost Analysis
61 61 61
-4 -4 -4 -4
31 31
Exercise: Array-of-edges Representation 31 31
62
Adjacency Matrix Representation
Exercise: Show Graph
62 62 62
Exercise:
91 91 91
28
Adjacency List Representation
28 28
Exercise:
Comparison of Graph Representations
Graph Abstract Data Type
Graph ADT
61 Exercise: Graph ADT Client 61 61 61
-4 Graph ADT (Array of Edges) -4 -4 -4
31
Graph ADT (Adjacency Matrix) 31 31 31
62
Exercise: Checking Neighbours (i) 62 62 62
91
Graph ADT (Adjacency List) 91 91
2
Exercise: Checking Neighbours (ii) 2 2
 8 8 8
Problems on Graphs
Problems on Graphs
Graph Algorithms
Graph Traversal
61 Finding a Path
61 61 61
-4
Depth-first Search
-4 -4 -4
31
Exercise: Depth-first Traversal (i) 31 31 31
62
Exercise: Depth-first Traversal (ii) 62 62 62
91
Exercise: Depth-first Traversal (iii) 91 91
28
Breadth-first Search
Exercise: Breadth-first Traversal
28 28
Other DFS Examples
Exercise: Buggy Cycle Check
Computing Connected Components
Exercise: Connected components
61 Hamiltonian and Euler Paths 61 61 61
-4
Hamiltonian Path and Circuit -4 -4 -4
31
Exercise: Hamiltonian Path 31 31 31
62
Euler Path and Circuit 62 62 62
91
Exercise: Euler Paths and Circuits 91 91
Summary 28 28 28
COMP9024 24T1 ♢Dynamic Data Structures♢ [0/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

∧ >>
61❖ Week 4 61 61 61
-4 -4 -4 -4
31 31 31 31
6
Things to2Note
62 62 62
91 … 91 91
28 28 28
Online help sessions: check the course homepage for up-to-date timetable
⇒ start weekly assessments *early* - tutors can help you better if you do
Mid term - Moodle quiz, Week 6 Thursday 2pm-3pm, details to follow
61 61 61 61
In-This
43 Lecture … -4
31
-4
31
-4
31
16 62 62 62
2 91 structures (Slides, [S] Ch. 17.1-17.5)
Graph data 91 91
28 28 28
Graph traversal (Slides, [S] Ch. 17.7, 18.1-18.3, 18.7)

Coming Up …
61 6 61 61
- Algorithms on graphs ([S]1Ch.
43 - 19-22)43 -4 -4
16 16 31 31
29 ♢Dynamic Data Structures♢29 62 62
COMP9024 24T1
12 12 [1/105] 91
2
 8 8 8

<< ∧ >>
61❖ Nerds You Should 61Know 61 61
-4 -4 -4 -4
31 31 31 31
62a series on famous computer scientists
The next in 62 … 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

6What
1- he invented affects 6your
1- life every single day …61- 61
43 43 43 -4
16 16 16 31
29 ♢Dynamic Data Structures♢29 29 62
COMP9024 24T1 [2/105]
12 12 12
 8 8 8

<< ∧ >>
61❖ Nerds You Should
61Know (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
Sir Tim Oxford CS Graduate (1976)
Berners-Lee Software engineer at CERN
61 61
Founder/Director of W3C at6MIT
1 (1994) 61
-4 - 4 - 43 -4
31 Inventing31the Web … 16 31
62 6 29hypertext
distributed 29 62
91 12 12
28 8
linking heterogeneous documents 8
universal naming scheme (URL)
transfer protocol (http)
61 61later apologised for initial6pair
1 61
of slashes ('//') in a web
-4 -4
address -4 -4
31 31 31 31
62 62 he should have defined6web
also thinks 2 addresses the 62
91 other way9round
12 (au.edu.unsw.cse) 912
28 8 8
Winner of the Turing Award in 2016

COMP9024 24T1 ♢Dynamic Data Structures♢ [3/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Nerds You Should 61Know (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Tim Berners-Lee's original diagram6of
2 the "Web" 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

(from his proposal document, 1989)

61 61
COMP9024 24T1 ♢Dynamic Data Structures♢ [4/105] 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Definitions
61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [5/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graphs 61 61 61
-4 -4 -4 -4
31 31 31 31
62
Many applications require 62 62 62
91 91 91
28 items (i.e. a set)
a collection of
28 28
relationships/connections between items

Examples:
61 6 1 6 1- 61
-4maps: items are cities, connections
-4 are roads
43 -4
3 3
16items are pages, connections
web: 16 are hyperlinks 16 31
29 29 29 62
12 you're familiar with 12
Collection types 12
8 8 8
arrays, lists … linear sequence of items

Graphs are more general … allow arbitrary connections

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [6/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graphs (cont) 61 61 61
-4 -4 -4 -4
31 31 31 31
A graph6G2= (V,E) 62 62 62
91 91 91
28
V is a set of vertices
28 28
E is a set of edges (subset of V×V)

Example:
61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [7/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graphs (cont) 61 61 61
-4 -4 -4 -4
31 31 31 31
62 Australian road distances
A real example: 62 62 62
91 91 91
Distance
2 8 2 8
Adelaide Brisbane Canberra Darwin Melbourne Perth Sydney
2 8
Adelaide - 2055 - 3051 732 2716 -
Brisbane 2055 - - 3429 1671 - 982

61Canberra - -
61- - 658
6- 1 309
61
-4
Darwin 3051 3429 - -4 - - 4049-4 - -4
31 732
Melbourne 1671 658
31 - - -
31873 31
62 62 62 62
Perth 91
2716 - - 404991 - - - 9 12
Sydney -
2 8 982 309 -
28873 - - 8

Notes: vertices are cities, edges are distance between cities, symmetric
61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [8/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graphs (cont) 61 61 61
-4 -4 -4 -4
31 31 31 31
62 representation of above:
Alternative 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [9/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graphs (cont) 61 61 61
-4 -4 -4 -4
31 31 31 31
62we might ask about a graph:
Questions 62 62 62
91 91 91
28 to get from item A to item
is there a way
28 B? 28
what is the best way to get from A to B?
which items are connected?
6Graph
1- algorithms are generally61 more complex than tree/list
61 ones: 61
43 -4 -4 -4
no1implicit order of items
3linked
(cf. 1 lists)
31 31
62 62 62 62
91 contain cycles
graphs may 91 91
28 28 28
concrete representation (i.e., a data structure) is less obvious
algorithm complexity depends on connection complexity

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [10/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Properties of Graphs 61 61 61
-4 -4 -4 -4
31 31 31 31
For now,6consider
29 62 and no direction, no weight
a graph with no (a,a) 62 62
12 91 91
28 written just as V and 2E.8
Terminology: |V|8and |E| (cardinality) normally

A graph with V vertices has at most V(V-1)/2 edges.

6The ratio E:V can vary considerably.

61 61 61
1- -4 -4 -4
43
if E1is closer to V , the graph3is1dense
2 31 31
62 62 62 62
91 to V, the graph is sparse
if E is closer 91 91
2
Example: web pages and hyperlinks8
8 2 28
Knowing whether a graph is sparse or dense is important

61 may affect choice of data

6 structures to represent6graph 61
1-
-4may affect choice of algorithms 1- -4
31 43 to process graph 43 31
62 16 16 62
9 29 29
COMP9024 24T11♢Dynamic
2 Data Structures♢ 12
[11/105] 12
 8 8 8

<< ∧ >>
61❖ Exercise: Number 61of Edges 61 61
-4 -4 -4 -4
31 31 31 31
6 a graph represent pairs
The edges2in
62of connected vertices. A6graph
2 with V has V 2 62
9 91 91
such pairs. 12 28 28
8
Consider V = {1,2,3,4,5} with all possible pairs:

E = { (1,1), (1,2), (1,3), (1,4), (1,5), (2,1), (2,2), …, (4,5), (5,5) }

61 61 61 61
-4 do we say that the maximum
Why -4 #edges is V(V-1)/2? -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [12/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
6…1 because 61 61 61
-4(v,w) and (w,v) denote the-same
4 edge
-4 -4
31 31 (in an undirected 31
graph) 31
62not consider loops (v,v) 62
we do 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [13/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Terminology 61 61 61
-4 -4 -4 -4
31 31 31 31
62 e that connects vertices
For an edge 62v and w 62 62
91 91 91
28
v and w are adjacent (neighbours)
28 28
e is incident on both v and w

Degree of a vertex v
61 6 1 v
6 1- 61
-4number of edges incident-on
43 43 -4
31 1 1 31
6
Synonyms: 29 6 29 62 62
1 1 91
28 edge = arc = link (Note:2some
vertex = node,
8 people use arc for directed2edges)
8

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [14/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Terminology 61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Path: a sequence of vertices where62 62 62
91 91 91
2has an edge to its predecessor
each vertex 8
28 28
Simple path: a path where
all vertices and edges are different
61 61 61 61
-4 a path
Cycle: -4 -4 -4
31 31 31 31
that6is2simple except last vertex6=2first vertex 62 62
91 91 91
Length of path2or
8 cycle: 28 28
#edges

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
COMP9024 24T1 ♢Dynamic Data Structures♢ [15/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Terminology 61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 graph
Connected 62 62 62
91 91 91
28 from each vertex to every
there is a path
28 other vertex 28
if a graph is not connected, it has ≥2 connected components

Complete graph KV
61 61 61 61
-4there is an edge from each-4vertex to every other vertex
-4 -4
31 31 31 31
62
in a complete 62
graph, E = V(V-1)/2 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91
COMP9024 24T1 ♢Dynamic Data Structures♢ [16/105] 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Terminology 61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Tree: connected (sub)graph with no6cycles
29 62 62
91 12 91
2 8 containing all vertices 8
Spanning tree: tree
28
Clique: complete subgraph

6Consider
1-
the following single
6 1-
graph: 61 61
43 43 -4 -4
16 16 31 31
29 29 62 62
12 12 91
8 8 28

61 61 61 61
-4 -4
This graph has 26 vertices, 33 edges, and 4 connected components -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
Note: The entire graph has no spanning tree; what is shown in green is a spanning tree of the third
connected component

61 61
COMP9024 24T1 ♢Dynamic Data Structures♢ [17/105] 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Terminology 61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 graph
Undirected 62 62 62
91 91 91
28
edge(u,v) = edge(v,u)
2
, no self-loops (i.e.8no edge(v,v))
28
Directed graph
edge(u,v) ≠ edge(v,u), can have self-loops (i.e. edge(v,v))
61 61 61 61
-4
Examples: -4 -4 -4
3 16 31 31 31
29 62 62 62
12 91 91
8 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91
COMP9024 24T1 ♢Dynamic Data Structures♢ [18/105]
91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Terminology 61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 of graphs …
Other types 62 62 62
91 91 91
2
Weighted graph8
28 28
each edge has an associated value (weight)
e.g. road map (weights on edges are distances between cities)
61 61 61 61
-4
Multi-graph -4 -4 -4
3 1
allow6
3 16 31 31
multiple edges between two vertices
2 2 62 62
9 1call
e.g. function 91 places)
graph (f() calls g() in several 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [19/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Data Structures
61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [20/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Representations
61 61 61
-4 -4 -4 -4
31 31 31 31
Defining6graphs:
29 62 62 62
12 91 91
8 of identifying vertices28
need some way
28
could give diagram showing edges and vertices
could give a list of edges
6E.g. 61the same graph:
1- four representations of 61 61
43 -4 -4 -4
16 31 31 31
29 62 62 62
12 91 91
8 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91
COMP9024 24T1 ♢Dynamic Data Structures♢ [21/105] 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Representations
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
We will 6
discuss 62data structures:
29 three different graph 62 62
12 91 91
8
1. Array of edges
28 28
2. Adjacency matrix
3. Adjacency list
61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [22/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Array-of-edges Representation
61 61 61
-4 -4 -4 -4
31 31 31 31
62represented as an array 6of2Edge values (= pairs of vertices)
Edges are 62 62
91 91 91
28 representation
space efficient
28 28
adding and deleting edges is slightly complex
undirected: order of vertices in an Edge doesn't matter
61 61 in an Edge encodes direction
directed: order of vertices 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
- 4 - 4 - -4
31
For simplicity, we always assume 31vertices to be numbered430..V-1
16 31
62 62 29 62
91 91 12
2
COMP9024 24T1 ♢Dynamic Data Structures♢ 2
[23/105]
 8 8 8

<< ∧ >>
61❖ Array-of-edges Representation
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Graph initialisation 62
(non-directed graph) 62 62
91 91 91
newGraph(V):
2 8 2 8 2 8
| Input number of nodes V
| Output new empty graph
|
61| g.nV = V // #vertices61 (numbered 0..V-1) 61 61
|-4 g.nE = 0 // #edges -4 -4 -4
| 3allocate
16 enough memory 3for
16 g.edges[] 31
62
31
62
| return29 g 29 91
12 12 28
8 8
How much is enough? … No more than V(V-1)/2 … Much less in practice (sparse
graph)

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [24/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Array-of-edges Representation
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Edge insertion 62 62 62
91 91 91
2 8
insertEdge(g,(v,w)):
2 8 2 8
| Input graph g, edge (v,w) // assumption: (v,w) not in g
|
| g.edges[g.nE]=(v,w)
61 | g.nE=g.nE+1 6 1- 61 61
-4 43 -4 -4
31 16 31 31
62 29 62 62
91 12 91
28 8 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [25/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Array-of-edges Representation
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Edge removal 62 62 62
91 91 91
2 8
removeEdge(g,(v,w)):
2 8 2 8
| Input graph g, edge (v,w) // assumption: (v,w) in g
|
| i=0
61| while (v,w)≠g.edges[i]
61 do 61 61
|-4 i=i+1 -4 -4 -4
| 3end
16 while 31 31
62// replace (v,w) by last edge
62 in array
31
62
29
| g.edges[i]=g.edges[g.nE-1] 91 91
1 2
| g.nE=g.nE-1 2 2
8 8 8

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [26/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Cost Analysis 61 61 61
-4 -4 -4 -4
31 31 31 31
Storage6cost:
29 O(E) (big enough for #62of9edges) 62 62
12 12 91
8
Cost of operations: 8 28
initialisation: O(1)
insert edge: O(1) (assuming edge array has space, edge does not exist in g)
61 6 1 6 61
-4find/delete edge: O(E) (need-4 to find edge in edge array) 1-4 -4
31 31 31 31
If array 6is2full on insert 62 62 62
91 91 91
allocate space
8 across ⇒ O(E)
28 for a bigger array, copy2edges 28
If we maintain edges in order
use binary search to insert/find edge ⇒ O(log E)
61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [27/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Array-of-edges
61 Representation61 61
-4 -4 -4 -4
31 31 31 31
62an array-of-edges representation
Assuming 62 … 62 62
91 91 91
28 to output all edges of2the
Write an algorithm 8 graph 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [28/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 61 61
-4
show(g): -4 -4 -4
| 3Input
16 graph g 31 31 31
| 29 62 62 62
| for all12i=0 to g.nE-1 do 912 91
28
| print 8
g.edges[i] 8
| end for

Time complexity: O(E)

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [29/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Adjacency Matrix 61Representation 61 61
-4 -4 -4 -4
31 31 31 31
62
Edges represented 62
by a V × V matrix 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

COMP9024 24T1 ♢Dynamic Data Structures♢ [30/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Adjacency Matrix 61Representation (cont)
61 61
-4 -4 -4 -4
31 31 31 31
62
Advantages 62 62 62
91 91 91
28
easily implemented
28
as 2-dimensional array
28
can represent graphs, digraphs and weighted graphs
graphs: symmetric boolean matrix
61 61 boolean matrix
digraphs: non-symmetric 61 61
-4 -4 -4 -4
31weighted: non-symmetric31matrix of weight values 31 31
62 62 62 62
91
Disadvantages: 91 91
28 28 28
if few edges (sparse) ⇒ memory-inefficient

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [31/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Adjacency Matrix 61Representation (cont)
61 61
-4 -4 -4 -4
31 31 31 31
62
Graph initialisation 62 62 62
91 91 91
newGraph(V):
2 8 2 8 2 8
| Input number of nodes V
| Output new empty graph
|
61| g.nV = V // #vertices 61 (numbered 0..V-1) 61 61
|-4 g.nE = 0 // #edges -4 -4 -4
| 3allocate
16 31
memory for g.edges[][]
62
31
62
31
62
| for 2all
91 i,j=0..V-1 do 91 91
| 28
g.edges[i][j]=0 // false 28 28
| end for
| return g

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [32/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Adjacency Matrix 61Representation (cont)
61 61
-4 -4 -4 -4
31 31 31 31
62
Edge insertion 62 62 62
91 91 91
2 8
insertEdge(g,(v,w)):
2 8 2 8
| Input graph g, edge (v,w)
|
| if g.edges[v][w]=0 then // (v,w) not in graph
61| g.edges[v][w]=16
1 // set to true 61 61
|-4 g.edges[w][v]=1 -4 -4 -4
| 316g.nE=g.nE+1 31
62
31
62
31
62
| end 2if
9 9 9
12 12 12
8 8 8

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [33/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Adjacency Matrix 61Representation (cont)
61 61
-4 -4 -4 -4
31 31 31 31
62
Edge removal 62 62 62
91 91 91
2 8
removeEdge(g,(v,w)):
2 8 2 8
| Input graph g, edge (v,w)
|
| if g.edges[v][w]≠0 then // (v,w) in graph
61| g.edges[v][w]=06
1 // set to false 61 61
|-4 g.edges[w][v]=0 -4 -4 -4
| 316g.nE=g.nE-1 31
62
31
62
31
62
| end 2if
9 9 91
12 12 28
8 8

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [34/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Show Graph61 61 61
-4 -4 -4 -4
31 31 31 31
62an adjacency matrix representation
Assuming 62 62 …
(undirected graph) 62
91 91 91
28 to output all edges of2the
Write an algorithm 8 graph (no duplicates!) 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [35/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Show Graph
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
show(g): 62 62 62
| Input 1
9graph g 91 91
|
2 8 2 8 28
| for all i=0 to g.nV-2 do
| | for all j=i+1 to g.nV-1 do
| | if g.edges[i][j] then
61| | 61
print i"—"j 61 61
|-4 | end if -4 -4 -4
3
| |16end for
31 31 31
2 62 62 62
9
| end for
12 9 12 91
8 8 28
Time complexity: O(V2)

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [36/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: 61 61 61
-4 -4 -4 -4
31 31 31 31
Analyse6storage 62 of adjacency matrix6representation
29 cost and time complexity 2 62
12 91 91
8 2
28 28
Storage cost: O(V )

If the graph is sparse, most storage is wasted.

6Cost
1- of operations: 61 61 61
43 -4 -4 -4
16
initialisation: O(V2) (initialise3V×V
16matrix) 31
62
31
62
2 9 2 91 91
12 O(1) (set two cells in matrix)
insert edge:
28 28
8
delete edge: O(1) (unset two cells in matrix)

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [37/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: (cont) 61 61 61
-4 -4 -4 -4
31 31 31 31
62optimisation: store only 6top-right
A storage 2 part of matrix. 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
New storage cost: V-1 int ptrs + V(V-1)/2 ints (but still O(V2))

Requires us to always use edges (v,w) such that v < w.

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [38/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Adjacency List Representation
61 61 61
-4 -4 -4 -4
31 31 31 31
For each6vertex,
29 store linked list of6adjacent
29 vertices: 62 62
12 12 91
8 8 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

COMP9024 24T1 ♢Dynamic Data Structures♢ [39/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Adjacency List Representation
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Advantages 62 62 62
91 91 91
28 to implement in languages
relatively easy
28 like C 28
can represent graphs and digraphs
memory efficient if E:V relatively small
6Disadvantages:
1- 61 61 61
43 -4 -4 -4
one16graph has many possible3representations
16 3
of the lists16
31
62
(unless 2 91are ordered by same criterion2e.g.
lists 91ascending) 29
28 28 12
8

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [40/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Adjacency List Representation
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Graph initialisation 62 62 62
91 91 91
newGraph(V):
2 8 2 8 2 8
| Input number of nodes V
| Output new empty graph
|
61| g.nV = V // #vertices 61 (numbered 0..V-1) 61 61
|-4 g.nE = 0 // #edges -4 -4 -4
| 3allocate
16 31
memory for g.edges[]
62
31
62
31
62
| for 2all
91 i=0..V-1 do 91 91
| 28
g.edges[i]=NULL 28
// empty list 28
| end for
| return g

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [41/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Adjacency List Representation
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Edge insertion: 62 62 62
91 91 91
2 8
insertEdge(g,(v,w)):
2 8 2 8
| Input graph g, edge (v,w)
|
| insertLL(g.edges[v],w)
61| 61
insertLL(g.edges[w],v) 61 61
|-4 g.nE=g.nE+1 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [42/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Adjacency List Representation
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Edge removal: 62 62 62
91 91 91
2 8
removeEdge(g,(v,w)):
2 8 2 8
| Input graph g, edge (v,w)
|
| deleteLL(g.edges[v],w)
61| 61
deleteLL(g.edges[w],v) 61 61
|-4 g.nE=g.nE-1 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [43/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: 61 61 61
-4 -4 -4 -4
31 31 31 31
Analyse6storage
29 cost and time complexity 62 of adjacency list representation62 62
12 91 91
8
Storage cost: O(V+E)
2 E list elements)
(V list pointers, total of 2·8
28
the larger of V,E determines the complexity

6Cost
1-
of operations: 61 61 61
4initialisation: -4 -4 -4
31 O(V) (initialise V3lists)
16 31 31
62 62 62
91 O(1) (insert one vertex2into
insert edge: 91list) 91
28 check for duplicates 28
if you don't 28
find/delete edge: O(V) (need to find vertex in list)
If vertex lists are sorted
61 61
insert requires search of list ⇒ O(V) 61 61
-4delete always requires a search,-regardless
43 -4 -4
31 1 of list order 31 31
62 62 62 62
9
COMP9024 24T11♢Dynamic
91 91
2 Data Structures♢ 2
[44/105]
2
 8 8 8

<< ∧ >>
61❖ Comparison of Graph 61 Representations 61 61
-4 -4 -4 -4
31 31 31 31
62 array
62 adjacency
adjacency
62 62
91 91 91
28 of edges matrix list
28 28
space usage E V2 V+E
initialise 1 V2 V

61insert edge 1 611 1 61 61

-4 1 -4 -4 -4
31 edge E
find/delete
31 V
31 31
62 62 62 62
91
Other operations: 91 91
28 28 28
array adjacency adjacency
of edges matrix list
disconnected(v)? E V 1
61isPath(x,y)? E·log V61V-2 V+E 61 61
-4 4 -4 -4
31
copy graph E V 23 16 E
31 31
62 29 62 62
91 12 91
2 2
 8 8 8
destroy graph 1 V E

COMP9024 24T1 ♢Dynamic Data Structures♢ [45/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Abstract Data
61 Type 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [46/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph ADT 61 61 61
-4 -4 -4 -4
31 31 31 31
Data: 62 62 62 62
91 91 91
2
set of edges,8set of vertices
28 28
Operations:
building: create graph, add edge
61 6 1 6 1- 61
-4deleting: remove edge, drop
-4 whole graph 43 -4
3 3
16 check if graph contains
scanning: 16 a given edge 16 31
29 29 29 62
12
Things to note: 12 12
8 8 8
set of vertices is fixed when graph initialised
we treat vertices as ints, but could be arbitrary Items

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [47/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph ADT (cont) 61 61 61
-4 -4 -4 -4
31 31 31 31
62 interface graph.h 62
Graph ADT 62 62
91 91 91
28
// graph representation is hidden
28 28
typedef struct GraphRep *Graph;

// vertices denoted by integers 0..N-1

61typedef int Vertex; 61 61 61

- edges are pairs of vertices-4(end-points)
//43
-4 -4
1 31 31 31
typedef62 struct Edge { Vertex 6v; 2 Vertex w; } Edge; 62 62
91 91 91
// operations 2on
8 graphs 28 28
Graph newGraph(int V); // new graph with V vertices
int numOfVertices(Graph); // get number of vertices in a graph
void insertEdge(Graph, Edge);
61void
bool
removeEdge(Graph, Edge);
adjacent(Graph,61
Vertex, Vertex); /* is 6 1 an edge
there
61
-4 -4 -4 -4
31 31 31
between two vertices */ 31
void 6showGraph(Graph);
29 62 62
// print all edges in a graph 62
1
void freeGraph(Graph); 91 91
2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [48/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Graph 6ADT 1- Client 61 61
-4 43 -4 -4
31 16 31 31
6
Write a program
29 that uses the graph2ADT to 62 62
12 91 91
8 depicted below
build the graph
28 28
print all the nodes that are incident to vertex 1 in ascending order

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [49/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 61 61
-4
#include <stdio.h> -4 -4 -4
31 "Graph.h"
#include 31 31 31
62 62 62 62
912 4 91 91
#define NODES
8 28 28
#define NODE_OF_INTEREST 1

int main(void) {
Graph g = newGraph(NODES);
61 61 61 61
-4 Edge e; -4 -4 -4
31 31 31 31
e.v6 = 0; e.w= 1; 62
insertEdge(g,e); 62 62
2 e.w
e.v =90; = 3; 91
insertEdge(g,e); 91
1
e.v = 1;28e.w= 3; 28
insertEdge(g,e); 28
e.v = 3; e.w = 2; insertEdge(g,e);

int v;
61 forif(v(adjacent(g,
= 0; v < NODES; v++) {
61v, NODE_OF_INTEREST)) 61 61
-4 -4 -4 -4
31 printf("%d\n", v); 31 31 31
} 62 62 62 62
91 91 91
2 2 2
 8 8 8
freeGraph(g);
return 0;
}
61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [50/105]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph ADT (Array 61 of Edges) 61 61
-4 -4 -4 -4
31 31 31 31
62
Implementation 62
of GraphRep (array-of-edges representation)62 62
91 91 91
2 8
typedef struct GraphRep {
2 8 2 8
Edge *edges; // array of edges
int nV; // #vertices (numbered 0..nV-1)
int nE; // #edges
61 int n; // 61
size of edge array 61 61
}-4GraphRep; -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91
COMP9024 24T1 ♢Dynamic Data Structures♢ [51/105] 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph ADT (Adjacency 61 Matrix) 61 61
-4 -4 -4 -4
31 31 31 31
62
Implementation 62
of GraphRep (adjacency-matrix 62
representation) 62
91 91 91
2 8
typedef struct GraphRep {
2 8 2 8
int **edges; // adjacency matrix
int nV; // #vertices
int nE; // #edges
61} GraphRep; 6 1- 61 61
-4 43 -4 -4
31 16 31 31
62 29 62 62
91 12 91
28 8 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [52/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph ADT (Adjacency 61 Matrix) (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Implementation 62 (adjacency-matrix representation)
of graph initialisation 62 62
91 91 91
28 28 28
Graph newGraph(int V) {
assert(V >= 0);
int i;

Graph g = malloc(sizeof(GraphRep)); assert(g != NULL);

61 g->nV = V; g->nE = 0; 61 61 61
-4 -4 -4 -4
3//1allocate memory for each row
31 31 31
62 = malloc(V * sizeof(int 6*));
g->edges 2 62
assert(g->edges != NULL);
62
91 memory for each column and
// allocate 91initialise with 0 91
for (i = 0;28
i < V; i++) { 28 28
g->edges[i] = calloc(V, sizeof(int)); assert(g->edges[i] != NULL);
}
return g;
}
6standard
1- 6 1
library function calloc(size_t
6 1- nbytes)
nelems, size_t
61
43 - 43 43 -4
1 1 1 31
6
allocates 6
29 a memory block of size 2nelems*nbytes 62 62
12 91 91
2 2
 8 8 8
and sets all bytes in that block to zero

COMP9024 24T1 ♢Dynamic Data Structures♢ [53/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph ADT (Adjacency 61 Matrix) (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Implementation 62
of edge insertion/removal (adjacency-matrix6representation)
2 62
91 91 91
28 28 28
// check if vertex is valid in a graph
bool validV(Graph g, Vertex v) {
return (g != NULL && v >= 0 && v < g->nV);
}
61void insertEdge(Graph g, Edge
61 e) { 61 61
-4assert(g != NULL && validV(g,e.v)
-4 && validV(g,e.w)); -4 -4
31 31 31 31
62
if (!g->edges[e.v][e.w])
62 e not in graph
{ // edge
62 62
91
g->edges[e.v][e.w] = 1; 91 91
28
g->edges[e.w][e.v] = 1; 28 28
g->nE++;
}
}

61voidassert(g
removeEdge(Graph g, Edge e) {
61
!= NULL && validV(g,e.v) && validV(g,e.w));61 61
-4 -4 -4 -4
3if1(g->edges[e.v][e.w]) { //31edge e in graph 31 31
62
g->edges[e.v][e.w] = 0; 62 62 62
91
g->edges[e.w][e.v] = 0; 91 91
g->nE--;2 2 2
 8 8 8
}
}

COMP9024 24T1 ♢Dynamic Data Structures♢ [54/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Checking 61 Neighbours (i) 61 61
-4 -4 -4 -4
31 31 31 31
Assuming62an adjacency-matrix representation
62 … 62 62
91 91 91
28 to check whether two
Implement a function
28 vertices are directly connected
28 by an
edge

bool adjacent(Graph g, Vertex x, Vertex y) { … }

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [55/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 61 61
-4 adjacent(Graph g, Vertex
bool -4 x, Vertex y) { -4 -4
3assert(g
1 31
!= NULL && validV(g,x) 31
&& validV(g,y)); 31
62 62 62 62
9 9 91
return 1(g->edges[x][y]
2 != 0); 12 28
} 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [56/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph ADT (Adjacency 61 List) 61 61
-4 -4 -4 -4
31 31 31 31
62
Implementation 62
of GraphRep (adjacency-list representation) 62 62
91 91 91
2 8
typedef struct GraphRep {
2 8 2 8
Node **edges; // array of lists
int nV; // #vertices
int nE; // #edges
61} GraphRep; 61 61 61
-4 -4 -4 -4
31 struct Node {
typedef 31 31 31
62
Vertex v;
62 62 62
91 91 91
28 *next;
struct Node 28 28
} Node;

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
COMP9024 24T1 ♢Dynamic Data Structures♢ [57/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Checking 61 Neighbours (ii) 61 61
-4 -4 -4 -4
31 31 31 31
Assuming62an adjacency list representation
62 … 62 62
91 91 91
28 to check whether two
Implement a function
28 vertices are directly connected
28 by an
edge

bool adjacent(Graph g, Vertex x, Vertex y) { … }

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [58/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 61 61
-4 adjacent(Graph g, Vertex
bool -4 x, Vertex y) { -4 -4
3assert(g
1 31
!= NULL && validV(g,x)); 31 31
62 62 62 62
9 91 91
return 1inLL(g->edges[x],
2 y); 28 28
} 8
inLL() checks if linked list contains an element

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [59/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Problems on Graphs
61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [60/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Problems on Graphs 61 61 61
-4 -4 -4 -4
31 31 31 31
62 of problems do we want6to
What kind 2 solve on/via graphs? 62 62
91 91 91
28
is the graph fully-connected
28 is <2)?
(# connected components
28
can we remove an edge and keep it fully-connected?
is one vertex reachable starting from some other vertex?
which vertices are reachable from v? (transitive closure)
61 6 1- all vertices? (circuit) 61 61
-4is there a cycle that passes through 43 -4 -4
3
what16is the cheapest cost path from v1to6w? 31 31
62 62
is there2a9 29 tree)
tree that links all vertices? (spanning 91
12 12 28
8 spanning tree?
what is the minimum 8
…
can a graph be drawn in a plane with no crossing edges? (planar graphs)
are two graphs "equivalent"? (isomorphism)
61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [61/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Algorithms 61 61 61
-4 -4 -4 -4
31 31 31 31
62 we examine algorithms
In this course 62for 62 62
91 91 91
28 (simple graphs)
graph traversal
28 28
reachability (directed graphs)
minimum spanning trees (weighted graphs)
61 shortest path (weighted6graphs)
1 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [62/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Graph Traversal61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [63/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Finding a Path 61 61 61
-4 -4 -4 -4
31 31 31 31
62on paths:
Questions 62 62 62
91 91 91
28 between two given vertices
is there a path
28 (src,dest)? 28
what is the sequence of vertices from src to dest?

Approach to solving problem:

61 6 1 6 1- 61
-4examine vertices adjacent-4to src 43 -4
3 3
16 of them is dest, then done
if any 16 16 31
29 29 29 62
otherwise 12from src (neighbours of neighbours)
12examine vertices two edges 12
8 8
repeat looking further and further from src
8
Two strategies for graph traversal/search: depth-first, breadth-first
DFS follows one path to completion before considering others
61 61 61 61
-4BFS "fans-out" from the starting
-4 vertex ("spreading"-subgraph)
43 -4
31 31 16 31
62 62 29 62
9
COMP9024 24T11♢Dynamic Data Structures♢ 9 12
[64/105] 12
2
 8 8 8

<< ∧ >>
61❖ Finding a Path (cont)
61 61 61
-4 -4 -4 -4
31 31 31 31
62 of BFS/DFS search for6checking
Comparison 2 if there is a path6from
2 a to h … 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

Both approaches ignore some edges by remembering previously visited vertices.

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [65/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Depth-first Search 61 61 61
-4 -4 -4 -4
31 31 31 31
62 search can be described62recursively as
Depth-first 62 62
91 91 91
28
depthFirst(G,v):
28 28
1. mark v as visited
2. for each (v,w)∈edges(G) do
61 if w has not been visited
61 then 61 61
-4 depthFirst(w) -4 -4 -4
3 16 3 16 31 31
29 induces backtracking 29 62 62
The recursion
12 12 91
8 8 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [66/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Depth-first Search 61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62DFS path checking 62
Recursive 62 62
91 91 91
2 8
hasPath(G,src,dest):
2 8 28
| Input graph G, vertices src,dest
| Output true if there is a path from src to dest in G,
| false otherwise
61| 61 61 61
|-4 mark all vertices in -4
G as unvisited -4 -4
| 3return 31
16 dfsPathCheck(G,src,dest)
6
31
6
31
62
29 29 29
12
dfsPathCheck(G,v,dest): 12 12
8
| mark v as visited
8 8
| if v=dest then // found dest
| return true
| else
61| | for all (v,w)∈edges(G)
61 do 61 61
-
|43| | if w has not been
-4 visited then -4 -4
1 31 31 31
| | 6|2 62
return dfsPathCheck(G,w,dest) 62via w to dest
// found path 62
| | | 9end
1 if 91 91
2 2 2
 8 8 8
| | end for
| end if
| return false // no path from v to dest
61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [67/105]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Depth-first 61 Traversal (i) 61 61
-4 -4 -4 -4
31 31 31 31
62execution of dfsPathCheck(G,0,5)
Trace the 62 on: 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
Consider neighbours in ascending order

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [68/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 61 61
-4
Answer: -4 -4 -4
31 31 31 31
6
29- 4 - 5
0-1-2-3
62 62 62
12 91 91
8 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [69/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Depth-first 61 Traversal (i) (cont)61 61
-4 -4 -4 -4
31 31 31 31
62
Cost analysis: 62 62 62
91 91 91
28
all vertices marked
28 visited at most once2⇒8 cost =
as unvisited, each vertex
O(V)
visit all edges incident on visited vertices ⇒ cost = O(E)
61 6 list representation
assuming an adjacency
1- 61 61
-4 43 -4 -4
Time3complexity
1 of DFS: O(V+E) 1(adjacency list representation)31 31
62 62 62 62
91 91
the larger of V,E determines the complexity 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [70/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Depth-first61 Traversal (i) (cont)61 61
-4 -4 -4 -4
31 31 31 31
62different graph data structures
Note how 62 affect cost: 62 62
91 91 91
28 representation
array-of-edges
28 28
visit all edges incident on visited vertices ⇒ cost = O(V·E)
cost of DFS: O(V·E)
61 61
adjacency-matrix representation 61 61
-4 -4 -4 -4
31visit all edges incident on3visited
1 31 2)
vertices ⇒ cost = O(V 31
62 62 62 62
cost9of12DFS: O(V2) 91
28
91
28
8
In case of Adjacency List:

For dense graphs … E ≅ V2 ⇒ O(V+E) = O(V2)

6For
1 sparse graphs … E ≅ V6⇒1 O(V+E) = O(E) 61 61
-4 -4 -4 -4
31 31 31 31
62 62
COMP9024 24T1 ♢Dynamic Data Structures♢ [71/105] 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Depth-first61 Traversal (i) (cont)61 61
-4 -4 -4 -4
31 31 31 31
Knowing62whether a path exists can6be
2 useful 62 62
91 91 91
28 path is even more useful
Knowing what the
28 28
⇒ record the previously visited node as we search through the graph (so that we
can then trace path through graph)

6Make
1-
use of global variable:
61 61 61
4visited[] -4 -4 -4
31 31
… array to store previously visited node, for3each
1 node being 31
62
visited 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [72/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Depth-first
61 Traversal (i) (cont)61 61
-4 -4 -4 -4
31 31 31 31
62 // store previously visited
visited[] 62 node, for each vertex 0..nV-1
62 62
91 91 91
2 8
findPath(G,src,dest):
2 8 2 8
| Input graph G, vertices src,dest
|
| for all vertices v∈G do
61| visited[v]=-1 61 61 61
|-4 end for -4 -4 -4
31
| visited[src]=src
31 31of the path 31
62 62 // starting node 62 62
91
| if dfsPathCheck(G,src,dest) 9then
1 91 order
// show path in dest..src
| | v=dest 28 28 28
| | while v≠src do
| | print v"-"
| | v=visited[v]
61|| || print
end while
src 61 61 61
-
|43end if
-4 -4 -4
16 3 16 316 31
29 29 29 62
1
dfsPathCheck(G,v,dest):
2 12 12
 8 8 8
| if v=dest then // found edge from v to dest
| return true
| else
61| | for all (v,w)∈edges(G)
61 do 61 61
|-4 | | if visited[w]=-1
-4 then -4 -4
| 3|1 | | visited[w]=v 31 31 31
| | 6|2 | if dfsPathCheck(G,w,dest)
62 then 62 62
9
| | | |12 return true
91// found path via w to dest91
8 28 28
| | | | end if
| | | end if
| | end for
| end if
61| return false 61 // no path from61
v to dest 61
-4 -4 -4 -4
31 31 31 31
62 62
COMP9024 24T1 ♢Dynamic Data Structures♢ [73/105] 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Depth-first61 Traversal (ii) 61 61
-4 -4 -4 -4
31 31 31 31
Show the62DFS order in which we visit
62 vertices in this graph when
62 searching for a 62
91 6:
path from 0 to
91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

6Consider
1- 61
neighbours in ascending order
61 61
43 - 43 -4 -4
16 16 31 31
29 ♢Dynamic Data Structures♢29 62 62
COMP9024 24T1
12 [74/105]
12 91
2
 8 8 8

<< ∧ >>
61 61 61 61
-04 0 3 5 3 1-4 5 4 7 8 -4 -4
31 31 31 31
[0] 6
[1]
29[2] [3] [4] [5] 6 [7]
[6]
29 [8] [9] 62 62
12 12 91
Path: 6-5-1-0 8 8 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [75/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Depth-first
61 Traversal (ii) (cont) 61 61
-4 -4 -4 -4
31 31 31 31
DFS can6also 62
29 be described non-recursively (via a stack): 62 62
12 91 91
8
hasPath(G,src,dest):
2 8 2 8
| Input graph G, vertices src,dest
| Output true if there is a path from src to dest in G,
| false otherwise
61| 61 61 61
|-4 mark all vertices in -4
G as unvisited -4 -4
| 3push
16 src onto new stack31s 6 31
62
31
62
29
| found=false 29 91
1
| while not 1
28found and s is not empty
28 do 28
| | pop v from s
| | mark v as visited
| | if v=dest then
| | found=true
61| | else 61 61 61
- -4
|43| | for each (v,w)∈edges(G) such that w
-has
4 not been visited
-4
1 31 31 31
| | 6|2 push w onto s 62 62 62
| | | 9end1 for 91 91
2 2 2
 8 8 8
| | end if
| end while
| return found
61 61 61 61
Uses
-4 standard stack operations
-4 (push, pop, check if empty) -4 -4
31 31 31 31
62
Time complexity 62
is the same: O(V+E) 62 62
91 91 91
28 28 28
COMP9024 24T1 ♢Dynamic Data Structures♢ [76/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Depth-first 61 Traversal (iii) 61 61
-4 -4 -4 -4
31 31 31 31
Show how62the stack evolves when 6executing
2 62 on:
findPathDFS(g,0,5) 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
Push neighbours in descending order … so they get popped in ascending order

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [77/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 4 651 61
-4 -4 -4 -4
31 31 3 5 5 315 31
62 62 62 62
91 1 2 49
12 4 4 4 91
28 4 4 4 8 4 4 4
28
(empty) → 0 → 5 → 5 → 5 → 5 → 5 → 5

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [78/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Breadth-first Search 61 61 61
-4 -4 -4 -4
31 31 31 31
62 to breadth-first search
Basic approach 62 (BFS): 62 62
91 91 91
28 current vertex
visit and mark
28 28
visit all neighbours of current vertex
then consider neighbours of neighbours
6Notes:
1- 61 61 61
43 -4 -4 -4
16 to describe recursively316
tricky
31
62
31
62
29 29 91
a minor variation
12 on non-recursive DFS
12 search works
⇒ switch the8stack for a queue 8 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [79/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Breadth-first Search
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 (records visiting order,
BFS algorithm 62 marks vertices as visited62when put on 62
queue):
91 91 91
28 28 28
visited[] // array of visiting orders, indexed by vertex 0..nV-1

findPathBFS(G,src,dest):
61| Input graph G, vertices
61 src,dest 61 61
|-4 -4 -4 -4
31 all vertices v∈G do
| for
31 31 31
|
6visited[v]=-1
29 62 62 62
1 91 91
| end for 2 28 28
8
| enqueue src into new queue q
| visited[src]=src
| found=false
| while not found and q is not empty do
61| | dequeue v from 6q1 61 61
-
|43| if v=dest then
-4 -4 -4
1 31 31 31
| | 62 found=true 62 62 62
| | else 91 91 91
2 2 2
 8 8 8
| | | for each (v,w)∈edges(G) such that visited[w]=-1 do
| | | enqueue w into q
| | | visited[w]=v
61| | | end for 61 61 61
|-4 | end if -4 -4 -4
| 3end
16 while 31 31 31
29 then
| if found 62 62 62
| 12 path in dest..src9order
display 12 91
28
| end if 8 8
Uses standard queue operations (enqueue, dequeue, check if empty)

61 61
COMP9024 24T1 ♢Dynamic Data Structures♢ [80/105]
61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Breadth-first
61 Traversal 61 61
-4 -4 -4 -4
31 31 31 31
Show the62BFS order in which we visit
62vertices in this graph when
62 searching for a 62
91 6:
path from 0 to
91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

6Consider
1- 61
neighbours in ascending order
61 61
43 - 43 -4 -4
16 16 31 31
29 ♢Dynamic Data Structures♢29 62 62
COMP9024 24T1
12 [81/105]
12 91
2
 8 8 8

<< ∧ >>
61 61 61 61
-04 0 0 2 5 0-4 5 5 3 -1 -4 -4
31 31 31 31
[0] 6
[1]
29[2] [3] [4] [5] 6 [7]
[6]
29 [8] [9] 62 62
12 12 91
Path: 6-5-0 8 8 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [82/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Breadth-first
61 Traversal (cont)61 61
-4 -4 -4 -4
31 31 31 31
62
Time complexity 62 list representation, same62as DFS)
of BFS: O(V+E) (adjacency 62
91 91 91
28 path
BFS finds a "shortest"
28 28
based on minimum # edges between src and dest.
stops with first-found path, if there are multiple ones
61 61 61 61
-4 -4
In many applications, edges are weighted and we want path -4 -4
31 31 31 31
62 62
based on minimum sum-of-weights along path src .. dest
62 62
91 91 91
28
We discuss weighted/directed graphs later.
28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [83/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Other DFS Examples 61 61 61
-4 -4 -4 -4
31 31 31 31
62
Other problems 62 search
to solve via DFS graph 62 62
91 91 91
2 2
checking for8the existence of a cycle 8
28
determining which connected component each vertex is in

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [84/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Buggy 6Cycle 1- Check 61 61
-4 43 -4 -4
31 16 31 31
6
A graph has
29a cycle if 29 62 62
12 12 91
it has a path8
of length > 1 8 28
with start vertex src = end vertex dest
and without using any edge more than once
6We 61the path, just indicate its6presence.
1- are not required to give 1- 61
43 - 43 43 -4
1 1 1 31
6
The following 6
29 DFS cycle check has two 29bugs. Find them. 62 62
12 12 91
hasCycle(G):8 8 28
| Input graph G
| Output true if G has a cycle, false otherwise
|
61| choose any vertex 6v∈G
1- 61 61
|-4 return dfsCycleCheck(G,v)
4 -4 -4
31 31 31 31
296
dfsCycleCheck(G,v):
62 62 62
91 91
| mark v 1as
2 visited 2 2
 8 8 8
| for each (v,w)∈edges(G) do
| | if w has been visited then // found cycle
| | return true
61| | else if dfsCycleCheck(G,w)
61 then 61 61
|-4 | return true -4 -4 -4
| 3end
16 for 31 31 31
2 false
| return 62 // no cycle at v 62 62
91 91 91
28 28 28
COMP9024 24T1 ♢Dynamic Data Structures♢ [85/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 61 61
1.-4Only one connected component
-4 is checked. -4 -4
31 31 31 31
2. The 6
loop 62 62 62
29 91 91
for
12
each (v,w)∈edges(G) do 28 28
8
should exclude the neighbour of v from which you just came, so as to prevent a
single edge w-v from being classified as a cycle.
61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [86/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Computing Connected61 Components 61 61
-4 -4 -4 -4
31 31 31 31
62
Problems: 62 62 62
91 91 91
28
how many connected
28
subgraphs are there?
28
are two vertices in the same connected subgraph?

Both of the above can be solved if we can

61 6 1 6 1- 61
-4build an array, one element-4for each vertex V 43 -4
3
indicating
3
16 which connected component16 V is in 16 31
29 29 29 62
12 … array [0..nV-1] of component
componentOf[] 12 IDs 12
8 8 8

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [87/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Computing Connected 61 Components 6(cont)
1- 61
-4 -4 43 -4
31 31 16 31
6 6
Algorithm2to assign vertices to connected
2 components: 29 62
91 91 12
2
components(G): 8 2 8 8
| Input graph G
|
| for all vertices v∈G do
61| 61
componentOf[v]=-1 61 61
|-4 end for -4 -4 -4
| 3compID=0
16 31
62
31
62
31
62
| for 2all
91 vertices v∈G do 91 91
28
| | if componentOf[v]=-1 then 2
8 28
| | dfsComponents(G,v,compID)
| | compID=compID+1
| | end if
| end for
61 61 61 61
-
43
dfsComponents(G,v,id):
-
43 -4 -4
16 16 31 31
| componentOf[v]=id
2 2 62 62
| for all9 1 vertices w adjacent 9to1 v do 91
2 2 2
 8 8 8
| if componentOf[w]=-1 then
| dfsComponents(G,w,id)
| end if
61 | end for 6 61 61
-4 1- -4 -4
31 43 31 31
16
COMP9024624T1 ♢Dynamic Data Structures♢[88/105] 62 62
29 29 91
12 12 28
8 8

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Connected 61 components 61 61
-4 -4 -4 -4
31 31 31 31
62execution of the algorithm
Trace the 62 62 62
91 91 91
2
1. on the graph8shown below
28 28
2. on the same graph but with the dotted edges added

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

Consider neighbours in ascending order

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [89/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61 61 61 61
1.-43[0] [1] [2] [3] [4] -4[5]
31 [6] [7] -4
31
-4
31
16 -1
-1 -1 -1 -1 -162-1 -1 62 62
29 91 91
0 -112 -1 -1 -1 -1 -1 2-1 28
0 -1
80 -1 -1 -1 -1
8
-1
0 0 0 -1 -1 -1 -1 -1
0 0 0 1 -1 -1 -1 -1
61 …61 61 61
-4 -4 2 2 2 -4 -4
3016 0 0 1 1 31 31 31
29 62 62 62
[1]12[2]
9
[4] [5] [6] 12[7]
91
2. [0] [3] 28
-1 -1
8-1 -1 -1 -1 -1 -1
8
0 -1 -1 -1 -1 -1 -1 -1
0 0 -1 -1 -1 -1 -1 -1
61 0 0 0 -1 6-11 -1 -1 -1 61 61
-4 -4 -4 -4
31 … 31 31 31
0
620 0 0 0 1
621 1
62 62
91 91 91
2 2 2
 8 8 8
COMP9024 24T1 ♢Dynamic Data Structures♢ [90/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Hamiltonian and6Euler
1- Paths 61 61
-4 43 -4 -4
31 16 31 31
62 29 62 62
91 12 91
28 8 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [91/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Hamiltonian Path 61and Circuit 61 61
-4 -4 -4 -4
31 31 31 31
62 path problem:
Hamiltonian 62 62 62
91 91 91
28
find a path connecting
2
two vertices v,w8in graph G
28
such that the path includes each vertex in G exactly once

If v = w, then we have a Hamiltonian circuit

61 61 61 61
-4 to state, but difficult to-4solve (NP-complete)
Simple -4 -4
3 16 3 16 31 31
2 2 62 62
Many real-world
91 applications require9you to visit all vertices of a9graph:
28 1 28 12
Travelling salesman
8
Bus routes
…
61 61 61 61
-4 -4 -4
Problem named after Irish mathematician, physicist and astronomer Sir William Rowan Hamilton -4
31
(1805 — 1865) 31 31 31
62 62 62 62
91 91
COMP9024 24T1 ♢Dynamic Data Structures♢ [92/105] 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Hamiltonian Path 61and Circuit (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 two possible Hamiltonian
Graph and 62paths: 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [93/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Hamiltonian Path 61and Circuit (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62
Approach: 62 62 62
91 91 91
2 possible simple paths (using
generate all 8
28 e.g. DFS) 28
keep a counter of vertices visited in current path
stop when find a path containing V vertices
6Can 61 DFS algorithm 61
1- be expressed via a recursive 61
43 -4 -4 -4
16 to simple path finding31approach,
similar 62 except
31
62
31
62
29 91 if length = v-1 (length9=1v for circuit)
keeps1track of path length; succeeds
28 28 28
resets "visited" marker after unsuccessful path

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [94/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Hamiltonian Path 61and Circuit (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62for finding Hamiltonian 6path:
Algorithm 2 62 62
91 91 91
2 8 2 8
visited[] // array [0..nV-1] to keep track of visited vertices
2 8
hasHamiltonianPath(G,src,dest):
| for all vertices v∈G do
61| 61
visited[v]=false 61 61
|-4 end for -4 -4 -4
| 3return 31
16 hamiltonR(G,src,dest,#vertices(G)-1)
6
31
6
31
62
29 29 29
12
hamiltonR(G,v,dest,d): 12 12
| Input G
8 graph 8 8
| v current vertex considered
| dest destination vertex
| d distance "remaining" until path found
61| 61 61 61
-
|43if v=dest then
-4 -4 -4
1 31 31 31
| 6if
2 d=0 then return true62else return false 62 62
| else 91 91 91
2 2 2
 8 8 8
| | mark v as visited
| | for each unvisited neighbour w of v in G do
| | if hamiltonR(G,w,dest,d-1) then
61| | return true
61 61 61
|-4 | end if -4 -4 -4
| 3|1 end for 31 31 31
| end62if 62 62 62
9 unvisited
| mark v 1as
91// reset visited mark 91
28 28 28
| // no hamiltonian path from v in this consideration
| return false

COMP9024 24T1 ♢Dynamic Data Structures♢ [95/105]

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Hamiltonian 61 Path 61 61
-4 -4 -4 -4
31 31 31 31
62execution of the algorithm
Trace the 62when searching for a Hamiltonian
62 path from 62
1 to 6:
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28
Consider neighbours in ascending order

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [96/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61-0-2-3-4-5-6
1- 61
d≠0 61 61
43
1-0-2-3-4-5-7-8-9 -4
no unvisited neighbour -4 -4
16 31 31 31
1-0-2-3-4-5-7-9-8
29 62
no unvisited neighbour 62 62
1-0-2-3-4-7-5-6
12 d≠0 91 91
2 28
1-0-2-3-4-7-8-98 8
no unvisited neighbour
1-0-2-3-4-7-9-8 no unvisited neighbour
1-0-2-3-4-8-7-5-6 d≠0

61-0-2-3-4-8-7-9
1-
no unvisited neighbour
6
✓ 1
61 61
1-0-2-3-4-8-9-7-5-6
4 -4 -4 -4
31 31 31 31
Repeat 6 62dest=6
on2your own with src=0 and 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [97/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Hamiltonian 61 Path (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62worst case requires (V-1)!6paths
Analysis: 2 to be examined 62 62
91 91 91
28 with isolated vertex and2the
Consider a graph 8 rest fully-connected 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
9
12 x,0)1for
9 91
Checking hasHamiltonianPath(g,
8 2 any x 8 28
requires us to consider every possible path
e.g 1-2-3-4, 1-2-4-3, 1-3-2-4, 1-3-4-2, 1-4-2-3, …
61 starting from any x, there
6 are 3! paths ⇒ 4! total paths
6 61
1- 1-
-4there is no path of length 54in these (V-1)! possibilities4 -4
31 31 31 31
62 62 62 62
There is no9known
12 simpler algorithm for 91this task 91
2 2
 8 8 8
Note, however, that the above case could be solved in constant time if
we had a fast check for 0 and x being in the same connected component

61 61
COMP9024 24T1 ♢Dynamic Data Structures♢ [98/105] 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Euler Path and Circuit61 61 61
-4 -4 -4 -4
31 31 31 31
62problem:
Euler path 62 62 62
91 91 91
28
find a path connecting
2
two vertices v,w8in graph G
28
such that the path includes each edge exactly once
(note: the path does not have to be simple ⇒ can visit vertices more than once)

6If1v = w, the we have an Euler

61 circuit 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

6Many 61 require you to visit all 6edges

1- real-world applications 1- of a graph: 61
43 - 43 43 -4
16 16 16 31
Postman
29 29 29 62
Garbage 1pickup
2 12 12
 8 8 8
…

Problem named after Swiss mathematician, physicist, astronomer, logician and engineer Leonhard
Euler (1707 — 1783)
61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [99/105] -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Euler Path and Circuit
61 (cont) 61 61
-4 -4 -4 -4
31 31 31 31
62 "brute-force" approach:
One possible 62 62 62
91 91 91
28 path if it's an Euler path28
check for each
28
would result in factorial time performance

Can develop a better algorithm by exploiting:

61 61 61 61
-4
Theorem. A graph has an -4 circuit if and only if
Euler -4 -4
3 1
it is connected
3 16 even degree
and all vertices have
31 31
6
29 29 62 62
1 1 91
Theorem. 28 has a non-circuitous Euler
A graph 28 path if and only if 28
it is connected and exactly two vertices have odd degree

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [100/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Euler Paths61 and Circuits 61 61
-4 -4 -4 -4
31 31 31 31
62these two graphs have an6Euler
Which of 2 62
path? an Euler circuit? 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91
COMP9024 24T1 ♢Dynamic Data Structures♢ [101/105] 91
2 2 2
 8 8 8

<< ∧ >>
6No
1- Euler circuit 61 61 61
43 -4 -4 -4
Only the 31 path, e.g. 2-0-1-3-2-4-531
16second graph has an Euler 31
29 62 62 62
12 91 91
8 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31
COMP9024 24T1 ♢Dynamic Data Structures♢ [102/105] 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Euler Paths61 and Circuits (cont) 61 61
-4 -4 -4 -4
31 31 31 31
Assume6the 62 (degree of a vertex)
29existence of degree(g,v) 62 62
12 91 91
28Euler path:
8 whether a graph has an
Algorithm to check
28
hasEulerPath(G,src,dest):
| Input graph G, vertices src,dest
61| Output true if G has61 Euler path from src 6to1 dest 61
|-4 -4
false otherwise -4 -4
| 31 31 31 31
62
| if degree(G,src) is even
62 degree(G,dest) is even
or
62 then 62
|
91 false
return
91 91
28 28 28
| end if
| for all vertices v∈G do
| if v≠src and v≠dest and degree(G,v) is odd then
| return false
61| end if 61 61 61
|-43end for -4
31
-4
31
-4
31
1 6 true
| return 6 6 62
29 29 29
12 12 12
 8 8 8
The basic idea: ensure that all vertices have even degree except for the src and
dest, which have odd degrees. All non-source/destination vertices with odd
degrees must be connected in pairs to form an even degree.
61 61 61 61
-4 -4
COMP9024 24T1 ♢Dynamic Data Structures♢ [103/105]
-4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

<< ∧ >>
61❖ Exercise: Euler Paths
61 and Circuits (cont) 61 61
-4 -4 -4 -4
31 31 31 31
Analysis6of
29hasEulerPath algorithm:62 62 62
12 91 91
28
assume that8connectivity is already checked
28
assume that degree is available via O(1) lookup
single loop over all vertices ⇒ O(V)
61 61 61 61
If -degree
4 requires iteration over
-4 vertices -4 -4
3 1 3 16 vertex is O(V)
cost6to compute degree of a single
31 31
29 29 62 62
12is O(V2)
overall cost 12 91
8 8 28
⇒ problem tractable, even for large graphs (unlike Hamiltonian path problem)

For the keen, a linear-time (in the number of edges, E) algorithm to compute an
6Euler
1 path is described in 6[Sedgewick]
1 Ch.17.7. 61 61
-4 -4 -4 -4
31 31 31 31
62 62
COMP9024 24T1 ♢Dynamic Data Structures♢ [104/105] 62 62
91 91 91
2 2 2
 8 8 8

<< ∧
61❖ Summary 61 61 61
-4 -4 -4 -4
31 31 31 31
Graph62terminology 62 62 62
91 91 91
28edges, vertex degree, connected
vertices, 28 graph, tree 28
path, cycle, clique, spanning tree, spanning forest
Graph representations

61 array of edges 61 61 61
-4 adjacency matrix -4 -4 -4
31 31 31 31
62
adjacency lists 62 62 62
91 91 91
2
Graph traversal
8 28 28
depth-first search (DFS)
breadth-first search (BFS)
cycle check, connected components
61 61 61 61
-4 -4 Euler paths/circuits
Hamiltonian paths/circuits, -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8
Suggested reading (Sedgewick):

graph representations … Ch. 17.1-17.5

Hamiltonian/Euler paths … Ch. 17.7

61 61 61 61
-4 -4
graph search … Ch. 18.1-18.3, 18.7 -4 -4
31 31 31 31
62 62 62 62
91 91
COMP9024 24T1 ♢Dynamic Data Structures♢ [105/105] 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2
 8 8 8

Produced: 5 Mar 2024

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
28 28 28

61 61 61 61
-4 -4 -4 -4
31 31 31 31
62 62 62 62
91 91 91
2 2 2