Graph algorithms
Data Structures and Algorithms
1
DSaA 2012/2013
Graph theory
Graph theory:
" definitions
" representation of graphs
" algorithms:
 connected components
 breadth-first search
 depth-first search
 minimum spanning tree
 single source shortest paths
 all-pairs shortest paths
2
DSaA 2012/2013
Seven Bridges of Königsberg (problem in 1736)
A
A
Degree(A) = 3
Degree(B) = 5
B D
B
D
Degree(C) = 3
Degree(D) = 3
C
C
" An Euler tour of a graph is a cycle that traverses each edge of the graph
exactly once, although it may visit a vertex more than once
A graph has an Euler tour if degree(v) is even for each vertex v.
" An Euler walk - in an graph is a path that uses each edge exactly once
An Euler walk exist if at most two vertices in the graph are of odd degree .
3
DSaA 2012/2013
Graph - definition
An undirected graph G is a pair (V, E)
where:
V is a finite set of points called vertices
E is a finite set of edges
e Îð E is an unordered pair (u, v), where u, v Îð V
(vertices u and v are connected)
An directed graph (digraph) G is a pair (V, E)
where:
V is a finite set of points called vertices
E is a finite set of edges (arcs)
e Îð E is an ordered pair (u, v), where u, v Îð V
(there is connection from u to v)
a b 1 2
c 3
f 6
d e 4 5
a) An example of an undirected graph.
b) An example of a directed graph.
4
DSaA 2012/2013
Definitions
" a path from vertex u to vertex v is a sequence (v0, v1, v2,..., vk) of
vertices
where
v0 = v, vk = u
and
(vi,vi+1) Îð E for i = 0, 1,..., k-1
" the length of a path number of edges in the path
" a path is simple if all of its vertices are distinct
" a cycle is a path where its starting and ending vertices are the
same: v0 = vk
" a graph is acyclic if it have no cycles
" a cycle is simple if all the intermediate vertices are distinct
" an graph is connected if evere pair is connected by a path
5
DSaA 2012/2013
Definitions
" a graph GI = (VI , EI) is a subgraph of G = (V, E) if VI Íð V and EIð Íð E
" the subgraph of G induced by VI Íð V is the graph GI = (VI , EI),
where EI = { (u, v) Îð E | u, v Îð VI}
" a complete graph is a graph in which each pair of vertices is
adjacent
" a forest is an acyclic graph
" a tree is a connected acyclic graph
" if G = (V, E) is a tree, then |E| = |V| - 1
" a weighted graph (digraph) G is a triple (V, E, w)
where:
V, E like before
w : E ®ð Âð is real-valued function defined on E
" the weight of graph is the sum of the weight of its edges
" the weight of a path is the sum of the weight of its edges
6
DSaA 2012/2013
Graph s representation in memory
" the adjacency matrix of graph G = (V, E) is an n × n array (n=|V|)
A = (ai,j), which elements are defined as follows:
1 (vi,vj) Îð E
ìð
=ð
ai,j
íð
0 otherwise
îð
" the weighted adjacency matrix, like the adjacency matrix:
w(vi,vj) if (vi,vj) Îð E
ìð
ïð
ai,j 0 if i = j
=ð
íð
ïð
" otherwise
îð
" the adjacency list of graph G = (V, E) is an array Adj[1..|V|] of lists.
For each v Îð V, Adj[v] is a linked list of all vertices adjacent to v.
" the weighted adjacency list. Simple modification of the adjacency
list to accommodate weighted graph.
7
DSaA 2012/2013
Example
1
éð0 1 0 0 0Å‚ð
Ä™ð1 0 1 0 1Å›ð a) An undirected graph and its adjacency
matrix representation.
Ä™ð Å›ð
2 3
A=ð 0 1 0 0 1
Ä™ð Å›ð
Ä™ð0 0 0 0 1Å›ð
Ä™ð Å›ð
Ä™ð0 1 1 1 0Å›ð
ëð ûð
4 5
1 2
2 1 3 5
b) An undirected graph and its adjacency
list representation.
3 2 5
4 5
5 2 3 4
8
DSaA 2012/2013
Why/where
With graphs we can express:
" nets
 computer nets
 traffic nets
 urban nets
 & nets
