Graphs
Graph Algorithms COMP4500/7500
Advanced Algorithms & Data Structures
August 10, 2019
August 10, 2019 1/1
Graphs
Overview
August 10, 2019
2/1
Graphs recap
Minimum spanning trees:
General
Prim’s algorithm Kruskal’s algorithm
Graphs
Graphs recap
Graphs are a common way of representing problems.
A graph G = (V,E) is made up of:
a set V of Vertices, e.g. (A, B, C, D, E, F)
a set E of Edges, e.g. ((A,B), (A,D), (A,C), (B,D), … )
A
@
E
@
@
C
D
F
August 10, 2019
3/1
Can be:
B
Directed/undirected Weighted/unweighted Cyclic/acyclic Connected/disconnected
Graphs
Programming with graphs: graph representations
There are two main approaches to representing graphs: Adjacency list.
E.g. for an undirected graph:
Node A
B
C
D
Connections B, D, C
A, D
A, D
A, B, C
B
@
@
@
C
D
August 10, 2019
4/1
A
Adjacency matrix.
E.g. for an undirected graph
ABCD A-XXX BX–X CX–X DXXX-
A
B
@
@
@
C
D
Graphs
Algorithms covered
Covered:
Breadth-first search
Depth-first search
Topological sort (DFS as a subroutine)
August 10, 2019
5/1
Graphs
A minimum spanning tree problem
Consider laying cable (e.g. for the NBN): Create a connected network of houses that uses the least amount of total cable.
Assume that the speed along the cable is fast: the distance house-to-house is irrelevant (we aren’t looking for shortest paths).
August 10, 2019 6/1
Graphs
A minimum spanning tree problem … in other words
We are given an undirected, weighted graph G = (V , E ) with weights w such that:
vertices V represent houses in the NBN
for each edge (u,v) 2 E, the weight w(u,v) is the cost of
laying cable from house u to house v.
We want to find an acyclic subset T ✓ E that
connects all of the verticePs in G such that
the total weight of T, i.e. (u,v)2E w(u,v), is minimised.
August 10, 2019
7/1
Graphs
The minimum spanning tree problem
Inputs
G a connected, undirected, weighted graph G = (V , E )
w weights w, where w(u,v) is the weight of the edge from u
to v Output
T A subset of E that forms a spanning tree T : a tree (connected acyclic subgraph of G) that contains all vertices of G (spanning)
and is of minimal weight
weight(T)= X w(u,v) (u,v)2T
August 10, 2019 8/1
Graphs
Example of MST
6 12 5
14 8 7 3 10
9 15
August 10, 2019
9/1
November 9, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.10
Graphs
Example of MST
6 12 5
14 8 7 3 10
9 15
August 10, 2019
10/1
November 9, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.11
Graphs
Generic construction of an MST
Approach: incrementally construct T , which is a set of edges, and which will eventually become an MST of G.
GENERIC-MST(G, w) 1T=;
2 3 4 5 6
while T is not a spanning tree
// invariant: T is a subset of some MST of G find an edge (u,v) that is safe for T
T = T [{(u,v)}
return T
August 10, 2019 15/1
Graphs
Prim’s algorithm
T is always a tree (a connected acyclic sub-graph of G): Initially T is chosen to contain any one vertex from G.V. At each step, the least-weight edge leaving T is added. The algorithm stops when T is spanning.
August 10,
53 4 12
2
6
2019
16/1
Graphs
Prim’s algorithm
How do we (efficiently) find the least-weight edge leaving T ?
Maintain a priority queue Q containing vertices V T . For each v 2 V T:
v.key: least weight of an edge connecting v to T
v.⇡ : the vertex adjacent to v on that least-weight edge
Represent
where r is the first vertex chosen for T .
T = {(v,v.⇡) : v 2 V {r} Q}
August 10, 2019 17/1
Graphs
Priority Queue
August 10, 2019
18/1
A priority queue Q maintains a set S of elements, each associated with a key, denoting its priority.
In a min-priority queue an element with the smallest key has the highest priority.
Operations are available to:
insert(Q,x)
inserts an element x with key x.key into Q
extract-min(Q)
removes and returns the element of Q with the smallest key decrease-key(Q,x,k)
decreases the key of x in Q to the value k.
Graphs
Prim’s algorithm
MST-PRIM(G,w,r)
1
2
3
4
5
6
7
8 // where T = {(v,v.⇡) : v 2 V {r} Q}
9 10 11 12 13
u = EXTRACT-MIN(Q) for each v 2 G.Adj[u]
if v 2 Q and w(u,v) < v.key v.⇡ = u
v.key = w(u, v) / Decrease key
foreachu2G.V u.key = 1
u.⇡ = NIL r.key=0
Q=G.V whileQ6=;
// invariant: T is a subset of some MST of G
August 10, 2019 19/1
Graphs
Example of Prim’s algorithm
∈A 6∞12 ∈V–A59
∞
∞∞∞
∞∞∞
14 8 7 15
∞0∞ ∞0∞
August 10, 2019
20/1
November 9, 2005
3 ∞ 10 ∞
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.27
Graphs
Example of Prim’s algorithm
∈A 6∞12 ∈V–A59
∞
∞∞∞
∞∞∞
14 8 7 15
∞0∞ ∞0∞
August 10, 2019
21/1
November 9, 2005
3 ∞ 10 ∞
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.28
Graphs
Example of Prim’s algorithm
∈A 6∞12 ∈V–A59
∞
∞7∞
∞7∞
14 8 7 15
∞ 015 ∞ 015
August 10, 2019
22/1
November 9, 2005
3 10 10 10
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.29
Graphs
Example of Prim’s algorithm
∞
∞7∞ ∞7∞
∈A 6∞12 ∈V–A59
14 8 7 15
∞ 015 ∞ 015
August 10, 2019
23/1
November 9, 2005
3 10 10 10
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.30
Graphs
Example of Prim’s algorithm
12
∈A 61212 ∈V–A59
579 579
14 8 7 15
∞ 015 ∞ 015
August 10, 2019
24/1
November 9, 2005
3 10 10 10
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.31
Graphs
Example of Prim’s algorithm
12
∈A 61212 ∈V–A59
579 579
14 8 7 15
∞ 015 ∞ 015
August 10, 2019
25/1
November 9, 2005
3 10 10 10
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.32
Graphs
Example of Prim’s algorithm
6
579 579
∈A 6612 ∈V–A59
14 8 7 15
14 015 14 015
August 10, 2019
26/1
November 9, 2005
3 8 10 8
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.33
Graphs
Example of Prim’s algorithm
6
∈A 6612
∈V–A59 579
579
14 8 7 15
14 015 14 015
August 10, 2019
27/1
November 9, 2005
3 8 10 8
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.34
Graphs
Example of Prim’s algorithm
6
∈A 6612
∈V–A59 579
579
14 8 7 15
14 015 14 015
August 10, 2019
28/1
November 9, 2005
3 8 10 8
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.35
Graphs
Example of Prim’s algorithm
6
∈A 6612
∈V–A59 579
579
14 8 7 15
3 015 3 015
August 10, 2019
29/1
November 9, 2005
3 8 10 8
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.36
Graphs
Example of Prim’s algorithm
6
∈A 6612
∈V–A59 579
579
14 8 7 15
3 015 3 015
August 10, 2019
30/1
November 9, 2005
3 8 10 8
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.37
Graphs
Example of Prim’s algorithm
6
∈A 6612
∈V–A59 579
579
14 8 7 15
3 015 3 015
August 10, 2019
31/1
November 9, 2005
3 8 10 8
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.38
Graphs
Example of Prim’s algorithm
6
∈A 6612
∈V–A59 579
579
14 8 7 15
3 015 3 015
August 10, 2019
32/1
November 9, 2005
3 8 10 8
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L16.39
Graphs
August 10, 2019
33/1
November 9, 2005
Q←V
key[v] ← ∞ for all v ∈ V
key[s] ← 0 for some arbitrary s ∈ V while Q ≠ ∅
do u ← EXTRACT-MIN(Q) for each v ∈ Adj[u]
doif v∈Qandw(u,v)
else
x.p = y
/ If equal rank, choose y as parent and increment its rank if x.rank == y.rank
y.rank = y.rank + 1
applies a union by rank heuristic:
the tree with fewer nodes is made to point to the tree with more nodes.
50/1
Graphs
Disjoint set forests: Union(x,y)
August 10,
a 0
b
0
Union(a,b)
b1 a0
2019
51/1
Graphs
Disjoint set forests: Union(x,y)
August 10,
a1 d2 b0 c00e f1
2019
52/1
Union(a,d)
g0
Graphs
Disjoint set forests: Union(x,y)
August 10,
d2 a10e f1
b0c0 g0 Union(a,d)
2019
53/1
Graphs
Kruskal’s approach
August 10, 2019
54/1
A set (of edges) T represents a tree
MST-KRUSKAL(G, w) 1T=;
2 3 4 5 6 7 8 9
for each vertex v 2 G.V MAKE-SET(v)
sort the edges of G.E into non-decreasing order by weight w for each (u, v ) taken from the sorted list
if FIND-SET(u) 6= FIND-SET(v) T = T [{(u,v)}
UNION(u,v) return T
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 55/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 56/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 57/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 58/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 59/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 60/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 61/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 62/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 63/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 64/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 65/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 66/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 67/1
Graphs
Kruskal’s MST algorithm walkthrough (CLRS Fig 23.4)
August 10, 2019 68/1
Graphs
Analysis of Kruskal
MST-KRUSKAL(G, w) 1T=;
2 3 4 5 6 7 8 9
1 2 3
for each vertex v 2 G.V MAKE-SET(v)
sort the edges of G.E into non-decreasing order by weight w for each (u, v ) taken from the sorted list
if FIND-SET(u) 6= FIND-SET(v) T = T [{(u,v)}
UNION(u,v) return T
MAKE-SET is constant time. Hence the first loop is ⇥(V). Sorting the edges is ⇥(E lg E).
The main loop is executed once per edge (|E| times). There are four calls to FIND-SET. CLRS contains a sophisticated argument that this is O(lg E).
Hence Kruskal’s algorithm using the disjoint-set forest
implementation is ⇥(E lg E ).
August 10, 2019 69/1
Graphs
Prim’s MST algorithm walkthrough (CLRS Figure 23.5)
August 10, 2019 70/1
Graphs
Prim’s MST algorithm walkthrough (CLRS Figure 23.5)
August 10, 2019 71/1
Graphs
Prim’s MST algorithm walkthrough (CLRS Figure 23.5)
August 10, 2019 72/1
Graphs
Prim’s MST algorithm walkthrough (CLRS Figure 23.5)
August 10, 2019 73/1
Graphs
Prim’s MST algorithm walkthrough (CLRS Figure 23.5)
August 10, 2019 74/1
Graphs
Prim’s MST algorithm walkthrough (CLRS Figure 23.5)
August 10, 2019 75/1
Graphs
Prim’s MST algorithm walkthrough (CLRS Figure 23.5)
August 10, 2019 76/1
Graphs
Prim’s MST algorithm walkthrough (CLRS Figure 23.5)
August 10, 2019 77/1
Graphs
Prim’s MST algorithm walkthrough (CLRS Figure 23.5)
August 10, 2019 78/1
Graphs
Prim’s MST algorithm walkthrough (CLRS Figure 23.5)
August 10, 2019 79/1
Graphs
Implementing MST algorithms
Data structures for incrementally building/maintaining the MST
Prim: a priority queue implemented using a heap
Kruskal: a disjoint set implemented using a disjoint-set forest
August 10, 2019 80/1
Graphs
MST recap
An MST gives the shortest total physical distance required to connect every node
Kruskal and Prim are two different approaches to constructing an MST
Kruskal’s algorithm requires an implementation of disjoint sets;
Prim’s algorithm requires an implementation of a priority queue
August 10, 2019
81/1
Graphs
Recap of this week
August 10, 2019
82/1
1
Minimum spanning trees Kruskal’s algorithm,
O(E lg E) using union-find trees Prim’s algorithm,
O(E lg V ) using binary heap or
O(E + V lg V ) using a Fibonacci heap