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 = P.deleteMin()
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 = T.removeMin()
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 G.numVertices()
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 G.numVertices()
for all u G.vertices()
setLabel(u, UNEXPLORED)
for all e G.edges()
setLabel(e, UNEXPLORED)
for all v G.vertices()
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 G.incidentEdges(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