Elementary

Elementary Graph
Graph Algorithms
Algorithms
 Graphs
 Graph G = (V, E)
» V = set of vertices
» E = set of edges  (VV)
 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.
 |E| = O(|V|2)
aphs-1 - 2 Lin / Devi
 Graphs
 If (u, v)  E, then vertex v is adjacent to vertex u.
 Adjacency relationship is:
» Symmetric if G is undirected.
» Not necessarily so 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.

 Other definitions in Appendix B (B.4 and B.5) as needed.

aphs-1 - 3 Lin / Devi

 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

aphs-1 - 4 Lin / Devi

 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.
a b a b d c

b c

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

a b a b d c

b a c

c d c d a b

d a c

aphs-1 - 5 Lin / Devi

 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)

aphs-1 - 6 Lin / Devi

 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 list. (degree(u)) time.
 (V) in the worst case.

aphs-1 - 7 Lin / Devi

 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
2 1 0 1 0 A = AT for undirected graphs.
c d 3 1 1 0 1
3 4 4 1 0 1 0
aphs-1 - 8 Lin / Devi
 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).
 Can store weights instead of bits for weighted graph.

aphs-1 - 9 Lin / Devi

 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).

aphs-1 - 10 Lin / Devi

 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.
Definitions:
Path between vertices u and v: Sequence of vertices (v1, v2, …, vk) such that
u=v1 and v =vk, and (vi,vi+1)  E, for all 1 i  k-1.
Length of the path: Number of edges in the path.
Path is simple if no vertex is repeated.
aphs-1 - 11 Lin / Devi
 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.

aphs-1 - 12 Lin / Devi

 BFS(G,s)
BFS(G,s)
1.1. for
foreach
eachvertex
vertexuuininV[G]
V[G]–– {s}{s}
22 do color[u]
docolor[u] white
white
33 d[u]
d[u] 
44 [u]
[u]nilnil white: undiscovered
color[s]
55 color[s] gray
gray gray: discovered
black: finished
d[s]
66 d[s] 00
77 [s][s]
nil
nil
88 QQ  Q: a queue of discovered
99 enqueue(Q,s)
enqueue(Q,s) vertices
color[v]: color of v
10 whileQQ
10 while d[v]: distance from s to v
11
11 douu
do dequeue(Q)
dequeue(Q) [u]: predecessor of v
12
12 for
foreach
eachvvininAdj[u]
Adj[u]
13
13 do
doififcolor[v]
color[v]==white
white
14
14 then color[v]
thencolor[v]  Example: animation.
gray
gray
15
15 d[v]
d[v] d[u]
d[u]++
11
16
16 [v]
[v]
uu
17
17 enqueue(Q,v)
enqueue(Q,v)
18
18 color[u]
color[u] black
black
aphs-1 - 14 Lin / Devi
 Example (BFS)
(Courtesy of Prof. Jim Anderson)

r s t u
 0  

   
v w x y

Q: s
0

aphs-1 - 15 Lin / Devi

 Example (BFS)

r s t u
1 0  

 1  
v w x y

Q: w r
1 1

aphs-1 - 16 Lin / Devi

 Example (BFS)

r s t u
1 0 2 

 1 2 
v w x y

Q: r t x
1 2 2

aphs-1 - 17 Lin / Devi

 Example (BFS)

r s t u
1 0 2 

2 1 2 
v w x y

Q: t x v
2 2 2

aphs-1 - 18 Lin / Devi

 Example (BFS)

r s t u
1 0 2 3

2 1 2 
v w x y

Q: x v u
2 2 3

aphs-1 - 19 Lin / Devi

 Example (BFS)

r s t u
1 0 2 3

2 1 2 3
v w x y

Q: v u y
2 3 3

aphs-1 - 20 Lin / Devi

 Example (BFS)

r s t u
1 0 2 3

2 1 2 3
v w x y

Q: u y
3 3

aphs-1 - 21 Lin / Devi

 Example (BFS)

r s t u
1 0 2 3

2 1 2 3
v w x y

Q: y
3

aphs-1 - 22 Lin / Devi

 Example (BFS)

r s t u
1 0 2 3

2 1 2 3
v w x y

Q: 

aphs-1 - 23 Lin / Devi

 Example (BFS)

r s t u
1 0 2 3

2 1 2 3
v w x y

BF Tree