" person connections
" technology processes
" work flow
" & .
9
DSaA 2012/2013
Connected components
In an undirected graph, a connected component or
component is a maximal connected subgraph. Two
vertices are in the same connected component if and
only if there exists a path between them
1 4
6 9
2 3
5 7 8
A graph with three connected components.
ConnectedComponents(G,w)
{ 1} for each vertex uÎðV[G] do
{ 2} MakeSet(v)
{ 3} for each edge (u,v)ÎðE do
{ 4} if FindSet(u) Ä…ð FindSet(v) then
{ 5} Union(u,v)
{ 6} A := Ćð
{ 7} for each vertex uÎðV[G] do
{ 8} A:=A Èð FindSet(u)
{ 9} return card(A) // number of elements in A set
10
DSaA 2012/2013
Connected components - example
V = { a, b, c, d, e, f, g, h, i}
E = { (a,c), (d,f), (d,i), (f,i), (e,h), (b,g), (a,b), (b,c), (c,g) }
{a} {a,c} {a,c} {a,c} {a,c} {a,c} {a,c} {a,c,b,g}
{b} {b} {b} {b} {b} {b} {b,g}
{c}
{d} {d} {d,f} {d,f,i} {d,f,i} {d,f,i} {d,f,i} {d,f,i}
{e} {e} {e} {e} {e} {e,h} {e,h} {e,h}
{f} {f}
{g} {g} {g} {g} {g} {g}
{h} {h} {h} {h} {h}
{i} {i} {i}
c g
d h
Complexity (adjacent lists): O(|V|+|E|)
a b
f i e
Complexity (adjacent matrix): O(|V|2)
11
DSaA 2012/2013
Breadth-first search
Given a graph G = (V, E) and a distinguished source vertex s, breadth-first search
systematically explores the edges of G to "discover" every vertex that is reachable
from s. It computes the distance (smallest number of edges) from s to each reachable
vertex. It also produces a "breadth-first tree" with root s that contains all reachable
vertices. For any vertex v reachable from s, the path in the breadth-first tree from s to
v corresponds to a "shortest path" from s to v in G, that is, a path containing the
smallest number of edges. The algorithm works on both directed and undirected
graphs.
Breadth-first search is so named because it expands the frontier between discovered and
undiscovered vertices uniformly across the breadth of the frontier. That is, the
algorithm discovers all vertices at distance k from s before discovering any vertices at
distance k + 1.
s
12
DSaA 2012/2013
BFS - code
" Breadth-first search colors each vertex white, gray, or black (color)
" Breadth-first search constructs a breadth-first tree, initially containing only
its root, which is the source vertex s
" Predecessor of u is stored in the variable p[u]
" The distance from the source s to vertex u computed by the algorithm is
stored in d[u].
r s t u
BFS(G,s)
Ä„ð 0 Ä„ð Ä„ð
{ 1} for every vertex uÎðV[G]-{s}
{ 2} do color[u]:=WHITE
{ 3} d[u]:= Ä„ð
Ä„ð Ä„ð Ä„ð Ä„ð
{ 4} p[u] := NIL
v w x y
{ 5} color[s]:=GREY
{ 6} d[s]:=0
r s t u v w x y
{ 7} p[s]:=NIL
{ 8} Enqueue(Q,s)
p
{ 9} while not Empty(Q)
{10} do u:=Dequeue(Q)
s
Q
{11} for every vÎðAdj[u]
{12} do if color[v]=WHITE
{13} then color[v]:=GREY
black
{14} d[v]:=d[u] + 1
{15} p[v]:=u
gray
{16} Enqueue(Q, v)
{17} color[u]:=BLACK
white
13
DSaA 2012/2013
BFS - example
r s t u
r s t u v w x y
1 0 Ä„ð Ä„ð s s
p
Ä„ð 1 Ä„ð Ä„ð w r
Q
v w x y
r s t u
r s t u v w x y
1 0 2 Ä„ð s w s w
p
Ä„ð 1 2 Ä„ð r t x
Q
v w x y
r s t u
r s t u v w x y
1 0 2 Ä„ð s w r s w
p
2 1 2 Ä„ð t x v
Q
v w x y
14
DSaA 2012/2013
BFS - example
r s t u
r s t u v w x y
1 0 2 3 s w t r s w
p
2 1 2 Ä„ð x v u
Q
v w x y
r s t u
r s t u v w x y
1 0 2 3 s w t r s w x
p
2 1 2 3 v u y
Q
v w x y
r s t u
r s t u v w x y
1 0 2 3 s w t r s w x
p
2 1 2 3 u y
Q
v w x y
15
DSaA 2012/2013
BFS - example
r s t u
r s t u v w x y
1 0 2 3 s w t r s w x
p
2 1 2 3 y
Q
v w x y
r s t u
r s t u v w x y
1 0 2 3 s w t r s w x
p
2 1 2 3
Q
v w x y
PrintPath(G,s,v)
{ 1} if v = s
{ 2} then print s
{ 3} else if p[v] = NIL
{ 4} then print  no path from s  to v  exists
{ 5} else PrintPath(G, s, p[v])
{ 6} print v
Complexity (adjacent lists): O(|V|+|E|) Complexity (adjacent matrix): O(|V|2)
16
DSaA 2012/2013
Depth-first search
" In depth-first search, edges are explored out of the most recently discovered vertex v
that still has unexplored edges leaving it. When all of v's edges have been explored,
the search "backtracks" to explore edges leaving the vertex from which v was
discovered. This process continues until we have discovered all the vertices that are
reachable from the original source vertex. If any undiscovered vertices remain, then
one of them is selected as a new source and the search is repeated from that source.
This entire process is repeated until all vertices are discovered
" Besides creating a depth-first forest, depth-first search also timestamps each vertex.
Each vertex v has two timestamps: the first timestamp d[v] records when v is first
discovered (and grayed), and the second timestamp f [v] records when the search
finishes examining v's adjacency list (and blackens v)
1
2
4
6
8
5
3 9
7
17
DSaA 2012/2013
DFS - code
DFS(G,s)
u v w
{ 1} for each vertex uÎðV[G] do
1/
{ 2} color[u]:=WHITE
{ 3} p[u] := NIL
{ 4} time:=0
{ 5} for each vertex uÎðV[G] do
x y z
{ 6} if color[u]=WHITE then
{ 7} DFS_Visit(u)
u v w
1/ 2/
DFS_VISIT(u)
{ 1}
color[u]:=GREY
{ 2}
time:=time+1
{ 3}
t[u]:=time
x y z
{ 4}
for each vÎðAdj[u] do
{ 5}
if color[v]=WHITE then
{ 6}
p[v] := u
u v w
{ 7}
DFS_Visit(v)
1/ 2/
{ 8}
color[u]:=BLACK
{ 9}
f[u] := time := time+1;
3/
x y z
18
DSaA 2012/2013
DFS - example
u v w u v w u v w
1/ 2/ 1/ 2/ 1/ 2/
B B B
4/ 3/ 4/5 3/ 4/5 3/6
x y z x y z x y z
u v w u v w u v w
1/ 2/7 1/ 2/7 1/8 2/7
B F B F B
4/5 3/6 4/5 3/6 4/5 3/6
x y z x y z x y z
u v w u v w u v w
1/8 2/7 9/ 1/8 2/7 9/ 1/8 2/7 9/
F B F B F B
C C
4/5 3/6 4/5 3/6 4/5 3/6 10/
x y z x y z x y z
19
DSaA 2012/2013
DFS - example
u v w u v w u v w
1/8 2/7 9/ 1/8 2/7 9/ 1/8 2/7 9/12
F B B F B B F B B
C C C
4/5 3/6 10/ 4/5 3/6 10/11 4/5 3/6 10/11
x y z x y z x y z
B  back edge
F  forward edge
C  cross edge
Complexity (adjacent lists): O(|V|+|E|) Complexity (adjacent matrix): O(|V|2)
20
DSaA 2012/2013
Minimum spanning tree (MST)
" Given a connected, undirected graph, a spanning tree
of that graph is a subgraph which is a tree and
connects all the vertices together.
" A minimum spanning tree or minimum weight
spanning tree is then a spanning tree with weight less
than or equal to the weight of every other spanning tree
Kruskal's algorithm
" create a forest F (a set of trees), where each vertex in the graph is a
separate tree
" create a set S containing all the edges in the graph
" while S is nonempty
" remove an edge with minimum weight from S
" if that edge connects two different trees, then add it to the forest,
combining two trees into a single tree
" otherwise discard that edge
21
DSaA 2012/2013
Kruskal's algorithm - example
4 2 4 2
a b c a b c
3 3
2 3 8 2 3 8
9 9
e e
4 4
1 1
f f
5 5
d d
g g
7 7
h h
5 5
6 6
4 2
a b c 4 2
a b c
3
2 3 8
3
2 3 8
9
e
9
4
e
1
f 4
5
d 1
f
5
d
g
7
h
5
g
7
6
h
5
6
4 2
a b c 4 2
a b c
3
2 3 8
3
2 3 8
9
e
9
4
e
1
f 4
5
d 1
f
5
d
g
7
h
5
g
7
6
h
5
6
22
DSaA 2012/2013
Kruskal's algorithm - example
4 2 4 2
a b c a b c
3 3
2 3 8 2 3 8
9 9
e e
4 4
1 1
f f
5 5
d d
g g
7 7
h h
5 5
6 6
4 2
4 2
a b c
a b c
3
3
2 3 8
2 3 8
9
9
e
e
4
4
1
1
f
5
f
5
d
d
g
7
g
7
g
5
h
5
6
6
4 2
4 2
a b c
a b c
3
3
2 3 8
2 3 8
9
9
e
e
4
4
1
1
f
5
f
5
d
d
g
7
g
7
h
5
h
5
6
6
23
DSaA 2012/2013
Kruskal s algorithm - code
MST(G,w)
{ 1} A := Ćð
{ 2} for each vertex uÎðV[G]
{ 3} do MakeSet(v)
{ 4} sort the edges of E into nondecreasing order by weight w
{ 5} for each edge (u,v)ÎðE, taken in nondecreasing order by weight
{ 6} do if FindSet(u) Ä…ð FindSet(v)
{ 7} then A:=A Èð {(u,v)}
{ 8} Union(u,v)
{ 9} return A
Complexity (adjacent lists): O(|E|logIE|)
24
DSaA 2012/2013
Single-source shortest paths
" The shortest path problem is the problem of finding a
path between two vertices such that the sum of the
weights of its constituent edges is minimized
" The single-source shortest path problem is a more
general problem, in which we have to find shortest paths
from a source vertex v to all other vertices in the graph
1. procedure Dijkstra_Single_Source_SP(V,E,w,s)
2. begin
3. VT := {s};
4. for all v Îð (V - VT) do
5. if edge(s, v) exists then l[v] := w(s, v);
6. else set l[v] := Ä„ð;
7. while VT Ä…ð V do
greedy
8. begin
algorithm
9. find a vertex u such that l[u] = min{ l[v] | v Îð (V - VT)};
10. VT := VT Èð {u};
11. for all v Îð (V - VT) do
12. l[v] = min{ l[v], l[u] + w(u, v) };
13. endwhile
14. end Dijkstra_Single_Source_SP
25
DSaA 2012/2013
SSSP - example
e h e h
b b
4 2 4 2
2 Ä„ð Ä„ð 2 6 Ä„ð
3 3
d d
2 3 8 2 3 8
1 1
Ä„ð 5
4 4
a 1 a 1
Ä„ð Ä„ð
5 5
0 0
g g
5 5
7 7
Ä„ð 11
5 5
6 6
c c
f f
e h
b
4 2
2 6 Ä„ð
e h
b
3
4 2
d
2 3 8
2 6 Ä„ð
1
5
4
3
d
a 1
2 3 8
Ä„ð
5
0
1
5 g
4
5
7
a 1
6
Ä„ð 5
5
0 6
c
g
f
5
7
Ä„ð
5
6
c
f
26
DSaA 2012/2013
SSSP - example
e h
e h
b
b
4 2
4 2
2 6 8
2 6 8
3
3
d
d
2 3 8
2 3 8
1
1
5
5
4
4
a 1
a 1
9
14 5
5
0
0
g
g
5
5 7
7
6
6 5
5
6
6
c
c
f
f
e h
b
4 2
2 6 8
e h
b
4 2
3
2 6 8 d
2 3 8
1
3 5
d
2 3 8
4
a 1
1 9
5
5
0
4
g
a 1
13
5 5
7
0
6
5
g
6
c
5
7
f
6
5
6
c
f
Complexity (binary heap): O(V log V + E log V)
Complexity (Fibonacci heap): O(V log V + E)
27
DSaA 2012/2013
MST  Prim s algorithm
" use the same idea as in Dijkstra_Single_Source_SP
" the difference is only in line 12, in which this algorithm
take into consideration only the weight of a edge (but not
a sum)
1. procedure Prim_MST(V,E,w,s)
2. begin
3. VT := {s};
4. for all v Îð (V - VT) do
5. if edge(s, v) exists then d[v] := w(s, v);
6. else set d[v] := Ä„ð;
7. while VT Ä…ð V do
8. begin
9. find a vertex u such that d[u] = min{ d[v] | v Îð (V - VT)};
10. VT := VT Èð {u};
11. for all v Îð (V - VT) do
12. d[v] = min{ d[v], w(u, v) };
13. endwhile
14. end Prim_MST
28
DSaA 2012/2013
All-pairs shortest paths
" run single-source shortest paths algorithm
for each vertex
 complexity of Dijkstra s algorithm for single
