Basic Graph Algorithms

(CLRS B.4-B.5, 22.1-22.4)

1 Basic Graph Definitions

• A graph G = (V, E) consists of a finite set of vertices V and a finite set of edges E.
– Directed graphs: E is a set of ordered pairs of vertices (u, v) where u, v ∈ V

1 2 3

V = {1, 2, 3, 4, 5, 6}

E = {(1,2), (2,2), (2,4), (2,5)

4 5 6 (4,1), (4,5), (5,4), (6,3)}

– Undirected graph: E is a set of unordered pairs of vertices {u, v} where u, v ∈ V

1 2 3

V = {1, 2, 3, 4, 5, 6}

E = {{1,2}, {1,5}, {2,5}, {3,6}}

4 5 6

• Edge (u, v) is incident to u and v

• Degree of vertex in undirected graph is the number of edges incident to it.
• In (out) degree of a vertex in directed graph is the number of edges entering (leaving) it.
• A path from u1 to u2 is a sequence of vertices < u1 =v0 , v1 , v2 , · · · , vk =u2 > such that
(vi , vi+1 ) ∈ E (or {vi , vi+1 } ∈ E)
– We say that u2 is reachable from u1
– The length of the path is k
– It is a cycle if v0 = vk
• An undirected graph is connected if every pair of vertices are connected by a path
– The connected components are the equivalence classes of the vertices under the “reach-
ability” relation. (All connected pair of vertices are in the same connected component).

1
 • A directed graph is strongly connected if every pair of vertices are reachable from each other

– The strongly connected components are the equivalence classes of the vertices under the
“mutual reachability” relation.

• Graphs appear all over the place in all kinds of applications, e.g:

– Trees (|E| = |V | − 1)
– Connectivity/dependencies (house building plans, WWW-page connections = internet
graph)

• Often the edges (u, v) in a graph have weights w(u, v), e.g.

– Road networks (distances)

– Cable networks (capacity)

1.1 Representation
• Adjacency-list representation:

– Array of |V | list of edges incident to each vertex.

Examples:

1 2
1 2 3
2 2 4 5

3
4 5 1

5 4
4 5 6
6 3

1 2 5
1 2 3
2 1 5
3 6
4
5 2 1
4 5 6
6 3

– Note: For undirected graphs, every edge is stored twice.

– If graph is weighted, a weight is stored with each edge.

• Adjacency-matrix representation:

2
 – |V | × |V | matrix A where (
1 if (i, j) ∈ E
aij =
0 otherwise
Examples:
j
1 2 3 4 5 6
1 2 3
1 0 1 0 0 0 0
2 0 1 0 1 1 0
3 0 0 0 0 0 0
i
4 1 0 0 0 1 0
5 0 0 0 1 0 0
6 0 0 1 0 0 0
4 5 6
j
1 2 3 4 5 6
1 2 3
1 0 1 0 0 1 0
2 1 0 0 0 1 0

i 3 0 0 0 0 0 1
4 0 0 0 0 0 0
5 1 1 0 0 0 0
6 0 0 1 0 0 0
4 5 6

– Note: For undirected graphs, the adjacency matrix is symmetric along the main diagonal
(AT = A).
– If graph is weighted, weights are stored instead of one’s.
• Comparison of matrix and list representation:

Adjacency list Adjacency matrix

O(|V | + |E|) space O(|V |2 ) space

Good if graph sparse (|E| << |V |2 ) Good if graph dense (|E| ≈ |V |2 )
No quick access to (u, v) O(1) access to (u, v)
• We will use adjacency list representation unless stated otherwise (O(|V | + |E|) space).

2 Graph traversal
• There are two standard (and simple) ways of traversing all vertices/edges in a graph in a
systematic way
– Breadth-first
– Depth-first
• We can use them in many fundamental algorithms, e.g finding cycles, connected components,
...

3
2.1 Breadth-first search (BFS)
• Main idea:

– Start at some source vertex s and visit,

– All vertices at distance 1,
– Followed by all vertices at distance 2,
– Followed by all vertices at distance 3,
..
.

• BFS corresponds to computing shortest path distance (number of edges) from s to all other
vertices.

• To control progress of our BFS algorithm, we think about coloring each vertex

– White before we start,

– Gray after we visit the vertex but before we have visited all its adjacent vertices,
– Black after we have visited the vertex and all its adjacent vertices (all adjacent vertices
are gray).

• We use a queue Q to hold all gray vertices—vertices we have seen but are still not done with.

• We remember from which vertex a given vertex v is colored gray – i.e. the node that discovered
v first; this is called parent[v].

• Algorithm:

BFS(s)
color[s] = gray
d[s] = 0
ENQUEUE(Q, s)
WHILE Q not empty DO
DEQUEUE(Q, u)
FOR (u, v) ∈ E DO
IF color[v] = white THEN
color[v] = gray
d[v] = d[u] + 1
parent[v] = u
ENQUEUE(Q, v)
FI
color[u] = black
OD

4
• Algorithm runs in O(|V | + |E|) time
• Example (for directed graph):
a) b)
a s d f 1
11
00
00
11 11
00
00
11
00
11 00
11
Q: Q : c, a
111
000
000
111
000
111
b c e g 1

c)
1 2 d) 1 2
11
00
00
11 111
000
000
111 111
000
000
111 11
00
00
11
00
11 000
111 000
111 00
11
Q : a, d, e Q : d, e, b
111
000
000
111 11
00
00
11 11
00
00
11
000
111
000
111 00
11
00
11 00
11
00
11
1 2 2 1 2

