INN701 Lecture 3
Queensland University of Technology
CRICOS No. 00213J
CAB301 Algorithms and Complexity
Lecture 8 – Graph algorithms I
Maolin Tang
School of Computer Science
Queensland University of Technology
CRICOS No. 00213J
a university for the worldreal R
Aims of this lecture
• This lecture introduces graph and graph algorithms, including
– Graph
– Traversal
– Topological sort
– Minimum spanning tree
2
CRICOS No. 00213J
a university for the worldreal R
References
• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Addison-Wesley, third edition, 2012. Sections 1.4, 3.5, 4.2, 9.1 and
9.2
• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein,
Introduction to Algorithms, third edition, 2009. Chapters 22 and 23
3
CRICOS No. 00213J
a university for the worldreal R
Graph
4
CRICOS No. 00213J
a university for the worldreal R
Graph
Graph is an important mathematical concept that has significant
applications.
A graph G consists of two sets: a set V of vertices, or nodes, and
a set E of edges that connect the vertices.
A
B E
C D
vertex
edge G = ( V, E ), where V = {A, B, C, D, E} and
E = {(A, B), (A, C), (A, D), (A, E), (B, C), (C, D), (D, E)}.
5
CRICOS No. 00213J
a university for the worldreal R
Graph applications
• Some examples of graph applications:
– In Transportation, a road network is represented as a graph
• Google Maps, Apple Maps, and Uber
– In Communication, a communication network is represented as a
graph
– In Electrical Engineering, a circuit diagram is represented as a
graph
– In Social Science, a social network is represented as a graph
– …
6
CRICOS No. 00213J
a university for the worldreal R
Terminology
A
B E
C D
Graphs can be categorised into undirected graphs and directed
graphs, or digraphs.
In an undirected graph the edges do not indicate a direction. In
contrast, in a directed graph the edges indicate a direction, and
are called directed edges.
A
B E
C D
An undirected graph A directed graph
7
CRICOS No. 00213J
a university for the worldreal R
Terminology
A weighted graph is a graph whose edges have a weight.
A
B E
C D
3 4
6 7
2
1
2
8
CRICOS No. 00213J
a university for the worldreal R
Terminology
A path between two vertices is a sequence of consecutive edges
that begins at one vertex and ends at another vertex.
– e1, e3, e4 is a path between A and D.
A cycle is a path that begins and ends at the same vertex.
– e1, e3, e6 is a cycle.
A
B E
C D
e1 e2
e6 e8
e3
e4
e5
9
CRICOS No. 00213J
a university for the worldreal R
Terminology
A
B E
C D
A graph is connected if there exists a path between each pair of
distinct vertices.
– e.g., G1 is connected graph, but G2 is not (it has two
components).
A
B E
C D
G1 G2
10
CRICOS No. 00213J
a university for the worldreal R
Terminology
A
B E
C D
A subgraph of a graph consists of a subset of the graph’s vertices
and a subset of the graph’s edges.
A
B E
C D
A
B E
CG
Two subgraphs of G
11
CRICOS No. 00213J
a university for the worldreal R
Graph representations
• Two popular representations of a graph:
– Adjacency matrix
– Adjacency list
• Types of graphs:
– Unweighted undirected graphs
– Weighted undirected graphs
– Unweighted directed graphs
– Weighted directed graphs
12
CRICOS No. 00213J
a university for the worldreal R
Adjacency matrix
• An adjacency matrix for an unweighted undirected graph of N
vertices is an N×N array A such that A[i][j] is 1 (true) if there is
an edge between vertex i and vertex j, and 0 (false) otherwise.
0
1
1
1
1
1
0
0
1
0
1
0
1
0
1
1
1
0
1
0
1
0
1
0
0
A
B
C
D
E
A B C D EA
B E
C D
(a) A unweighted undirected graph (b) The adjacency matrix representation of (a)
13
CRICOS No. 00213J
a university for the worldreal R
Adjacency matrix
∞
4
7
6
3
3
∞
∞
2
∞
6
∞
1
∞
2
7
2
∞
1
∞
4
∞
2
∞
∞
A
B
C
D
E
A B C D E
(a) A weighted undirected graph (b) The adjacency matrix representation of (a)
A
B E
C D
3 4
6 7
2
1
2
An adjacency matrix for a weighted undirected graph of N
vertices is an N×N array A such that A[i][j] is the weight of the
edge between vertex i and vertex j, and ∞ otherwise.
14
CRICOS No. 00213J
a university for the worldreal R
Adjacency matrix
0
0
1
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
1
0
1
0
0
A
B
C
D
E
A B C D E
(a) A unweighted directed graph (b) The adjacency matrix representation of (a)
A
B E
C D
• An adjacency matrix for an unweighted directed graph of N
vertices is an N×N array A such that A[i][j] is 1 (true) if there is
a directed edge from vertex i to vertex j, and 0 (false) otherwise.
15
CRICOS No. 00213J
a university for the worldreal R
Adjacency matrix
∞
∞
7
∞
3
∞
∞
∞
∞
∞
6
∞
∞
∞
2
∞
∞
∞
1
∞
4
∞
2
∞
∞
A
B
C
D
E
A B C D E
(a) A weighted directed graph (b) The adjacency matrix representation of (a)
An adjacency matrix for a weighted directed graph of N
vertices is an N×N array A such that A[i][j] is the weight of the
edge between vertex i and vertex j if there is a directed edge
from vertex i to vertex j and ∞ otherwise.
16
A
B E
C D
CRICOS No. 00213J
a university for the worldreal R
Adjacency list
A
B E
C D
(a) A unweighted undirected graph (b) The adjacency matrix representation of (a)
A
B
C
D
E
B C D E ^
A C ^
A B D ^
A C E ^
A D ^
An adjacency list for an unweighted undirected graph of N
vertices consists of N linked lists, each of which represents a
vertex. The nodes in the linked list represent those vertices that
are adjacent to the vertex.
17
CRICOS No. 00213J
a university for the worldreal R
Adjacency list
A
B E
C D
3 4
6 7
2
1
2
(a) A weighted undirected graph (b) The adjacency matrix representation of (a)
A
B
C
D
E
B 3
A 6
C 6 D 7 E 4 ^
A 3 C 2 ^
B 2 D 1 ^
A 7 C 1 E 2 ^
A 4 D 2 ^
For a weighted undirected graph, there is an additional attribute
in the nodes of the linked lists, representing the weight of the
edge.
18
CRICOS No. 00213J
a university for the worldreal R
Adjacency list
^
A
B
C
D
E
C E ^
A C ^
D ^
A E ^
(a) A unweighted directed graph (b) The adjacency matrix representation of (a)
A
B E
C D
An adjacency list for an unweighted directed graph of N vertices
consists of N linked lists, each of which represents a vertex and
the nodes in the linked list represent the vertices to which there is
a directed edge from the vertex.
19
CRICOS No. 00213J
a university for the worldreal R
Adjacency list
(a) A weighted directed graph (b) The adjacency matrix representation of (a)
An adjacency list for a weighted directed graph of N vertices
consists of N linked lists, each of which represents a vertex and
the nodes in the linked list represent the vertices to which there is
a directed edge from the vertex.
20
A
B E
C D
^
A
B
C
D
E
C 6 E 4 ^
A 3 C 2 ^
D 1 ^
A 7 E 2 ^
CRICOS No. 00213J
a university for the worldreal R
Graph traversal
21
CRICOS No. 00213J
a university for the worldreal R
Graph traversal
A graph traversal visits all the vertices in a graph
Two graph traversal algorithms:
– Depth-first search traversal
– Breadth-first search traversal
22
CRICOS No. 00213J
a university for the worldreal R
Depth-first search traversal
From a given vertex v, the depth-first search traversal proceeds
along a path from v as deeply into the graph as possible before
backtracking.
A
F
ED
C
B
G
(1) (2)
(3)
(4)
(6)
(7)
(5)
23
CRICOS No. 00213J
a university for the worldreal R
Depth-first search traversal
24
CRICOS No. 00213J
a university for the worldreal R
Depth-first search traversal
25
CRICOS No. 00213J
a university for the worldreal R
Breadth-first search traversal
It starts with a given vertex. After visiting the vertex, it visits all
the unvisited vertices that are adjacent to the vertex, and then all
the unvisited vertices two edges apart from the vertex, and so
on, until all the vertices have been visited.
A
F
ED
C
B
G
(1)
(2)
(4)
(5)(3)
(6)
(7)
26
CRICOS No. 00213J
a university for the worldreal R
Breadth-first search traversal
27
CRICOS No. 00213J
a university for the worldreal R
Breadth-first search traversal
28
A
F
ED
C
B
G
CRICOS No. 00213J
a university for the worldreal R
Topological sort
29
CRICOS No. 00213J
a university for the worldreal R
Topological sort
An algorithm for Directed Acyclic Graph, or DAG – a directed
graph without cycle.
A DAG has a natural order.
– For example, in the following DAG, A precedes B, which
precedes C.
Topological sorting is to find an order of the vertices of a DAG
such that each vertex comes before all vertices to which it has an
edge.
A B C
D E F
G
30
CRICOS No. 00213J
a university for the worldreal R
Topological sort
If vertices represent units that a student needs to complete, and
directed edges represent the constraints between units,
topological sort gives the order of the units the student can take
satisfying all constraints, such as prerequisites.
– For example, AGDBECF is a feasible order to take the units.
But AGDEBCF is not.
There are several topological sort algorithms. Next slide shows a
simple topological sort algorithm.
31
CRICOS No. 00213J
a university for the worldreal R
Topological sort
ALGORITHM TopologicalSort (G)
// Input: a DAG, G(V, E)
// output: a sequence of all the vertices of G such that each
// vertex comes before all vertices to which it has an edge
G'(V’, E’) ← G(V, E)
while V’ ≠ Φ do
find a vertex v ϵ V’ such that in-degree(v) = 0
output v
remove v and all the edges adjacent to v
32
CRICOS No. 00213J
a university for the worldreal R
Topological sort – Example
A B C
D E F
G
A
B C
D E F
G
A B
C
D E F
G
A B
C
D E F G
Output:
Output:
Output:
(1)
(2)
(3)
(4)
33
CRICOS No. 00213J
a university for the worldreal R
Topological sort – Example
A B
C
DE F G
A B
C
D EF G
A B CD EF G
A B CD E FG
Output:
Output:
Output:
Output:
(5)
(6)
(7)
(8)
34
CRICOS No. 00213J
a university for the worldreal R
Minimum spanning tree
35
CRICOS No. 00213J
a university for the worldreal R
Spanning tree
A spanning tree of a connected undirected graph G is a
connected subgraph of G that all of G’s vertices and n-1 of G’s
edges, where n is the number of vertices in G.
A graph may have many different spanning trees.
Graph G A spanning tree of G
36
CRICOS No. 00213J
a university for the worldreal R
Minimum spanning tree
A minimum spanning tree of a connected undirected graph is a
spanning tree which has the minimal sum of edge weights (costs).
It may not be unique for a particular graph.
Two popular minimum spanning tree algorithms:
– Kruskal’s algorithm
– Prim’s algorithm
37
CRICOS No. 00213J
a university for the worldreal R
Kruskal’s algorithm
A simple algorithm that finds a minimum spanning tree.
It is proposed by J. Kruskal in 1956.
It sorts the edges of the graph in ascending order, and then tries
to add edges one by one to an initially empty tree. If it does not
form a cycle in the tree by adding an edge, then the edge is
included; otherwise, the edge is not included in the tree. This
process is repeated until n-1 edges have been included in the
tree, where n is the number of the vertices in the graph, and the
tree is a minimum spanning tree.
38
CRICOS No. 00213J
a university for the worldreal R
Kruskal’s algorithm
39
CRICOS No. 00213J
a university for the worldreal R
Kruskal’s algorithm
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
(1) (2) (3) (4)
(5) (6) (7)
L = [
40
CRICOS No. 00213J
a university for the worldreal R
Prim’s algorithm
Another simple algorithm that finds a minimum spanning tree.
It is proposed by R.C. Prim in 1957.
It begins at any vertex. Initially, the minimum spanning tree
contains the only starting vertex. At each stage, the algorithm
selects a least-cost edge from among those that begin with a
vertex in the tree and end with a vertex not in the tree. The latter
vertex and least-cost edge are then added to the tree. The
process is repeated until all the vertices are added to the tree.
41
CRICOS No. 00213J
a university for the worldreal R
Prim’s algorithm
42
CRICOS No. 00213J
a university for the worldreal R
Prim’s algorithm
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
(1) (2) (3) (4)
(5) (6) (7)
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
(8)
A
F
ED
C
B
G
5
7 8
9 7
5
15
6
11
9
8
43
CAB301 Algorithms and Complexity��Lecture 8 – Graph algorithms I
Aims of this lecture
References
Graph
Graph
Graph applications
Terminology
Terminology
Terminology
Terminology
Terminology
Graph representations
Adjacency matrix
Adjacency matrix
Adjacency matrix
Adjacency matrix
Adjacency list
Adjacency list
Adjacency list
Adjacency list
Graph traversal
Graph traversal
Depth-first search traversal
Depth-first search traversal
Depth-first search traversal
Breadth-first search traversal
Breadth-first search traversal
Breadth-first search traversal
Topological sort
Topological sort
Topological sort
Topological sort
Topological sort – Example
Topological sort – Example
Minimum spanning tree
Spanning tree
Minimum spanning tree
Kruskal’s algorithm
Kruskal’s algorithm
Kruskal’s algorithm
Prim’s algorithm
Prim’s algorithm
Prim’s algorithm