source shortest paths:O(V log V + E)
 complexity for V vertices: O(V2log V+V*E)
" if we have a graph with negative weights
(but without negative cycles):
 Bellman-Ford algorithm single source shortest
paths can be used. Complexity: O(VE)
 complexity for V vertices : O(V2E)
29
DSaA 2012/2013
Floyd s algorithm  structure of the path
Let pij(k) means shortest path form vertex i to wertex j with intermediate vertices from a
Let pij(k) means shortest path form vertex i to wertex j with intermediate vertices from a
set {1, 2, ..., k}. Let dij(k) means weight of the path.
set {1, 2, ..., k}. Let dij(k) means weight of the path.
all intermediate vertices in {1, 2,.., k-1}
all intermediate vertices in {1, 2,.., k-1}
all intermediate vertices in {1, 2,.., k-1}
k
i j
all intermediate vertices in {1, 2,.., k-1}
wij if k =ð 0
ìð
(
dynamic
dijk ) =ð
íðmin programming
(ð (ð (ð
(ðdijk -ð1)ð, dikk -ð1)ð +ð dkjk -ð1)ð)ð if k Å‚ð1
îð
30
DSaA 2012/2013
Floyd s algorithm  code, example
1. procedure FLOYD_ALL_PAIRS_SP(A)
2. begin
3. D(0) = A;
complexity:
4. for k = 1 to n do
5. for i = 1 to n do O(V3)
6. for j = 1 to n do
7. d(k)i,j := min( d(k-1)i,j, d(k-1)i,k + d(k-1)k,j );
8. end FLOYD_ALL_PAIRS_SP
4 2
2 5 8
0 2 5 Ä„ð Ä„ð Ä„ð Ä„ð Ä„ð
ìð
3
2 3 8 ïð
2 0 Ä„ð 3 4 Ä„ð Ä„ð Ä„ð
1
4
ïð
4
1
7
5
ïð
5 Ä„ð 0 5 Ä„ð 6 Ä„ð Ä„ð
1
ïð
3
7
6
5
ïðÄ„ð 3 5 0 3 1 Ä„ð Ä„ð
6
D(ð0)ð =ð
íð
ïðÄ„ð 4 Ä„ð 3 0 4 8 2
ïðÄ„ð Ä„ð 6 1 4 0 7 Ä„ð
Given a directed graph G = (V, E) with vertex set
V={1,2,...,n}, we may wish to find out whether there is a
ïð
path in G from i to j for all vertex pairs i, j V. The transitive
ïðÄ„ð Ä„ð Ä„ð Ä„ð 8 7 0 1
closure of G is defined as the graph G* = (V, E*), where
ïðÄ„ð Ä„ð Ä„ð Ä„ð 2 Ä„ð 1 0
E*= {(i, j) : there is a path from vertex i to vertex j in G}.
îð
31
DSaA 2012/2013
Floyd s algorithm  example
0 2 5 Ä„ð Ä„ð Ä„ð Ä„ð Ä„ð 0 2 5 5 6 Ä„ð Ä„ð Ä„ð
ìð ìð
ïð ïð
2 0 7 3 4 Ä„ð Ä„ð Ä„ð 2 0 7 3 4 Ä„ð Ä„ð Ä„ð
ïð ïð
ïð ïð
5 7 0 5 Ä„ð 6 Ä„ð Ä„ð 5 7 0 5 11 6 Ä„ð Ä„ð
ïð ïð
5 3 5 0 3 1 Ä„ð Ä„ð
ïðÄ„ð 3 5 0 3 1 Ä„ð Ä„ð D(ð2)ð =ð ïð
D(ð1)ð =ð
íð íð
6 4 11 3 0 4 8 2
ïðÄ„ð 4 Ä„ð 3 0 4 8 2 ïð
ïðÄ„ð Ä„ð 6 1 4 0 7 Ä„ð ïðÄ„ð Ä„ð 6 1 4 0 7 Ä„ð
ïð ïð
ïðÄ„ð Ä„ð Ä„ð Ä„ð 8 7 0 1 ïðÄ„ð Ä„ð Ä„ð Ä„ð 8 7 0 1
ïðÄ„ð Ä„ð Ä„ð Ä„ð 2 Ä„ð 1 0 ïðÄ„ð Ä„ð Ä„ð Ä„ð 2 Ä„ð 1 0
îð îð
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
ìð ìð
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð ïð
ïð ïð
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð ïð
D(ð3)ð =ð D(ð4)ð =ð
íð_ _ _ _ _ _ _ _ íð_ _ _ _ _ _ _ _
ïð ïð
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð ïð
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
îð îð
32
DSaA 2012/2013
Floyd s algorithm  example
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
ìð ìð
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð ïð
ïð ïð
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð ïð
D(ð5)ð =ð D(ð6)ð =ð
íð_ _ _ _ _ _ _ _ íð_ _ _ _ _ _ _ _
ïð ïð
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð ïð
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
îð îð
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
ìð ìð
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð ïð
ïð ïð
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð ïð
D(ð7)ð =ð D(ð8)ð =ð
íð_ _ _ _ _ _ _ _ íð_ _ _ _ _ _ _ _
ïð ïð
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð ïð
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
ïð_ _ _ _ _ _ _ _ ïð_ _ _ _ _ _ _ _
îð îð
33
DSaA 2012/2013