CSCI 2720:
Data Structures
Review 4
Tianming Liu
Department of Computer Science & Bioimaging Research Center
The University of Georgia
Definition : graph
A graph G=(V,E) is
a finite nonempty set V of objects called vertices (the
singular is vertex)
together with a (possibly empty) set E of unordered pairs of
distinct vertices of G called edges.
Some authors call a graph by the longer term ``undirected graph'' and simply
use the following definition of a directed graph as a graph. However when using
Definition 1 of a graph, it is standard practice to abbreviate the phrase ``directed
graph'' (as done below in Definition 2) with the word digraph.
Definition: digraph
A digraph G=(V,E) is
a finite nonempty set V of vertices
together with a (possibly empty) set E of ordered pairs of
vertices of G called arcs.
An arc that begins and ends at a same vertex u is called a loop. We
usually (but not always) disallow loops in our digraphs.
By being defined as a set, E does not contain duplicate (or multiple)
edges/arcs between the same two vertices.
For a given graph (or digraph) G we also denote the set of vertices by
V(G) and the set of edges (or arcs) by E(G) to lessen any ambiguity.
Computer representations
adjacency matrices
For a graph G of order n , an adjacency matrix
representation is a boolean matrix (often encoded with 0's
and 1's) of dimension n such that entry (i,j) is true if and
only if edge/arc (I,j) is in E(G).
adjacency lists
For a graph G of order n , an adjacency lists
representation is n lists such that the i-th list contains a
sequence (often sorted) of out-neighbours of vertex i of G
.
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).
BFS(G,s)
1. for each vertex u in V[G] {s}
2
do color[u] white
3
d[u]
4
[u] nil
5 color[s] gray
6 d[s] 0
7 [s] nil
8 Q
9 enqueue(Q,s)
10 while Q
11
do u dequeue(Q)
12
for each v in Adj[u]
13
do if color[v] = white
14
then color[v] gray
15
d[v] d[u] + 1
16
[v] u
17
enqueue(Q,v)
18
color[u] black
Pseudo-code
DFS(G)
1. for each vertex u V[G]
2.
do color[u] white
3.
[u] NIL
4. time 0
5. for each vertex u V[G]
6.
do if color[u] = white
7.
then DFSVisit(u)
DFS-Visit(u)
1.
color[u] GRAY White vertex u
has been discovered
2.
time time + 1
3.
d[u] time
4.
for each v Adj[u]
5.
do if color[v] = WHITE
6.
then [v] u
7.
DFS-Visit(v)
8.
color[u] BLACK Blacken u;
it is finished.
9.
f[u] time time + 1
DIJKSTRA'S ALGORITHM PSEUDOCODE
dist[s] 0
(distance to source vertex is zero)
for all v V{s}
do dist[v]
(set all other distances to infinity)
S
(S, the set of visited vertices is initially empty)
QV
(Q, the queue initially contains all vertices)
while Q
(while the queue is not empty)
do u mindistance(Q,dist)
(select the element of Q with the min. distance)
SS{u}
(add u to list of visited vertices)
for all v neighbors[u]
do if dist[v] > dist[u] + w(u, v)
(if new shortest path found)
then d[v] d[u] + w(u, v)
(set new value of shortest path)
(if desired, add traceback code)
return dist
Example
A
0
4
2
B
7
5
E
C
3
B
2
7
5
E
D
8
0
4
C
3
D
11
7
5
E
C
3
D
8
Example (cont.)
A
0
4
2
B
C
3
5
E
D
8
5
A
0
4
2
B
2
C
3
5
E
D
8
Prims algorithm
e d b c a
9
Vertex Parent
e
b
c
d
-
d b c a
4 5 5
Vertex Parent
e
b
e
c
e
d
e
The MST initially consists of the vertex e, and we update
the distances and parent for its adjacent vertices
Prims algorithm
d b c a
9
4 5 5
Vertex Parent
e
b
e
c
e
d
e
4
5
e
a c b
2 4 5
Vertex Parent
e
b
e
c
d
d
e
a
d
Prims algorithm
a c b
2 4 5
b
6
4
5
Vertex Parent
e
b
e
c
d
d
e
a
d
e
c b
4 5
Vertex Parent
e
b
e
c
d
d
e
a
d
Prims algorithm
c b
9
4 5
4
5
Vertex Parent
e
b
e
c
d
d
e
a
d
e
b
5
Vertex Parent
e
b
e
c
d
d
e
a
d
Prims algorithm
b
9
4
5
Vertex Parent
e
b
e
c
d
d
e
a
d
The final minimum spanning tree
Vertex Parent
e
b
e
c
d
d
e
a
d
Prims Algorithm
Initialization
a. Pick a vertex r to be the root
b. Set D(r) = 0, parent(r) = null
c. For all vertices v V, v r, set D(v) =
d. Insert all vertices into priority queue P,
using distances as the keys
9
b
6
e a b c d
4
5
Vertex Parent
e
-
Prims Algorithm
While P is not empty:
1. Select the next vertex u to add to the tree
u = [Link]()
2. Update the weight of each vertex w adjacent to
u which is not in the tree (i.e., w P)
If weight(u,w) < D(w),
a. parent(w) = u
b. D(w) = weight(u,w)
c. Update the priority queue to reflect
new distance for w
Kruskals algorithm
9
b
6
E = {(a,d), (c,d), (d,e), (a,c),
4
5
(b,e), (c,e), (b,d), (a,b)}
Forest
{a}, {b}, {c}, {d}, {e}
{a,d}, {b}, {c}, {e}
{a,d,c}, {b}, {e}
{a,d,c,e}, {b}
{a,d,c,e,b}
{(a,d)}
{(a,d), (c,d)}
{(a,d), (c,d), (d,e)}
{(a,d), (c,d), (d,e), (b,e)}
Kruskals Algorithm
A priority queue stores
the edges outside the
cloud
Key: weight
Element: edge
At the end of the
algorithm
We are left with one
cloud that encompasses
the MST
A tree T which is our
MST
Algorithm KruskalMST(G)
for each vertex V in G do
define a Cloud(v) {v}
let Q be a priority queue.
Insert all edges into Q using their
weights as the key
T
while T has fewer than n-1 edges do
edge e = [Link]()
Let u, v be the endpoints of e
if Cloud(v) Cloud(u) then
Add edge e to T
Merge Cloud(v) and Cloud(u)
return T
Digraphs
wake up
A typical student day
2
study computer sci.
7
play
eat
4
work
5
more c.s.
8
write c.s. program
rest
9
make cookies
for c.s. prof.
10
sleep
11
dream of cs16
Algorithm for Topological Sorting
Method TopologicalSort(G)
HG
// Temporary copy of G
n [Link]()
while H is not empty do
Let v be a vertex with no outgoing edges
Label v n
nn-1
Remove v from H
Running time: O(n + m).
Topological Sorting Algorithm
using DFS
Simulate the algorithm by using
depth-first search
Algorithm topologicalDFS(G)
Input dag G
Output topological ordering of G
n [Link]()
for all u [Link]()
setLabel(u, UNEXPLORED)
for all e [Link]()
setLabel(e, UNEXPLORED)
for all v [Link]()
if getLabel(v) = UNEXPLORED
topologicalDFS(G, v)
O(n+m) time.
Algorithm topologicalDFS(G, v)
Input graph G and a start vertex v of G
Output labeling of the vertices of G
in the connected component of v
setLabel(v, VISITED)
for all e [Link](v)
if getLabel(e) = UNEXPLORED
w opposite(v,e)
if getLabel(w) = UNEXPLORED
setLabel(e, DISCOVERY)
topologicalDFS(G, w)
else
{e is a forward or cross edge}
Label v with topological number n
nn-1
Topological Sorting Example
Topological Sorting Example
Topological Sorting Example
Topological Sorting Example
7
8
Topological Sorting Example
6
7
8
Topological Sorting Example
5
7
Topological Sorting Example
4
6
5
7
Topological Sorting Example
4
6
5
7
Topological Sorting Example
2
3
4
6
5
7
Topological Sorting Example
2
4
6
5
7
The End
