CS 332: Algorithms
Graph Algorithms
https://www.cs.virginia.edu/~luebke/cs332.f
all00/lecture18.ppt
David Luebke 1 10/14/18
Review: Graphs
● A graph G = (V, E)
■ V = set of vertices, E = set of edges
■ Dense graph: |E| |V|2; Sparse graph: |E| |V|
■ Undirected graph:
○ Edge (u,v) = edge (v,u)
○ No self-loops
■ Directed graph:
○ Edge (u,v) goes from vertex u to vertex v, notated uv
■ A weighted graph associates weights with either the edges
or the vertices
David Luebke 2 10/14/18
Review: Representing Graphs
● Assume V = {1, 2, …, n}
● An adjacency matrix represents the graph as a n x n
matrix A:
■ A[i, j] = 1 if edge (i, j) E (or weight of edge)
= 0 if edge (i, j) E
■ Storage requirements: O(V2)
○ A dense representation
■ But, can be very efficient for small graphs
○ Especially if store just one bit/edge
○ Undirected graph: only need one diagonal of matrix
David Luebke 3 10/14/18
Universal Sink
● Show how to determine whether a directed
graph G contains a universal sink - a vertex
with in-degree (V-1) (V is the number of
vertices) and out-degree 0, given an adjacency
matrix for G. Can be done in O(V)
David Luebke 4 10/14/18
Review: Breadth-First Search
● “Explore” a graph, turning it into a tree
■ One vertex at a time
■ Expand frontier of explored vertices across the
breadth of the frontier
● Builds a tree over the graph
■ Pick a source vertex to be the root
■ Find (“discover”) its children, then their children,
etc.
David Luebke 5 10/14/18
Review: Breadth-First Search
● Again will associate vertex “colors” to guide the
algorithm
■ White vertices have not been discovered
○ All vertices start out white
■ Grey vertices are discovered but not fully explored
○ They may be adjacent to white vertices
■ Black vertices are discovered and fully explored
○ They are adjacent only to black and gray vertices
● Explore vertices by scanning adjacency list of grey
vertices
David Luebke 6 10/14/18
Review: Breadth-First Search
BFS(G, s) {
initialize vertices;
Q = {s}; // Q is a queue (duh); initialize to s
while (Q not empty) {
u = RemoveTop(Q);
for each v u->adj {
if (v->color == WHITE)
v->color = GREY;
v->d = u->d + 1;
v->p = u;
v->d represents level of v
Enqueue(Q, v);
} v->p represents the parent of v
u->color = BLACK;
}
}
David Luebke 7 10/14/18
Breadth-First Search: Example
r s t u
v w x y
David Luebke 8 10/14/18
Breadth-First Search: Example
r s t u
0
v w x y
Q: s
David Luebke 9 10/14/18
Breadth-First Search: Example
r s t u
1 0
1
v w x y
Q: w r
David Luebke 10 10/14/18
Breadth-First Search: Example
r s t u
1 0 2
1 2
v w x y
Q: r t x
David Luebke 11 10/14/18
Breadth-First Search: Example
r s t u
1 0 2
2 1 2
v w x y
Q: t x v
David Luebke 12 10/14/18
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2
v w x y
Q: x v u
David Luebke 13 10/14/18
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: v u y
David Luebke 14 10/14/18
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: u y
David Luebke 15 10/14/18
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: y
David Luebke 16 10/14/18
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: Ø
David Luebke 17 10/14/18
BFS: The Code Again
BFS(G, s) {
initialize vertices; Touch every vertex: O(V)
Q = {s};
while (Q not empty) {
u = RemoveTop(Q);
for each v u->adj { u = every vertex, but only once
if (v->color == WHITE) (Why?)
v->color = GREY;
So v = every vertexv->d = u->d + 1;
that appears in v->p = u;
Enqueue(Q, v);
some other} vert’s
adjacencyu->color
list = BLACK;
}
} What will be the running time?
Total running time: O(V+E)
David Luebke 18 10/14/18
Breadth-First Search: Properties
● BFS calculates the shortest-path distance to
the source node
● Since BFS gives a path from root to node,
d[v]>=sd[v] (cant be shorter than shortest
path)
● To prove that d[v]!> sd[v]
David Luebke 19 10/14/18
Proof sketch
● Let v be node closest to s that has d[v]!=sd[v].
● Let u be vertex just before v on shortest path from s to v which
means d[u]=sd[u] but d[v]>d[u]+1
● Lets look at what could have happened during the bfs when u
was being explored. Note u is grey.
-either v was white or black or grey. All show contradiction
If v was white: then d[v]=d[u]+1
If v was black: then v was enqueued before u so d[v] <=d[u]
If v was grey: so v was discovered through say w. Hence d[w]
was enqueued before u and hence d[w]<=d[u]. Hence, d[w]
+1<=d[u]+1. Hence d[v]=d[w]+1<=d[u]+1.
David Luebke 20 10/14/18
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
David Luebke 21 10/14/18
Depth-First Search
● Vertices initially colored white
● Then colored gray when discovered
● Then black when finished
David Luebke 22 10/14/18
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;
} }
David Luebke 23 10/14/18
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?
David Luebke 24 10/14/18
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;
} }
u->f represents finishing time of u
David Luebke 25 10/14/18
DFS Example
source
vertex
David Luebke 26 10/14/18
DFS Example
source
vertex
d f
1 | | |
| |
| | |
David Luebke 27 10/14/18
DFS Example
source
vertex
d f
1 | | |
2 | |
| | |
David Luebke 28 10/14/18
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | | |
David Luebke 29 10/14/18
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | 4 | |
David Luebke 30 10/14/18
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | 4 5 | |
David Luebke 31 10/14/18
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | 4 5 | 6 |
David Luebke 32 10/14/18
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 |
3 | 4 5 | 6 |
David Luebke 33 10/14/18
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 |
3 | 4 5 | 6 |
David Luebke 34 10/14/18
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?
David Luebke 35 10/14/18
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 9 |10
3 | 4 5 | 6 |
David Luebke 36 10/14/18
DFS Example
source
vertex
d f
1 | 8 |11 |
2 | 7 9 |10
3 | 4 5 | 6 |
David Luebke 37 10/14/18
DFS Example
source
vertex
d f
1 |12 8 |11 |
2 | 7 9 |10
3 | 4 5 | 6 |
David Luebke 38 10/14/18
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 |
David Luebke 39 10/14/18
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 14|
David Luebke 40 10/14/18
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 14|15
David Luebke 41 10/14/18
DFS Example
source
vertex
d f
1 |12 8 |11 13|16
2 | 7 9 |10
3 | 4 5 | 6 14|15
David Luebke 42 10/14/18
Paranthesis theorem
For any two vertices u and v in the graph only one of the
below hold true
D[u] < f[u] <d[v] < f[v]
D[v] < f[v] <d[u] < f[u]
D[u] < d[v] <f[v] < f[u]
D[v] < d[u] <f[u] < f[v]
● Corollary: Vertex v is a proper descendant of vertex u in the
depth-first forest for a (directed or undirected) graph G iff d[u]
< d[v] <f[v] < f[u]
David Luebke 43 10/14/18
