CS 332: Algorithms

Graph Algorithms
 Depth-First Search
● Depth-first search is another strategy for
exploring a graph
■ Explore “deeper” in the graph whenever possible
■ Edges are explored out of the most recently
discovered vertex v that still has unexplored edges
■ When all of v’s edges have been explored,
backtrack to the vertex from which v was
discovered
 Depth-First Search
● Vertices initially colored white
● Then colored gray when discovered
● Then black when finished
 Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
u->color = GREY;
for each vertex u  G->V
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
 Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
u->color = GREY;
for each vertex u  G->V
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}

What does u->d represent?

 Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
u->color = GREY;
for each vertex u  G->V
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}

What does u->f represent?

 Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
u->color = GREY;
for each vertex u  G->V
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}

Will all vertices eventually be colored black?

 Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
u->color = GREY;
for each vertex u  G->V
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}

What will be the running time?

 Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
u->color = GREY;
for each vertex u  G->V
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
There is actually a tighter bound.
How many times will DFS_Visit() actually be called?
 Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
u->color = GREY;
for each vertex u  G->V
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}

So, running time of DFS = O(V+E)

 Depth-First Sort Analysis
● This running time argument is an informal
example of amortized analysis
■ “Charge” the exploration of edge to the edge:
○ Each loop in DFS_Visit can be attributed to an edge in the
graph
○ Runs once/edge if directed graph, twice if undirected
○ Thus loop will run in O(E) time, algorithm O(V+E)
 Considered linear for graph, b/c adj list requires O(V+E) storage
■ Important to be comfortable with this kind of
reasoning and analysis
 DFS Example
source
vertex
 DFS Example
source
vertex
d f
1 | | |

| |

| | |
 DFS Example
source
vertex
d f
1 | | |

2 | |

| | |
 DFS Example
source
vertex
d f
1 | | |

2 | |

3 | | |
 DFS Example
source
vertex
d f
1 | | |

2 | |

3 | 4 | |
 DFS Example
source
vertex
d f
1 | | |

2 | |

3 | 4 5 | |
 DFS Example
source
vertex
d f
1 | | |

2 | |

3 | 4 5 | 6 |
 DFS Example
source
vertex
d f
1 | 8 | |

2 | 7 |

3 | 4 5 | 6 |
 DFS Example
source
vertex
d f
1 | 8 | |

2 | 7 |

3 | 4 5 | 6 |
 DFS Example
source
vertex
d f
1 | 8 | |

2 | 7 9 |

3 | 4 5 | 6 |

What is the structure of the grey vertices?

What do they represent?
 DFS Example
source
vertex
d f
1 | 8 | |

2 | 7 9 |10

3 | 4 5 | 6 |
 DFS Example
source
vertex
d f
1 | 8 |11 |

2 | 7 9 |10

3 | 4 5 | 6 |
 DFS Example
source
vertex
d f
1 |12 8 |11 |

2 | 7 9 |10

3 | 4 5 | 6 |
 DFS Example
source
vertex
d f
1 |12 8 |11 13|

2 | 7 9 |10

3 | 4 5 | 6 |
 DFS Example
source
vertex
d f
1 |12 8 |11 13|

2 | 7 9 |10

3 | 4 5 | 6 14|
 DFS Example
source
vertex
d f
1 |12 8 |11 13|

2 | 7 9 |10

3 | 4 5 | 6 14|15
 DFS Example
source
vertex
d f
1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15
 DFS: Kinds of edges
● DFS introduces an important distinction
among edges in the original graph:
■ Tree edge: encounter new (white) vertex
○ The tree edges form a spanning forest
○ Can tree edges form cycles? Why or why not?
 DFS Example
source
vertex
d f
1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges
 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
○ Encounter a grey vertex (grey to grey)
 DFS Example
source
vertex
d f
1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges Back edges

 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
○ Not a tree edge, though
○ From grey node to black node
 DFS Example
source
vertex
d f
1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges Back edges Forward edges

 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
■ Cross edge: between a tree or subtrees
○ From a grey node to a black node
 DFS Example
source
vertex
d f
1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges Back edges Forward edges Cross edges

 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
■ Cross edge: between a tree or subtrees
● Note: tree & back edges are important; most
algorithms don’t distinguish forward & cross
 DFS: Kinds Of Edges
● Thm 23.9: If G is undirected, a DFS produces
only tree and back edges
● Proof by contradiction:
source
■ Assume there’s a forward edge F?
○ But F? edge must actually be a
back edge (why?)
 DFS: Kinds Of Edges
● Thm 23.9: If G is undirected, a DFS produces only
tree and back edges
● Proof by contradiction:
source
■ Assume there’s a cross edge
○ But C? edge cannot be cross:
○ must be explored from one of the
vertices it connects, becoming a tree
vertex, before other vertex is explored
○ So in fact the picture is wrong…both
lower tree edges cannot in fact be
tree edges
C?
 DFS And Graph Cycles
● Thm: An undirected graph is acyclic iff a DFS
yields no back edges
■ If acyclic, no back edges (because a back edge implies a
cycle
■ If no back edges, acyclic
○ No back edges implies only tree edges
○ Only tree edges implies we have a tree or a forest
○ Which by definition is acyclic

● Thus, can run DFS to find whether a graph has a

cycle
 DFS And Cycles
● How would you modify the code to detect cycles?
DFS(G) DFS_Visit(u)
{ {
u->color = GREY;
for each vertex u  G->V
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
 DFS And Cycles
● What will be the running time?
DFS(G) DFS_Visit(u)
{ {
u->color = GREY;
for each vertex u  G->V
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
 DFS And Cycles
● What will be the running time?
● A: O(V+E)
● We can actually determine if cycles exist in
O(V) time:
■ In an undirected acyclic forest, |E|  |V| - 1
■ So count the edges: if ever see |V| distinct edges,
must have seen a back edge along the way