Elementary Graph Algorithms
Representations of graphs:
undirected graph
1 2
5 4
• G = ( V, E ) is a undirected graph, V denotes a
vertex, and E = ( u, v ) the edge of G.
2
Representation by adjacency-list
• Adjacency-list
1 2 5
2 1 3 4 5
3 2 4
4 2 3 5
5 1 2 4
3
Representation by adjacency-matrix
• Adjacency-matrix
1 2 3 4 5
1 0 1 0 0 1
2 1 0 1 1 1
3 0 1 0 1 0
4 0 1 1 0 1
5 1 1 0 1 0
4
Representations of graphs: Directed
graph
• Directed graph
1 2
5 4
• G = ( V, E ) is a directed graph, V denotes a
vertex, and E = ( u, v ) the edge of G.
5
Adjacency-list
• Adjacency-list
1 2 5
2 3 4
3 3 4
4 1
5 4
6
Adjacency-matrix
• Adjacency-matrix
1 2 3 4 5
1 0 1 0 0 1
2 0 0 1 1 0
3 0 0 1 1 0
4 1 0 0 0 0
5 0 0 0 1 0
7
Breadth-first search
Given a graph G = ( V, E ) and a distinguish source
vertex s, breadth-first search ( BFS ) systematically
explores the edges of G to “discover” every vertex
that is reachable from s. It computes the distance
( fewest number of edges ) from s to all such
reachable vertices.
8
Breadth-first search
It also produces a “breadth-first tree” with
root s that contains all such 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. The algorithm works on both directed
and undirected graphs.
9
Breadth-first search
BFS is so named because it expands in 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.
10
Breadth-first search
To keep track of process, BFS colors each
vertex white, green or red. All vertices start out
white and may later become green and then red.
A vertex is discovered the first time it is
encountered during the search, at which time it
becomes nonwhite.
11
Breadth-first search
Green and red vertices, therefore, have been
discovered, but BFS distinguishes between
them to ensure that the search proceeds in a
breadth-first manner.
12
Breadth-first search
It ( u, v ) ∈ E and vertex u is red, then
vertex v is either green or red; that is, all
vertices adjacent to red vertices have
been discovered. Green vertices may
have some adjacent white vertices; they
represent the frontier between discovered
and undiscovered vertices.
13
Data Structures used in BFS
The BFS procedure assumes that the input
graph G = ( V, E ) is represented using adjacency
lists. It maintains several additional data
structures with each vertex in G. The color of
each vertex u ∈ V is stored in the variable
Color [ u ] and the predecessor of u is stored in
the variable π [ u ].
14
Data Structures used in BFS
If u has no predecessor ( for example,
if u = s or u has not discovered ), then
π [ u ] = NIL. The distance from source s to
vertex u computed by the algorithm is stored in
d [ u ]. The algorithm also uses a first-in, first-out
queue Q to manage the set of green vertices.
15
BFS(G,s)
{ for each vertex u ∈ V[G]-{s}
do color[u]WHITE
∞
d[u]∞
π[u]NIL
Time Complexity:
color[s]GREEN O(|E|+|V|)
d[s]0
π[s]NIL
Enqueue(Q,s)
while Q≠≠empty
do uhead[Q]
for each v ∈ Adj[u]
do if color[v] = WHITE
then color[v]GREEN
d[v]d[u]+1
π[v]u
Enqueue(Q,v)
color[u]RED
Dequeue(Q)
} 16
Steps of BFS Algorithm
r s t u
∞ 0 ∞ ∞ Q
(a) s
∞ ∞ ∞ ∞ 0
v w x y
r s t u
1 0 ∞ ∞ Q
(b) w r
∞ 1 ∞ ∞ 1 1
v w x y
r s t u
1 0 2 ∞ Q
(c) r t x
∞ 1 2 ∞ 1 2 2
v w x y
17
Steps of BFS Algorithm
r s t u
1 0 2 ∞ Q
(d) t x v
2 1 2 ∞ 2 2 2
v w x y
r s t u
1 0 2 3 Q
(e) x v u
2 1 2 ∞ 2 2 3
v w x y
r s t u
1 0 2 3 Q
(f) v u y
2 1 2 3 2 3 3
v w x y
18
Steps of BFS Algorithm
r s t u
1 0 2 3 Q
(g) u y
2 1 2 3 3 3
v w x y
r s t u
1 0 2 3 Q
(h) y
2 1 2 3 3
v w x y
r s t u
1 0 2 3 Q
(i) empty
2 1 2 3
v w x y
19
Breath First Tree
r s t u
1 0 2 3
2 1 2 3
v w x y
Breadth-first tree
20
Print Path
Print-Path(G,s,v)
{ if v=s
then print s
else if π[v]=NIL
then print “no path from” s “to” v
else Print-Path ( G, s, π[v] )
print v
}
21
Depth-First Search
The strategy followed by depth-first search (DFS)
is, as its name implies, to search “deeper” in the
graph whenever possible.
In DFS, edges are explored out of the most
recently discovered vertex v that still has
unexplored edges leaving it.
22
DFS
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.
23
DFS
If any undiscovered vertex remain, then any one
of them is selected as a new source and the
search is repeated from that source.
24
DFS
As in breadth-first search, whenever a vertex v is
discovered during a scan of adjacency list of an
already discovered vertex u, depth-first search
records this event by setting v’s predecessor
field π [ v ] to u.
25
DFS
Unlike BFS, whose predecessor sub-graph form
a tree, the predecessor sub-graph produced by a
depth-first search may be composed of several
trees, because the search may be repeated from
multiple sources.
26
DFS
The predecessor sub-graph of a DFS is
therefore defined slightly differently from that of a
BFS: we let G π = ( V, E π), where
E π = { ( π [ v ], v ): v ε V and π [ v ] ≠ NIL }.
The predecessor sub-graph of a DFS form depth-
first forest composed of several depth-first trees.
The edged in Eπ are called tree edges.
27
DFS
As in breadth-first search, vertices are colored
during the search to indicate their state. Each
vertex is initially white, is grayed when it is
discovered in the search, and blackened when
it is finished, that is, when its adjacency list
has been examined completely. This technique
guarantees that each vertex ends up in exactly
one depth-first tree, so that these trees are
disjoint.
28
DFS
Besides creating a depth-first forest, DFS 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 ( blacken v ). These
timestamps are used in many graph algorithms and are
generally helpful in reasoning about the behavior of
DFS.
29
DFS
The procedure DFS below records when it discovers
vertex u in the variable d [ u ] and when it finishes
vertex u in the variable f [ u ]. These timestamps are
integers between 1 and 2 I V I, since there is one
discovery event and one finishing event for each of the
I V I vertices. For every vertex u,
d [ u ] < f [ u ].
Vertex u is WHITE before time d [ u ], GRAY between
d [ u ] and time f [ u ] and BLACK thereafter.
30
DFS Algorithm
DFS(G)
{ for each vertex u ∈ V [ G ]
do color[u] WHITE
π [u ] NIL
time 0
for each vertex u ∈ V [ G ]
do if color[u]= WHITE
then DFS-Visit( u )
}
31
DFS-Visit
DFS-Visit( u )
{ color[ u ] GRAY //u has just been
discovered
d[ u ] time time + 1
for each v ∈ Adj [ u ]
do if color[v]= WHITE
then π [ v ] u
DFS-Visit( v )
color [ u ] BLACK
//DFS-Visit( u ) is done
f [ u ] time time + 1
}
32
Steps of DFS algorithm
Start
(a) u v w (b) u v w
1/ 1/ 2/
x y z x y z
(c) u v w (d) u v w
1/ 2/ 1/ 2/
3/ 4/ 3/
x y z x y z
33
Steps of DFS algorithm
(e) u v w (f) u v w
1/ 2/ 1/ 2/
B B
4/ 3/ 4/5 3/
x y z x y z
(g) u v w (h) u v w
1/ 2/ 1/ 2/7
B B
4/5 3/6 4/5 3/6
x y z x y z
34
Steps of DFS algorithm
(i) u v w (j) u v w
1/ 2/7 1/8 2/7
F B B
F
4/5 3/6 4/5 3/6
x y z x y z
(k) u v w
(l) u v w
1/8 2/7 9/ 1/8 2/7 9/
F B
F B C
4/5 3/6 4/5 3/6
x y z
x y z
35
Steps of DFS algorithm
(m) u v w (n) u v w
1/8 2/7 9/ 1/8 2/7 9/
F B C B C
F
B
4/5 3/6 10/ 4/5 3/6 10/
x y z x y z
(o) u v w (o) u v w
1/8 2/7 9/ 1/8 2/7 9/12
F B C F B C B
B
4/5 3/6 10/11 4/5 3/6 10/11
x y z x y z
36
Different Edges
• Tree edges are edges in the depth first forest Gπ.
Edge ( u, v ) is a tree edge if v was first discovered
by exploring edge ( u, v ).
• Back edges are those edge ( u, v ) connecting a
vertex u to an ancestor v in DFS. Self-loops are
considered to be back edges.
37
Different Edges
• Forward edges are those non-tree edges ( u, v )
connecting a vertex u to a descendant v in a DFS.
• Cross edges are all other edges. They can go
between vertices in the same DFS, as long as one
vertex is not an ancestor of the other, or they can go
between vertices in different depth-first-trees.
38
(a) y z s t
3/6 2/9 1/10 11/16
B F C B
4/5 7/8 12/13 C 14/15
C C u
x w v
(b)
s t
z v u
y w
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
( s (z (y (x x) y) (w w) z) s) (t (v v) (u u) t)
39
(c)
s
C t
F B
z C u
v
B C
y
w
C
40
Topological Sort
DAG ( Directed Acyclic Graph)
A topological sort of a DAG G = ( V, E ) is a linear
ordering of all vertices such that if G contains an
edge ( u, v ), then u appears before v in the ordering.
A topological sort of a graph can be viewed as an
ordering of its vertices along a horizontal line so that
all directed edges go from left to right. Topological
sorting is thus different from the usual kind of
“sorting” based on comparison. 41
Algorithm of Topological Sort
Topological-Sort ( G )
• call DFS ( G ) to compute finishing time f [ v ]
for each vertex v
• as each vertex is finished, insert it onto the
front of a linked list
• return the linked list of vertices
42
An Example
undershorts 11/16 socks 17/18
watch 9/10
12/15
pants shoes 13/14
1/8
shirt
belt tie 2/5
The discovery time and finishing
6/7
jacket times from DFS are shown next
3/4
to each vertex.
socks undershorts pants shoes watch shirt belt tie jacket
17/18 11/16 12/15 13/14 9/10 1/8 6/7 2/5 3/4
The same graph shown topological sorted. 43
Strongly Connected Components
1. call DFS ( G ) to compute finishing times f [ u ]
for each vertex u
2. compute GT
3. call DFS(GT), but in the main loop of DFS,
consider the vertices in order of decreasing f
[u ] ( as computed in line 1 )
4. output the vertices of each tree in the depth-
first forest of step 3 as a separate strongly
connected component
44
a b c d
13/14 11/16 1/10 8/9
G:
12/15 3/4 2/7 5/6
cd
e f g h
abe h
a b c d
13/14 11/16 1/10 8/9
fg
GT:
12/15 3/4 2/7 5/6
e f g h
45
