Graphs
Introduction to Graph Algorithms COMP4500/7500
Advanced Algorithms & Data Structures
August 29, 2019 1/43
Graphs
Overview
What have we done so far and why? Introduction to graphs
Representing graphs
Breadth-first search
Depth-first search
August 29, 2019 2/43
Graphs
What have we done and why?
Goal: To be able to efficiently solve complex problems First: we need to be able to analyse the efficiency of algorithms.
There are different measures of efficiency, e.g. time, space.
How efficient an algorithm is depends on its input size and input value.
We can describe the best, average or worst case as a
function of input size.
Functions can be described and compared using asymptotic notation.
Θ: asymptotic tight bounds O: asymptotic upper bounds Ω: asymptotic lower bounds
August 29, 2019 3/43
Graphs
Quick question
Which asymptotic notation (e.g. O, Ω, Θ) do we use to describe
worst case time complexity? best case time complexity? average case time complexity?
August 29, 2019 4/43
Graphs
What have we done and why?
Non-trivial algorithms use loops and/or recursion Loops can be analysed using summations
n T(n) = i2
i=0
Recursive programs can be analysed using recurrences
T(n) = 2T(n/2) + n
Use mathematical/logical reasoning to convert these into a statement in terms of asymptotic notation: Θ(n2).
August 29, 2019 5/43
Graphs
Graphs
A
B
E
@ @
@
C
D
F
Made up of
Vertices
A, B, C, D, E, F
Edges
(A,B), (A,D), (A,C), (B,D), (C,D), (E, D), (E, F), (D, F)
August 29, 2019 6/43
Graphs
Graphs
A
B
E
Could be used to represent
Geographical information (Vertices = cities, Edges = roads) Networks (Vertices = computers, Edges = cables)
Brains (Vertices = neurons, Edges = synapses)
Programs (Vertices = statements, Edges = control flow)
@ @
@
C
D
F
August 29, 2019 7/43
Graphs
Graphs: Key property: directed or undirected
Undirected:
A
B
@ @
@
E
C
D
F
Cannot have self-loops.
If (u,v) ∈ E(G), v is adjacent to u in G (symmetric). Edge (u,v) ∈ E(G) is incident on vertices v and u
The degree of a vertex v is the number of edges incident upon it.
August 29, 2019 8/43
Graphs
Graphs: Key property: directed or undirected
Directed:
–
6@ @
@R? ? D-F
Can have self-loops.
If (u,v) ∈ E(G), v is adjacent to u in G (asymmetric). Edge (u,v) ∈ E(G) is incident from (leaves) vertex u and incident on (enters) vertices v.
The out-degree of a vertex v is the number of edges leaving it.
The in-degree of a vertex v is the number of edges entering it.
The degree of a vertex is the sum of its in-degree and out-degree.
A
B
E
C
August 29, 2019 9/43
Graphs
Quick question
What (exactly) is the maximum number of edges in an: directed graph with n vertices? n2
undirected graph with n vertices?
n−1 i = n(n − 1)/2 i=0
August 29, 2019 10/43
Graphs
Graphs: Key property: weighted or unweighted
Unweighted:
A
B
E
@ @
@
C
D
F
August 29, 2019 11/43
Graphs
Graphs: Key property: weighted or unweighted
Weighted: 0.6
–
6
1.2 2.5
? -F
0.9 3.1
A
B
E
C
D
August 29, 2019 12/43
Graphs
Graphs: terminology
For a graph G = (V,E):
Apathoflengthk fromavertexv0 toavertexvk isa sequence ⟨v0, v1, v2, . . . , vk ⟩ of vertices such that (vi−1,vi) ∈ E for i ∈ 1,2,…,k.
u is reachable from v if there is a path from v to u.
A path is simple if all vertices in the path are distinct.
Apathformsacycleifv0 =vk andk >1.
A cycle is simple if v1,…,vk are distinct and all of its edges are distinct.
A graph with no simple cycles is acyclic.
August 29, 2019 13/43
Graphs
Graphs: terminology
An undirected graph G = (V,E) is:
connected if every vertex is reachable from all other
vertices.
a forest if it has acyclic.
a tree if it is a forest with only one connected component.
August 29, 2019 14/43
Graphs
Quick question
(For an undirected graph:)
What are the minimum and maximum number of edges in a: tree with n vertices? (n−1, n−1)
forest with n vertices? (0, n−1)
connected graph with n vertices? (n − 1, n(n−1)/2)
August 29, 2019 15/43
Graphs
Graphs: terminology
An directed graph G = (V,E) is:
strongly connected if there every two vertices are reachable from each other.
August 29, 2019 16/43
Graphs
Graphs: terminology
Graph G′ = (V′,E′) is a sub-graph of G = (V,E) when V′ ⊆V andE′ ⊆E.
Additionally, G′ is a spanning sub-graph of G if V′ = V also holds.
The sub-graph of G = (V,E) that is induced by V’ is the graph G′ = (V′,E′) where
E′ ={(u,v)∈E:u∈V′∧v∈V′}.
August 29, 2019 17/43
Graphs
Graphs
Information about graphs we may need:
Shortest path from vertex v to vertex u
Shortest path from vertex v to every other vertex Does the graph contain cycles?
Is it connected?
Find a minimum spanning tree?
Shortest tour of all vertices(?)
Graphs will be used to explore different programming styles throughout the course.
August 29, 2019 18/43
Graphs
Types of graphs
Directed Acyclic Graph (DAG) Connected graph
Trees are special types of graphs Lists/vectors are also simple graphs
August 29, 2019 19/43
Graphs
Graph representations
There are two main approaches to representing graphs: Adjacency list
Adjacency matrix
(Representing the set of vertices and edges directly is usually too inefficient.)
August 29, 2019 20/43
Graphs
Graph representations: adjacency list (undirected)
Node Connections
A B,D,C
B A,D
C A,D
D A,B,C
For undirected graph G = (V,E) with V vertices and E edges what is the worst-case:
space complexity?
Θ(V + v∈G.V degree(v)) = Θ(V + 2E) ∈ Θ(V + E)
time complexity of isAdjacentTo(u, v )? Θ(V )
time complexity to list all adjacent vertex pairs? Θ(V + v∈G.V degree(v)) = Θ(V + 2E) ∈ Θ(V + E)
A
B
@ @
@
C
D
August 29, 2019 21/43
Graphs
Graph representations: adjacency list (directed)
– Node Connections A B, D
A
6@ @
@R ?
D
BD CA DC
B
C
For directed graph G = (V,E) with V vertices and E edges what is the worst-case:
space complexity?
Θ(V + v∈G.V outDegree(v)) = Θ(V + E)
time complexity of isAdjacentTo(u, v )? Θ(V )
time complexity to list all adjacent vertex pairs? Θ(V + v∈G.V outDegree(v)) = Θ(V + E)
August 29, 2019 22/43
Graphs
Graph representations: adjacency matrix (undirected)
ABCD A- B– C– D-
For undirected graph G = (V,E) with V vertices and E edges what is the worst-case:
space complexity? Θ(V2)
time complexity of isAdjacentTo(u, v )? Θ(1)
time complexity to list all adjacent vertex pairs? Θ(V2)
A
B
@ @
@
C
D
August 29, 2019 23/43
Graphs
Graph representations: adjacency matrix (directed)
– ABCD A--
A
6@ @
R@ ?
D
B— C— D–-
B
C
For undirected graph G = (V,E) with V vertices and E edges what is the worst-case:
space complexity? Θ(V2)
time complexity of isAdjacentTo(u, v )? Θ(1)
time complexity to list all adjacent vertex pairs? Θ(V2)
August 29, 2019 24/43
Graphs
Comparison of graph representations
The adjacency list representation is often the most efficient is the graph is sparse: few edges relative to the number of vertices.
The adjacency matrix representation is often most efficient if the graph is dense: many edges relative to the number of vertices.
August 29, 2019 25/43
Graphs
Graph traversal algorithms
Breadth-first search Depth-first search
August 29, 2019 26/43
Graphs
Breadth-First Search (BFS)
For an unweighted graph G:
The length of a path is the number of edges in that path.
E.g. the length of ⟨v1, v2, v3⟩ is 2.
The distance from vertex u to v is the length of the
shortest path from u to v in G. Breadth-first search (BFS):
Takes as input a unweighted graph G = (V,E) and a designated start vertex v ∈ G.V .
Traverses vertices in G in order of their distance from a v. Finds shortest paths from v to every other vertex in G.
August 29, 2019 27/43
Graphs
Breadth-First Search (BFS)
E.g. a possible traversal order of a tree:
August 29, 2019 28/43
Graphs
Breadth-First Search (BFS): How do we implement it?
What do we know?
1 Start vertex v is at a distance 0 from itself.
2 The vertices adjacent to v, other than those at distance 0, are at distance 1.
3 The vertices adjacent to v’s adjacent vertices, other than those at distance 0 or 1, are at distance 2.
4 etc.
August 29, 2019 29/43
Graphs
Breadth-First Search (BFS): How do we implement it?
We will use a queue data structure: Vertices are:
enqueued in order of their distance from the start vertex, dequeued in order of their distance from the start vertex.
The first element added to the queue is the start vertex. When a vertex is dequeued, its adjacent vertices that have
not yet been reached are enqueued.
How do we keep track of which vertices have been reached?
August 29, 2019 30/43
Graphs
Breadth-First Search (BFS): How do we implement it?
Colours are used distinguish vertices at different stages within the algorithm:
White: not reached yet
(i.e. never enqueued – a shortest path not yet found)
Grey: reached but all adjacent vertices not reached yet (i.e. enqueued but not dequeued – a shortest path found)
Black: reached and completed
(i.e. enqueued and dequeued – a shortest path found)
August 29, 2019 31/43
Graphs
BFS pseudo-code
Finding a path: keep track of the predecessor of each vertex BFS(G,v)
1 2 3 4 5 6 7 8 9
10 11 12 13
foruinG.V-{v}
u.distance = ∞ ; u.colour = white ; u.parent = NULL
v.distance = 0 ; v.colour = grey ; v.parent = NULL Q.initialise()
Q.enqueue(v)
while not Q.isEmpty()
current = Q.dequeue()
for u in G.adjacent[current]
if u.colour == white
u.distance = current.distance + 1 u.colour = grey ; u.parent = current Q.enqueue(u)
current.colour := black
August 29, 2019 32/43
Graphs
BFS: worst-case time complexity?
BFS(G,v)
1 2 3 4 5 6 7 8 9
10 11 12
foruinG.V-{v}
u.distance = ∞ ; u.colour = white
v.distance = 0 ; v.colour = grey Q.initialise() ; Q.enqueue(v) while not Q.isEmpty()
current = Q.dequeue()
for u in G.adjacent[current]
if u.colour == white
u.distance = current.distance + 1 u.colour = grey
Q.enqueue(u)
current.colour := black
Θ(V)+Θ(1)+(v∈G.V Θ(1)+outDegree(v)×Θ(1)) = Θ(V +E)
August 29, 2019 33/43
Graphs
Depth-first Search (DFS)
Doesn’t necessarily find shortest-paths.
Often used as a subroutine within other algorithms.
A recursive algorithm that visits a vertex v by:
choosing a unvisited vertex u adjacent to v
visiting u and all of its unvisited reachable vertices,
before backtracking to v and continuing until v has no more unvisited adjacent vertices.
August 29, 2019 34/43
Graphs
Depth-first Search (DFS)
E.g. a possible traversal order of a tree:
August 29, 2019 35/43
Graphs
DFS pseudo-code
DFS(G)
1 2 3 4
foruinG.V
u.color = white
foruinG.V
if u.colour == white then DFS-VISIT(G, u)
DFS-VISIT(G,v)
1 2 3 4 5
v.colour = grey for u in adjacent[v]
if u.colour == white DFS-VISIT(G, u)
v.colour = black
August 29, 2019 36/43
Graphs
DFS pseudo-code: recording predecessor subgraph
DFS(G)
1 2 3 4
foruinG.V
u.color = white ; u.parent = NULL
foruinG.V
if u.colour == white then DFS-VISIT(G, u)
DFS-VISIT(G,v)
1 2 3 4 5 6
v.colour = grey for u in adjacent[v]
if u.colour == white u.parent = v
DFS-VISIT(G, u) v.colour = black
August 29, 2019 37/43
Graphs
DFS: worst case time complexity?
DFS(G)
1 2 3 4
foruinG.V
u.color = white
foruinG.V
if u.colour == white then DFS-VISIT(G, u)
DFS-VISIT(G,v)
1 2 3 4 5
v.colour = grey for u in adjacent[v]
if u.colour == white DFS-VISIT(G, u)
v.colour = black
Θ(V) + (v∈G.V Θ(1) + outDegree(v) × Θ(1)) = Θ(V + E)
August 29, 2019 38/43
Graphs
DFS pseudo-code: with timestamps
DFS(G)
1 2 3 4 5
1 2 3 4 5 6 7
time=0 foruinG.V
u.color = white foruinG.V
if u.colour == white then DFS-VISIT(G, u) DFS-VISIT(G,v)
time = time + 1 ; u.discovered = time v.colour = grey
for u in adjacent[v]
if u.colour == white DFS-VISIT(G, u)
v.colour = black
time = time + 1 ; u.finished = time
August 29, 2019 39/43
Graphs
Topological sort
A directed acyclic graph (DAG) is a directed graph with no cycles.
The directed edges in a DAG can be thought of as dependencies between vertices.
A topological sort of a directed acyclic graph G = (V , E ) is a linear ordering of V such that:
if (u,v) ∈ E,
then u comes before v in the topological ordering.
August 29, 2019 40/43
Graphs
Topological sort
August 29, 2019 41/43
Graphs
Topological sort
TOPOLOGICAL-SORT(G)
1 initialise an empty linked-list of vertices
2 call DFS(G)
3 as each vertex is finished, insert it onto the front of a linked list
4 return the list of vertices
i.e. returns vertices in descending order of their DFS finish time.
August 29, 2019 42/43
Graphs
Recap
Graphs are a commonly occurring structure in difficult problems
Can be
directed, undirected cyclic, acyclic weighted, unweighted
Often represented as an adjacency list or adjacency matrix Breadth-first search is used for finding shortest-paths
Depth-first search is used for probing the structure of the graph (e.g., topological sort)
August 29, 2019 43/43