CS 316: ALGORITHMS

Lecture 7: Graph Representation

and Search
Prepared by: Assoc. Prof. Ensaf Hussein
Presented by:
Dr. Mohammed El-Said
Dr. Mai Hamdalla
LINEAR DATA STRUCTURES

Array Linked List

Stack Queue
NON-LINEAR DATA STRUCTURES

Tree Graph
 GRAPH – DEFINITIONS

Graph – mathematical object consisting of a

set of: G = (V, E)
 Denoted by
 V = nodes (vertices, points).
 E = edges (links, arcs) between pairs of nodes,
where each edge is a pair (v,w) s.t. v,w  V

4
APPLICATIONS
Applications that involve not only a set of items, but
also the connections between them

Maps Schedules Computer networks

Hypertext Circuits
DEFINITIONS
GRAPHS - DEFINITIONS
If the edge pair is ordered then the graph is called a directed
graph (also called digraphs) .
Undirected graph, which is not a directed graph, also called a
normal graph or just a graph.

Undirected Directed
graph graph

Directed edge

V = { A,B,C,D }
E = {(A,B), (B,A), (A,D), V = { 1, 3,5,7,9,11}
(D,A) (B,D), (D,B), (B,C), E = {(1,3) (3,1) (11,1) (9,11) (9,9) (5,9)
 GRAPH – DEFINITIONS
Two vertices of a graph are adjacent if they are joined by an edge.

Vertex w is adjacent to v if edge (v,w)  E.

Undirected Directed
graph graph
- An edge is enough - if there is a direct edge from v
to w
w is successor of v
v is predecessor of w
Ex:
With Edge (B,D) Ex:
. B is adjacent to D • 3 is adjacent to 1 
. D is adjacent to B. (1,3)
With Edge (B,C) • 1 is adjacent to 3 
. B is adjacent to C (3,1)
. C is adjacent to B. • 8
 GRAPH – DEFINITIONS

A (directed) path between two vertices is a sequence of edges that

begins at one vertex and ends at another vertex.
w1, w2, …, wN is a path if (wi, wi+1)  E for 1  i .
N-1path passes through a vertex only once.
A simple
Example:

1 2
A graph G (undirected)

3 4 5

The graph G= (V,E) has 5 vertices and 12 edges:

V = {1,2,3,4,5}
E = { (1,2),(1,3),(1,4),(2,5),(3,4),(4,5), (2,1),(3,1),(4,1),(5,2),(4,3)
(5,4) }
Path: 9
 GRAPH – DEFINITIONS

A cycle is a path that begins and ends at the same vertex.

• For undirected graphs, the edges must be distinct No Self
loops
• In a directed graph is a path of length at least 1 such
that w1 = wN.  Self loops
• A directed acyclic graph (DAG) is a type of directed
graph having no cycles.
A simple cycle is a cycle that does not pass through other vertices
more than once.

10
 GRAPH – AN EXAMPLE
1 2
A graph G (undirected)

3 4 5

The graph G= (V,E) has 5 vertices and 12 edges:

V = {1,2,3,4,5}
E = { (1,2),(1,3),(1,4),(2,5),(3,4),(4,5), (2,1),(3,1),(4,1),(5,2),(4,3),
(5,4) }

• Adjacent:
1 and 2 are adjacent -- 1 is adjacent to 2 and 2 is adjacent to 1

• Cycle:
2,5,4,1,2 (a simple cycle), 1,3,4,1,4,1 (a cycle, but not simple
cycle)
DIRECTED GRAPH – AN EXAMPLE
1 2

3 4 5

The graph G= (V,E) has 5 vertices and 7 edges:

V = {1,2,3,4,5}
E = { (1,2),(1,4),(2,5),(4,5),(3,1),(4,3),(5,5) }

• Adjacent:
2 is adjacent to 1, but 1 is NOT adjacent to 2
• Path:
1,2,5 ( a directed path),
• Cycle:
1,4,3,1 (a directed cycle), 5,5 (a Self loop)
 GRAPH -- DEFINITIONS
 A connected graph has a path between each pair of distinct vertices
 A complete graph has an edge between each pair of distinct vertices
• A complete graph is also a connected graph. But a connected
graph may not be a complete graph.

connected disconnected complete

13
 GRAPH – DEFINITIONS
In graph, degree is the number of edges incident on a
node
In digraph, Degree = in-degree + out-degree
•In-degree: Number of edges entering
•Out-degree: Number of edges leaving
outdeg(1)=2
indeg(1)=0

outdeg(2)=2
deg(1) = 2
indeg(2)=2
deg(2) = 3
deg(5) = 3
outdeg(3)=1
indeg(3)=4
 WEIGHTED GRAPH
We can label the edges of a graph with numeric values, the
graph is called a weighted graph.

8
1 2 Weighted (Undirected) Graph
10 3 6

5 7
3 4 5

8
1 2 Weighted Directed Graph
10 3 6

5 7
3 4 5

15
 TYPES OF GRAPHS
• Undirected: edge (u, v) = (v, u); for all v, (v, v)  E (No self
loops.)
• Directed: (u, v) is edge from u to v, denoted as u  v. Self
loops are allowed.
• Weighted: each edge has an associated weight, given by a
weight function w : E  R.
• Dense: |E|  |V|2.
• Sparse: |E| << |V|2.
Adjacency relationship is:
• Symmetric if G is undirected.
• Not necessarily symmetric if G is directed.
If G is connected:
• There is a path between every pair of vertices.
• |E|  |V| – 1.
• Furthermore, if |E| = |V| – 1, then G is a tree.
GRAPH REPRESENTATIONS
HOW TO REPRESENT A GRAPH, IN MEMORY?
 REPRESENTATION OF GRAPHS
Two standard ways.
• Adjacency Lists. a b a b d c

b a c

c d c d a b

d a c

• Adjacency Matrix.

1 2 1 2 3 4
a b
1 0 1 1 1
2 1 0 1 0
c d 3 1 1 0 1
3 4 4 1 0 1 0
 ADJACENCY LISTS
Consists of an array Adj of |V| lists. One list per
vertex.
For u  V, Adj[u] consists of all vertices adjacent to u.
Adj
a b a b d c

b c
If weighted, store weights also in
c d c d adjacency lists.
d

a b a b d c

b a c

c d c d a b

d a c
 STORAGE REQUIREMENT
For directed graphs:
• Sum of lengths of all adj. lists is
out-degree(v) = |E|
vV
No. of edges leaving v
• Total storage: (V+E)
For undirected graphs:
• Sum of lengths of all adj. lists is
degree(v) = 2|E|
vV
No. of edges incident on v. Edge (u,v)
is incident on vertices u and v.
• Total storage: (V+E)
PROS AND CONS: ADJ LIST

Pros
• Space-efficient, when a graph is sparse.
• Can be modified to support many graph
variants.
Cons
• Determining if an edge (u,v) G is not
efficient.
• Have to search in u’s adjacency
a b list.
d c
(degree(u)) time. a c
b
• (V) in the worst case. d a b
c
d a c
 ADJACENCY MATRIX
|V|  |V| matrix A.
Number vertices from 1 to |V| in some arbitrary
manner.
A is then given by: 1 if (i, j )  E
A[i, j ] aij 
1
0 otherwise
2 1 2 3 4
a b
1 0 1 1 1
2 0 0 1 0
c d4 3 0 0 0 1
3 4 0 0 0 0
1 2 1 2 3 4
a b
1 0 1 1 1
A = AT for undirected graphs.
2 1 0 1 0
c d 3 1 1 0 1
3 4 4 1 0 1 0
For weighted graph:
Weights are stored instead of 1
SPACE AND TIME

Space: (V2).
• Not memory efficient for large graphs.
Time: to list all vertices adjacent to u: (V).
Time: to determine if (u, v)  E: (1).

1 2 3 4
1 0 1 1 1
2 0 0 1 0
3 0 0 0 1
4 0 0 0 0
SEARCHING A GRAPH
GRAPH-SEARCHING ALGORITHMS

Searching a graph:
• Systematically follow the edges of a graph
to visit the vertices of the graph.
Used to discover the structure of a graph.
Standard graph-searching algorithms.
• Breadth-first Search (BFS).
• Depth-first Search (DFS).
GRAPH-SEARCHING ALGORITHMS
 BREADTH-FIRST SEARCH
Input: Graph G = (V, E), either directed or undirected,
and source vertex s  V.
Output:
• d [v] = distance (smallest # of edges, or shortest path)
from s to v, for all v  V. d [v] =  if v is not reachable from
s.
• [v] = u such that (u, v) is last edge on shortest path s
v.
• u is v’s predecessor.
• Builds breadth-first tree with root s that contains all
reachable vertices.
 BREADTH-FIRST SEARCH
Expands the frontier between discovered and
undiscovered vertices uniformly across the breadth of
the frontier.
• A vertex is “discovered” the first time it is
encountered during the search.
• A vertex is “finished” if all vertices adjacent to it
have been discovered.
Colors the vertices to keep track of progress.
• White – Undiscovered.
• Gray – Discovered but not finished.
• Black – Finished.
• Colors are required only to reason about the
algorithm. Can be implemented without colors.
BFS(G,s)
BFS(G,s)
1.
1. for
for each
each vertex
vertex uu inin V[G]
V[G] –– {s}
{s}
2.
2. dodo color[u]
color[u]   white
white
3.
3. d[u]
d[u]   white:
4.
4. [u][u]  nil
nil undiscovered
5.
5. color[s]
color[s]   gray
gray gray: discovered
black: finished
6.
6. d[s]
d[s]  00 Q: a queue of
7.
7. [s]  nil
[s]  nil
discovered
vertices
8.
8. Q Q   color[v]: color of
9.
9. enqueue(Q,s)
enqueue(Q,s) v
d[v]: distance
10.
10.while
while Q Q  from s to v
11.
11. dodo uu 
 dequeue(Q)
dequeue(Q) [u]: predecessor
12.
12. for
for each
each vv inin Adj[u]
Adj[u]
of v

13.
13. do
do if
if color[v]
color[v] == white
white
14.
14. then
then color[v]
color[v] 
gray
gray
15.
15. d[v]
d[v]  d[u]
d[u] +
+
11
16.
16. [v]  uu
[v] 
17.
17. enqueue(Q,v)
enqueue(Q,v)
BFS(G,s)
BFS(G,s)
1.
1. for
foreach
eachvertex
vertexuuin
inV[G]
V[G]–– {s}
{s} π:
2.
2. do
docolor[u]
color[u]white
white s
3.
3. d[u]
d[u]
4. nil
4. [u]nil
[u] nil
5.
5. color[s]
color[s]gray
gray r
6.
6. d[s]
d[s]00 nil
7. [s]nil
[s]
7.
8. QQ
nil
t nil
8.
9.
9. enqueue(Q,s)
enqueue(Q,s) u nil
v
r s t u nil
Example:
 0   w
Q: nil
s
d: x0
nil
   
y
v w x y
nil
BFS(G,s)
BFS(G,s)
1.
1. for
for each
each vertex
vertex uu inin V[G]
V[G] –– {s}
{s}
2.
2. dodo color[u]
color[u]   white
white
3.
3. d[u]
d[u]   white:
4.
4. [u][u]  nil
nil undiscovered
5.
5. color[s]
color[s]   gray
gray gray: discovered
black: finished
6.
6. d[s]
d[s]  00 Q: a queue of
7.
7. [s]  nil
[s]  nil
discovered
vertices
8.
8. Q Q   color[v]: color of
9.
9. enqueue(Q,s)
enqueue(Q,s) v
d[v]: distance
10.
10.while
while Q Q  from s to v
11.
11. dodo uu 
 dequeue(Q)
dequeue(Q) [u]: predecessor
12.
12. for
for each
each vv inin Adj[u]
Adj[u]
of v

13.
13. do
do if
if color[v]
color[v] == white
white
14.
14. then
then color[v]
color[v] 
gray
gray
15.
15. d[v]
d[v]  d[u]
d[u] +
+
11
16.
16. [v]  uu
[v] 
17.
17. enqueue(Q,v)
enqueue(Q,v)
BFS(G,s)
BFS(G,s)
10.
10. while
whileQQ π:
11.
11. do
douudequeue(Q)
dequeue(Q) s
12.
12. for
foreach
eachvvin
inAdj[u]
Adj[u]
13. do nil
13. doififcolor[v]
color[v]==white
white
14.
14. then
thencolor[v]
color[v]gray
gray r
15.
15. d[v]
d[v]d[u]
d[u]++11 nil
16. [v]uu
[v]
16.
17. enqueue(Q,v)
t nil
17. enqueue(Q,v)
18.
18. color[u]
color[u]black
black u nil
v
r s t u nil
Example:
 0   w
Q: nil
s
d: x0
nil
   
y
v w x y
nil
BFS(G,s)
BFS(G,s)
10.
10. while
whileQQ π:
11.
11. do
douudequeue(Q)
dequeue(Q) s nil
12.
12. for
foreach
eachvvin
inAdj[u]
Adj[u]
13. do
r
13. doififcolor[v]
color[v]==white
white
14.
14. then
thencolor[v]
color[v]gray
gray s
15.
15. d[v]
d[v]d[u]
d[u]++11 t
16. [v]uu
[v]
16.
17. enqueue(Q,v)
u
17. enqueue(Q,v)
18.
18. color[u]
color[u]black
black
v
w
r s t u s
Example:
1 0   x
Q: yw r
d: 1 1
 1  
v w x y
EXAMPLE (BFS)

π:
r s t u
s
1 0 2 
nil
r
s
 1 2  t
v w x y w
u
Q: r t x v
d: 1 2 2 w
s
EXAMPLE (BFS)

π:
r s t u
s
1 0 2 
nil
r
s
2 1 2  t
v w x y w
u
Q: t x v v r
d: 2 2 2 w
s
EXAMPLE (BFS)

π:
r s t u
s nil
1 0 2 3
r
s
t
2 1 2  w
v w x y u t
v r
Q: x v u w
d: 2 2 3 s
x
EXAMPLE (BFS)

π:
r s t u
s
1 0 2 3
nil
r
s
2 1 2 3 t
v w x y w
u t
Q: v u y v r
d: 2 3 3 w
s
EXAMPLE (BFS)

π:
r s t u
s
1 0 2 3
nil
r
s
2 1 2 3 t
v w x y w
u t
Q: EMPTY v r
w
s
BREADTH-FIRST TREE

π:
r s t u
s
1 0 2 3
nil
r
s
2 1 2 3 t
v w x y w
u t
v r
Breadth First Tree
w
s
BREADTH-FIRST TREE
For a graph G = (V, E) with source s, the
predecessor subgraph of G is G = (V , E) where
• V ={vV : [v]  NIL}{s}
• E ={([v],v)E : v  V - {s}}
The predecessor subgraph G is a breadth-first tree
if:
• V consists of the vertices reachable from s and
• for all vV , there is a unique simple path from s
to v in G that is also a shortest path from s to v in
G.
The edges in E are called tree edges.
|E | = |V | - 1.
BFS(G,s)
BFS(G,s) ANALYSIS OF BFS
1.
1. for
for each
each vertex
vertex uu inin V[G]
V[G] –– {s}
{s}
2.
2. dodo color[u]
color[u]   white
white
3.
3. d[u]
d[u]   O(V)
4.
4. [u]  nil
[u]  nil
5.
5. color[s]
color[s]   gray
gray
6.
6. d[s]
d[s]  00
7.
7. [s]
[s]  nil
nil
8.
8. Q Q  
9.
9. enqueue(Q,s)
enqueue(Q,s) Each vertex is enqueued and
10.
10.while
while Q Q   dequeued at most once.
11.
11. dodo uu  dequeue(Q)
dequeue(Q) So, total time for queuing is
12.
12. for
for each
each vv in Adj[u] O(V).
in Adj[u]
13.
13. do
do if
if color[v]
color[v] == white
whiteAdjacency list of
14.
14. then
then color[v] 
color[v]each
 vertex is
gray
gray scanned at most
15. d[v]  once.+ The sum of
d[u]
15. d[v]  d[u] + of all
lengths
11
adjacency lists is
16.
16. [v]  u
[v]  u(E).
17.
17. enqueue(Q,v)
enqueue(Q,v)
 ANALYSIS OF BFS

Total running time of BFS is O(V+E),

linear in the size of the adjacency list representation of
graph.
 DEPTH-FIRST SEARCH (DFS)
Explore edges out of the most recently discovered
vertex v.
When all edges of v have been explored, backtrack to
explore other edges leaving the vertex from which v
was discovered (its predecessor).
“Search as deep as possible first.”
Continue until all vertices reachable from the original
source are discovered.
If any undiscovered vertices remain, then one of
them is chosen as a new source and search is
repeated from that source.
 DEPTH-FIRST SEARCH
Input: G = (V, E), directed or undirected. No source
vertex given!
Output:
• 2 timestamps on each vertex. Integers between 1
and 2|V|.
• d [v] = discovery time (v turns from white to
gray)
• f [v] = finishing time (v turns from gray to
black)
• [v] : predecessor of v = u, such that v was
discovered during the scan of u’s adjacency list.
Uses the same coloring scheme for vertices as BFS.
 PSEUDO-CODE
DFS(G)
DFS(G) DFS-Visit(u)
DFS-Visit(u)
1.
1. for
foreach vertexuu
eachvertex 1.
1. color[u]
color[u]   GRAY
GRAY //// White
White
V[G] vertex
V[G] vertex uu has
has been
been
2.
2. do
docolor[u] white
color[u] white discovered
discovered
3.
3. [u]
[u]NIL
NIL 2.
2. time
time   time
time + + 11
4.
4. time
time 00 3.
3. d[u]d[u]  time
time
5.
5. for
foreach vertexuu
eachvertex 4.
4. for for each
each vv  Adj[u]
Adj[u]
V[G]
V[G] 5.
5. do
do ifif color[v]
color[v] = =
6.
6. do
doififcolor[u]
color[u]=
= WHITE
white
WHITE
ses a global
whitetimestamp time. 6.
6. then
then [v]  uu
[v] 
7.
7. then
thenDFS-
DFS-
Visit(u) 7.
7. DFS-
DFS-
Visit(u)
Visit(v)
Visit(v)
8.
8. color[u]
color[u]   BLACK
BLACK
//// Blacken
Blacken u;u; itit is
is finished.
finished.
 DFS-Visit(u)
DFS-Visit(u)
1.
1. color[u]
color[u] GRAY
GRAY
2.
2. time
time time
time+ +11
EXAMPLE (DFS) 3.
3. d[u]
d[u] time
time
4.
4. for
foreach
eachvvAdj[u]
Adj[u]
5.
5. do
doififcolor[v]
color[v]= =
WHITE
WHITE
6.
6. then
then[v] uu
[v]
7.
7. DFS-
DFS-
Visit(v)
Visit(v)
8.
8. color[u]
color[u] BLACK
BLACK
u v 9. w
9. f[u]
f[u]time
time π:time
time++11
1/ u
nil
v
w
x
U x y z y
z
 DFS-Visit(u)
DFS-Visit(u)
1.
1. color[u]
color[u] GRAY
GRAY
2.
2. time
time time
time+ +11
EXAMPLE (DFS) 3.
3. d[u]
d[u] time
time
4.
4. for
foreach
eachvvAdj[u]
Adj[u]
5.
5. do
doififcolor[v]
color[v]= =
WHITE
WHITE
6.
6. then
then[v] uu
[v]
7.
7. DFS-
DFS-
Visit(v)
Visit(v)
8.
8. color[u]
color[u] BLACK
BLACK
u v w π:time
9.
9. f[u]
f[u]time
time time++11
1/ 2/ u
nil
v
u
v w
x y z x
u y
 DFS-Visit(u)
DFS-Visit(u)
1.
1. color[u]
color[u] GRAY
GRAY
2.
2. time
time time
time+ +11
EXAMPLE (DFS) 3.
3. d[u]
d[u] time
time
4.
4. for
foreach
eachvvAdj[u]
Adj[u]
5.
5. do
doififcolor[v]
color[v]= =
WHITE
WHITE
6.
6. then
then[v] uu
[v]
7.
7. DFS-
DFS-
Visit(v)
Visit(v)
8.
8. color[u]
color[u] BLACK
BLACK
u v 9.
9. f[u]
f[u]
w time
time π:time
time++11
1/ 2/ u
nil
v
y u
v 3/ w
x y z x
u y
 DFS-Visit(u)
DFS-Visit(u)
1.
1. color[u]
color[u] GRAY
GRAY
2.
2. time
time time
time+ +11
EXAMPLE (DFS) 3.
3. d[u]
d[u] time
time
4.
4. for
foreach
eachvvAdj[u]
Adj[u]
5.
5. do
doififcolor[v]
color[v]= =
WHITE
WHITE
6.
6. then
then[v] uu
[v]
7.
7. DFS-
DFS-
Visit(v)
Visit(v)
8.
8. color[u]
color[u] BLACK
BLACK
u v 9.
9. f[u]
f[u]
w time
time π:time
time++11
1/ 2/
u
nil
X v
y u
v 4/ 3/ w
x
u x y z
y
 DFS-Visit(u)
DFS-Visit(u)
1.
1. color[u]
color[u] GRAY
GRAY
2.
2. time
time time
time+ +11
EXAMPLE (DFS) 3.
3. d[u]
d[u] time
time
4.
4. for
foreach
eachvvAdj[u]
Adj[u]
5.
5. do
doififcolor[v]
color[v]= =
WHITE
WHITE
6.
6. then
then[v] uu
[v]
7.
7. DFS-
DFS-
Visit(v)
Visit(v)
8.
8. color[u]
color[u] BLACK
BLACK
u v 9. w π:time
9. f[u]
f[u]time
time time++11
1/ 2/ u
X nil
B
v
y u
v 4/ 3/ w
u x y z x
y
 DFS-Visit(u)
DFS-Visit(u)
1.
1. color[u]
color[u] GRAY
GRAY
2.
2. time
time time
time+ +11
EXAMPLE (DFS) 3.
3. d[u]
d[u] time
time
4.
4. for
foreach
eachvvAdj[u]
Adj[u]
5.
5. do
doififcolor[v]
color[v]= =
WHITE
WHITE
6.
6. then
then[v] uu
[v]
Leaf node 7.
7. DFS-
DFS-
Visit(v)
Visit(v)
8.
8. color[u]
color[u] BLACK
BLACK
u v 9.
9. f[u]
f[u]
w time
time π:time
time++11
1/ 2/
u
nil
y B v
u
v w
4/5 3/
u x y z x
y
 DFS-Visit(u)
DFS-Visit(u)
1.
1. color[u]
color[u] GRAY
GRAY
2.
2. time
time time
time+ +11
EXAMPLE (DFS) 3.
3. d[u]
d[u] time
time
4.
4. for
foreach
eachvvAdj[u]
Adj[u]
5.
5. do
doififcolor[v]
color[v]= =
WHITE
WHITE
6.
6. then
then[v] uu
[v]
7.
7. DFS-
DFS-
Visit(v)
Visit(v)
8.
8. color[u]
color[u] BLACK
BLACK
u v 9. w π:time
9. f[u]
f[u]time
time time++11
1/ 2/ u
nil
B
v
v u
4/5 3/6 w
u x y z x
y
EXAMPLE (DFS)
u v w π:
1/ 2/7 u
B
nil
v
4/5 3/6
u
u x y z w
x
y
y
v
z
EXAMPLE (DFS)
u v w π:
1/ 2/7 u
B
nil
F
v
4/5 3/6
u
u x y z w
x
y
y
v
z
DFS(G)
DFS(G) DFS-Visit(u)
DFS-Visit(u)
1.
1. color[u]
color[u] GRAY
1.
1. for
foreach vertexuu
eachvertex GRAY
V[G]
V[G] 2.
2. time
time time
time+ +11
2.
2.
EXAMPLE
do
docolor[u]
(DFS)
white
color[u] white
3.
3. d[u]
d[u] time
time
4.
4. for
foreach
eachvvAdj[u]
Adj[u]
3.
3. [u]
[u]NIL
NIL 5.
5. do
doififcolor[v]
color[v]= =
4.
4. time
time 00 WHITE
WHITE
5.
5. for
foreach vertexuu
eachvertex 6.
6. then
then[v] uu
[v]
V[G]
V[G] 7.
7. DFS-
DFS-
6. do Visit(v)
Visit(v)
6. doififcolor[u]
color[u]=
=
white
white 8.
8. color[u]
color[u] BLACK
BLACK
u v 9. w π:time
7.
7. then DFS-
then DFS- 9. f[u]
f[u]time
time time++11
Visit(u)
Visit(u) 1/8 2/7 u
nil
B
F v
u
4/5 3/6 w
x y z x
y
EXAMPLE (DFS)
u v w π:
1/8 2/7 9/ u
B
nil
F
v
4/5 3/6
u
w x y z w
nil
x
y
y
v
EXAMPLE (DFS)
u v w π:
1/8 2/7 9/ u
B C
nil
F
v
4/5 3/6
u
w x y z w
nil
x
y
y
v
EXAMPLE (DFS)
u v w π:
1/8 2/7 9/ u
B C
nil
F
v
z u
4/5 3/6 10/
w x y z w
nil
x
y
y
v
EXAMPLE (DFS)
u v w π:
1/8 2/7 9/ u
B C
nil
F
v
z u
4/5 3/6 10/ B
w x y z w
nil
x
y
y
v
EXAMPLE (DFS)
u v w π:
1/8 2/7 9/ u
B C
nil
F
v
4/5 3/6 10/11 B
u
w x y z w
nil
x
y
y
v
EXAMPLE (DFS)
u v w π:
1/8 2/7 9/12 u
B C
nil
F
v
4/5 3/6 10/11 B
u
x y z w
nil
x
y
y
v
DEPTH FIRST FOREST

u v w π:
u
nil
v
u
w
x y z
nil
x
y
y
v
 ANALYSIS OF DFS
DFS(G)
DFS(G) DFS-Visit(u)
DFS-Visit(u)
1.
1. for
foreach vertexuu (V) 1.
eachvertex 1. color[u]
color[u]  GRAY
GRAY  White
White
V[G] vertex
V[G] vertex uu has
has been
been
2.
2. do
docolor[u] white
color[u] white discovered
discovered
3.
3. [u]
[u]NIL
NIL 2.
2. time
time  time
time + + 11
4.
4. time
time 00 (V)
3.
3. d[u]  time
d[u]  time
5.
5. for
foreach vertexuu
eachvertex 4.
4. for
for each
each vv  Adj[u]
Adj[u] (E)
V[G]
V[G] 5.
5. do
do ifif color[v]
color[v] = =
6.
6. do
doififcolor[u]
color[u]=
= WHITE
white
WHITE
white 6. then
6. then [v]  uu
[v] 
7.
7. then
thenDFS-
DFS-
Visit(u) 7.
7. DFS-
DFS-
Visit(u)
Visit(v)
Visit(v)
8.
8. color[u]
color[u]   BLACK
BLACK  
Blacken
Blacken u; u; itit is
is finished.
finished.
ANALYSIS OF DFS

Loops on lines 1-3 & 5-7 take (V) time,

excluding time to execute DFS-Visit.

DFS-Visit is called once for each white vertex

vV when it’s painted gray the first time.
Lines 4-7 of DFS-Visit is executed |Adj[v]|
times. The total cost of executing DFS-Visit is
vV|Adj[v]| = (E)

Total running time of DFS is (V+E).

DFS: KINDS OF EDGES

DFS introduces an important distinction among

edges in the original graph:
• Tree edge: encounter new (white) vertex
• Back edge: from descendent to ancestor
• Forward edge: from ancestor to descendent, but
not a tree edge.
• Cross edge: between a tree or subtrees
Note: tree & back edges are important; most
algorithms don’t distinguish forward & cross
Theorem:
Theorem:
In
InDFS
DFSof
ofan
anundirected
undirectedgraph,
graph,we
weget
getonly
onlytree
treeand
andback
backedges.
edges.No
No
forward
forwardor
orcross
crossedges.
edges.
REFERENCES

Introduction to Algorithms, Second Edition by

Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest and Clifford Stein, The MIT Press © 2001
Chapter 22.1, 22.2, 22.3