e)
1 2 3 f) 1 2 3
11
00
00
11 11
00
00
11 111
000
000
111 11
00
00
11
00
11 00
11 000
111 00
11
Q : e, b, f Q : b, f
11
00
00
11 111
000
000
111 11
00
00
11
00
11 000
111 00
11
2 1 2 2 1 2

g) h)
1 11
00
00
11
2 00
11
3
11
00
1 111
000
000
111
2 3
00
11
00
11 00
11
00
11 000
111
000
111
Q:f Q:g
11
00
00
11 11
00
00
11
00
11 00
11
2 1 2 2 1 2 4

i)
1 2 3
11
00 11
00
00
11
00
11 00
11
00
11
Q:

2 1 2 4

• Note:
– parent[v] forms a tree; BFS-tree.
– d[v] contains length of shortest path from s to v. (Prove by induction)
– We can use parent[v] to find the shortest path from s to a given vertex.
• If graph is not connected we have to try to start the traversal at all nodes.

FOR each vertex u ∈ V DO

IF color[u] = white THEN BFS(u)
OD

5
 – Note: We can use algorithm to compute connected components in O(|V | + |E|) time.

2.2 Depth-first search (DFS)

• If we use stack instead of queue Q we get another traversal order; depth-first

– We go “as deep as possible”,

– Go back until we find unexplored adjacent vertex,
– Go as deep as possible,
..
.

• Often we are interested in “start time” and “finish time” of vertex u

– Start time (d[u]): indicates at what “time” vertex is first visited.

– Finish time (f[u]): indicates at what “time” all adjacent vertices have been visited.

• We can write DFS iteratively using the same algorithm as for BFS but with a STACK instead
of a QUEUE, or, we can write a recursive DFS procedure

– We will color a vertex gray when we first meet it and black when we finish processing
all adjacent vertices.

• Algorithm:

DFS(u)
color[u] = gray
d[u] = time
time = time + 1
FOR (u, v) ∈ E DO
IF color[v] = white THEN
parent[v] = u
DFS(v)
FI
OD
color[u] = black
f [u] = time
time = time + 1

• Algorithm runs in O(|V | + |E|) time

– As before we can extend algorithm to unconnected graphs and we can use it to detect
cycles in O(|V | + |E|) time.

6
 • Example:
idth=12cmdfs1.pdf
g) h)
1/ 3/ 4/ 1/ 3/ 4/
111
000
000
111 11
00
00
11 11
00
00
11 11
00
00
11 11
00
00
11 000
111
00 111
000
000
111 00
11 00
11 00
11 11 000
111

111
000 11
00 11
00
000
111 00
11 00
11
000
111 00
11 00
11
2/ 6/7 5/ 2/ 6/7 5/8

i) j)
1/ 3/ 4/9 1/ 3/10 4/9
111
000 11
00 11
00
000
111
000
111 00
11
00
11 00
11
00
11

111
000 11
00
000
111 00
11
000
111 00
11
2/ 6/7 5/8 2/ 6/7 5/8

k) l)
1/ 3/10 4/9 1/ 3/10 4/9
111
000 11
00 11
00 111
000
000
111 00
11 00
11 000
111
000
111 00
11 00
11 000
111

111
000 11
00
000
111 00
11
000
111 00
11
000
111 00
11
2/11 6/7 5/8 2/11 6/7 5/8
m) n)
12/ 1/ 3/10 4/9 12/ 1/ 3/10 4/9
11 111
00 000 11
00 11
00 11
00 111
000
00
11
00 111
11 000
000
111 00
11
00
11 00
11
00
11 00
11
00
11 000
111
000
111

11
00 11
00 11
00
00
11
00
11 00
11
00
11 00
11
00
11
2/11 6/7 5/8 13/ 2/11 6/7 5/8

o) p)
12/ 1/ 3/10 4/9 12/15 1/16 3/10 4/9
11
00
00
11 000
111 11
00 11
00 111
000
00 111
000 00
11 00
11 000
111
11 000
111 00
11 00
11 000
111

11
00 11
00
00
11 00
11
00
11 00
11
13/14 2/11 6/7 5/8 13/14 2/11 6/7 5/8

• As previously parent[v] forms a tree; DFS-tree

– Note: If u is descendent of v in DFS-tree then d[v] < d[u] < f [u] < f [v]

3 Topological sorting
• Definition: Topological sorting of directed acyclic graph G = (V, E) is a linear ordering of
vertices V such that (u, v) ∈ E ⇒ u appear before v in ordering.

7
• Topological ordering can be used in scheduling:

– Example: Dressing (arrow implies “must come before”)

Socks
Watch
Underwear Shoes

Shirt
Pants

Tie
Belt

Jacket

We want to compute order in which to get dressed. One possibility:

Socks Underwear Pants Shoes Watch Shirt Belt Tie Jacket

1 2 3 4 5 6 7 8 9

The given order is one possible topological order.

• Algorithm: Topological order just reverse DFS finish time (⇒ O(|V | + |E|) running time).

• Correctness: (u, v) ∈ E ⇔ f (v) < f (u)

– Proof: When (u, v) is explored by DFS algorithm, v must be white or black (gray ⇒
cycle).
∗ v white: v visited and finished before u is finished ⇒ f (v) < f (u)
∗ v black: v already finished ⇒ f (v) < f (u)

• Alternative algorithm: Count in-degree of each vertex and repeatedly number and remove
in-degree 0 vertex and its outgoing edges: Homework.