aphs-1 - 24 Lin / Devi

 Analysis of BFS
 Initialization takes O(V).
 Traversal Loop
» After initialization, each vertex is enqueued and dequeued at
most once, and each operation takes O(1). So, total time for
queuing is O(V).
» The adjacency list of each vertex is scanned at most once. The
sum of lengths of all adjacency lists is (E).
 Summing up over all vertices => total running time of BFS
is O(V+E), linear in the size of the adjacency list
representation of graph.
 Correctness Proof
» We omit for BFS and DFS.
» Will do for later algorithms.

aphs-1 - 25 Lin / Devi

 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.
aphs-1 - 26 Lin / Devi
 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.
aphs-1 - 27 Lin / Devi
 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.

aphs-1 - 28 Lin / Devi

 Pseudo-code
DFS(G)
DFS(G) DFS-Visit(u)
DFS-Visit(u)
1.1. for
foreach vertexuuV[G]
eachvertex V[G] color[u]
1.1. color[u] GRAY White
GRAY Whitevertex
vertexuu
has
hasbeenbeendiscovered
2.2. do color[u]
docolor[u] white
white discovered
3.3. [u]
[u] NIL
NIL time
2.2. time time
time++11
time
4.4. time 00
3.3. d[u]
d[u] timetime
5.5. for
foreach vertexuuV[G]
eachvertex V[G]
4.4. for eachvvAdj[u]
foreach Adj[u]
6.6. do 5.5. do
doififcolor[v]
color[v]==WHITE
doififcolor[u]
color[u]==white
white WHITE
7.7. then
thenDFS-Visit(u)
DFS-Visit(u)
6.6. then[v]
then [v]uu
7.7. DFS-Visit(v)
DFS-Visit(v)
8.8. color[u]
color[u] BLACK Blacken
BLACK Blackenu;u;
Uses a global timestamp time. ititisisfinished.
finished.
9.9. f[u]
f[u] time
time time
time++11
Example: animation.

aphs-1 - 29 Lin / Devi

 Example (DFS)
(Courtesy of Prof. Jim Anderson)

u v w
1/

x y z

aphs-1 - 30 Lin / Devi

 Example (DFS)

u v w
1/ 2/

x y z

aphs-1 - 31 Lin / Devi

 Example (DFS)

u v w
1/ 2/

3/
x y z

aphs-1 - 32 Lin / Devi

 Example (DFS)

u v w
1/ 2/

4/ 3/
x y z

aphs-1 - 33 Lin / Devi

 Example (DFS)

u v w
1/ 2/
B

4/ 3/
x y z

aphs-1 - 34 Lin / Devi

 Example (DFS)

u v w
1/ 2/
B

4/5 3/
x y z

aphs-1 - 35 Lin / Devi

 Example (DFS)

u v w
1/ 2/
B

4/5 3/6
x y z

aphs-1 - 36 Lin / Devi

 Example (DFS)

u v w
1/ 2/7
B

4/5 3/6
x y z

aphs-1 - 37 Lin / Devi

 Example (DFS)

u v w
1/ 2/7

F B

4/5 3/6
x y z

aphs-1 - 38 Lin / Devi

 Example (DFS)

u v w
1/8 2/7

F B

4/5 3/6
x y z

aphs-1 - 39 Lin / Devi

 Example (DFS)

u v w
1/8 2/7 9/

F B

4/5 3/6
x y z

aphs-1 - 40 Lin / Devi

 Example (DFS)

u v w
1/8 2/7 9/

F B C

4/5 3/6
x y z

aphs-1 - 41 Lin / Devi

 Example (DFS)

u v w
1/8 2/7 9/

F B C

4/5 3/6 10/

x y z

aphs-1 - 42 Lin / Devi

 Example (DFS)

u v w
1/8 2/7 9/

F B C

4/5 3/6 10/ B

x y z

aphs-1 - 43 Lin / Devi

 Example (DFS)

u v w
1/8 2/7 9/

F B C

4/5 3/6 10/11 B

x y z

aphs-1 - 44 Lin / Devi

 Example (DFS)

u v w
1/8 2/7 9/12

F B C

4/5 3/6 10/11 B

x y z

aphs-1 - 45 Lin / Devi

 Analysis of DFS
 Loops on lines 1-2 & 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 3-6 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).

aphs-1 - 46 Lin / Devi