Elementary Graph 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)
 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.
 An edge (u, v) is said to be incident to u and v
 Degree of a vertex in undirected graph is the number of
edges incident to it.
 In-degree of a vertex in directed graph is the number of
edges entering it.
 Out-degree of a vertex in directed graph is the number of
edges leaving it.
Graphs
 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
 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
 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)
 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.
 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
 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.
 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).
 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.
 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.
BFS(G,s)
1. for each vertex u in V[G] – {s}
2 do color[u] ← white
3 d[u] ← ∝
white: undiscovered
4 π[u] ← nil gray: discovered
5 color[s] ← gray black: finished
6 d[s] ← 0
7 π[s] ← nil Q: a queue of discovered
8 Q←Φ vertices
9 enqueue(Q,s) color[v]: color of v
d[v]: distance from s to v
10 while Q ≠ Φ π[u]: predecessor of v
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
 Example (BFS)

r s t u
∞ 0 ∞ ∞

∞ ∞ ∞ ∞
v w x y

Q: s
0
 Example (BFS)

r s t u
1 0 ∞ ∞

∞ 1 ∞ ∞
v w x y

Q: w r
1 1
 Example (BFS)

r s t u
1 0 2 ∞

∞ 1 2 ∞
v w x y

Q: r t x
1 2 2
 Example (BFS)

r s t u
1 0 2 ∞

2 1 2 ∞
v w x y

Q: t x v
2 2 2
 Example (BFS)

r s t u
1 0 2 3

2 1 2 ∞
v w x y

Q: x v u
2 2 3
 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
 Example (BFS)

r s t u
1 0 2 3

2 1 2 3
v w x y

Q: u y
3 3
 Example (BFS)

r s t u
1 0 2 3

2 1 2 3
v w x y

Q: y
3
 Example (BFS)

r s t u
1 0 2 3

2 1 2 3
v w x y

Q: ∅
 Example (BFS)

r s t u
1 0 2 3

2 1 2 3
v w x y

BF Tree
 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.
 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.
 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.
 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.
 Pseudo-code
DFS(G) DFS-Visit(u)
1. for each vertex u ∈ V[G] 1. color[u] ← GRAY ∇ White vertex u
2. do color[u] ← white has been discovered
3. π[u] ← NIL 2. time ← time + 1
4. time ← 0 3. d[u] ← time
5. for each vertex u ∈ V[G] 4. for each v ∈ Adj[u]
6. do if color[u] = white 5. do if color[v] = WHITE
7. then DFS-Visit(u) 6. then π[v] ← u
7. DFS-Visit(v)
8. color[u] ← BLACK ∇ Blacken u;
Uses a global timestamp time. it is finished.
9. f[u] ← time ← time + 1
Example (DFS)

u v w
1/

x y z
Example (DFS)

u v w
1/ 2/

x y z
Example (DFS)

u v w
1/ 2/

3/
x y z
Example (DFS)

u v w
1/ 2/

4/ 3/
x y z
Example (DFS)

u v w
1/ 2/
B

4/ 3/
x y z
Example (DFS)

u v w
1/ 2/
B

4/5 3/
x y z
Example (DFS)

u v w
1/ 2/
B

4/5 3/6
x y z
Example (DFS)

u v w
1/ 2/7
B

4/5 3/6
x y z
Example (DFS)

u v w
1/ 2/7

F B

4/5 3/6
x y z
Example (DFS)

u v w
1/8 2/7

F B

4/5 3/6
x y z
Example (DFS)

u v w
1/8 2/7 9/

F B

4/5 3/6
x y z
Example (DFS)

u v w
1/8 2/7 9/

F B C

4/5 3/6
x y z
Example (DFS)

u v w
1/8 2/7 9/

F B C

4/5 3/6 10/

x y z
Example (DFS)

u v w
1/8 2/7 9/

F B C

4/5 3/6 10/ B

x y z
Example (DFS)

u v w
1/8 2/7 9/

F B C

4/5 3/6 10/11 B

x y z
Example (DFS)

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

F B C

4/5 3/6 10/11 B

x y z
 DFS(G)
Analysis of DFS 1. for each vertex u ∈ V[G]
2. do color[u] ← white
3. π[u] ← NIL
 Loops on lines 1-3 & 5-7 take 4. time ← 0
Θ(V) time, excluding time to 5. for each vertex u ∈ V[G]
execute DFS-Visit. 6. do if color[u] = white
7. then DFS-Visit(u)
 DFS-Visit is called once for each DFS-Visit(u)
white vertex v∈V when it’s 1. color[u] ← GRAY ∇ White vertex u
painted gray the first time. has been discovered
Lines 4-6 of DFS-Visit is 2. time ← time + 1
3. d[u] ← time
executed |Adj[v]| times. The total
4. for each v ∈ Adj[u]
cost of executing DFS-Visit is
5. do if color[v] = WHITE
∑v∈V|Adj[v]| = Θ(E) 6. then π[v] ← u
7. DFS-Visit(v)
 Total running time of DFS is 8. color[u] ← BLACK ∇ Blacken u;
Θ(V+E). it is finished.
9. f[u] ← time ← time + 1
 Parenthesis Theorem
Theorem:
In any depth-first search of a (directed or undirected) graph G = (V, E),
for any two vertices u and v, exactly one of the following three
conditions holds:
1. d[u] < f [u] < d[v] < f [v] or d[v] < f [v] < d[u] < f [u] and neither u
nor v is a descendant of the other.
2. d[u] < d[v] < f [v] < f [u] and v is a descendant of u.
3. d[v] < d[u] < f [u] < f [v] and u is a descendant of v.
 So d[u] < d[v] < f [u] < f [v] cannot happen.
 Like parentheses:
 OK: ( ) [ ] ( [ ] ) [ ( ) ]
 Not OK: ( [ ) ] [ ( ] )
Corollary
v is a proper descendant of u if and only if d[u] < d[v] < f [v] < f [u].
Example (Parenthesis Theorem)

y z s t
3/6 2/9 1/10 11/16

B F C B

4/5 7/8 12/13

C 14/15
C C
x w v u

(s (z (y (x x) y) (w w) z) s) (t (v v) (u u) t)
Example (Parenthesis Theorem)
 Depth-First Trees
 Predecessor subgraph defined slightly different from
that of BFS.
 The predecessor subgraph of DFS is Gπ = (V, Eπ) where
Eπ ={(π[v],v) : v ∈ V and π[v] ≠ NIL}.
» How does it differ from that of BFS?
» The predecessor subgraph Gπ forms a depth-first forest
composed of several depth-first trees. The edges in Eπ are
called tree edges.

Definition:
Forest: An acyclic graph G that may be disconnected.
 White-path Theorem
Theorem:
v is a descendant of u if and only if at time d[u], there is
a path u-v consisting of only white vertices. (Except for
u, which was just colored gray.)
 Classification of Edges
 Tree edge: an edge in the depth-first forest. Found by
exploring (u, v).
 Back edge: (u, v), where u is a descendant of v (in the
depth-first tree).
 Forward edge: (u, v), where v is a descendant of u, but
not a tree edge.
 Cross edge: any other edge. Can go between vertices in
same depth-first tree or in different depth-first trees.
y z s t
3/6 2/9 1/10 11/16

B F C B

4/5 7/8 12/13 14/15

C C C
x w v u
 Classification of Edges
y z s t
3/6 2/9 1/10 11/16

B F C B

4/5 7/8 12/13

C 14/15
C C
x w v u

Observations:
1. In DFS of an undirected graph, we get only tree and back
edges. No forward or cross edges.
2. A self loop becomes a back edge.
 Identification of Edges
 Edge type for edge (u, v) can be identified when it
is first explored by DFS.
 Identification is based on the color of v.
» White – tree edge.
» Gray – back edge.
» Black – forward or cross edge.
y z s t
3/6 2/9 1/10 11/16

B F C B

4/5 7/8 12/13

C 14/15
C C
x w v u
 BFS vs DFS
BFS DFS
 Search operates in a  Search moves as deep
width wise manner on as possible , hence the
the given graph, hence name.
the name.
 A single source is  No input source is
specified as input. specified, search
selects random sources
from the graph.
 Produces a Breadth  Produces a Depth first
first tree as output. forest as output.
 Uses Queue data  Uses Stack data
structure structure.
 BFS vs DFS
BFS DFS
 Used to find single  Path may not be the
source shortest path in shortest.
an unweighted graph
 Does not guarantee the  Guarantees the total
total coverage coverage
 Suitable for searching  Suitable when there are
vertices which are solutions away from
closer to the given the selected source
source
 Application of BFS:

Testing the Bipartiteness of a graph

 Bipartite graph
 A bipartite graph is a graph whose vertices can be
divided into two disjoint and independent sets U
and V such that every edge connects a vertex in U
to one in V.
Bipartite graph
 Bipartite graph
 A bipartite graph is an undirected graph G = (V, E) in
which the nodes can be colored red or blue such that
every edge has one red and one blue end.
 A bipartite graph is a graph that does not contain any odd-
length cycles.
BFS and Bipartiteness
BFS and Bipartiteness
BFS and Bipartiteness
 Bipartiteness Testing
 How can we test if G is bipartite?
» Do a BFS starting from some node s.
» Color even levels “blue” and odd levels “red”.
» Check each edge to see if any edge has both
endpoints the same color.
Bipartiteness Testing
 Application of DFS:

Topological sorting in a DAG

 Directed Acyclic Graph
 DAG – Directed graph with no cycles.
 Good for modeling processes and structures that have a
partial order:
» a > b and b > c ⇒ a > c.
» But may have a and b such that neither a > b nor b > a.
 Can always make a total order (either a > b or b > a for
all a ≠ b) from a partial order.
 Example
DAG of dependencies for putting on goalie
equipment.
socks shorts T-shirt batting glove

hose chest pad

pants sweater

skates mask

leg pads catch glove

blocker
 Characterizing a DAG
Lemma: A directed graph G is acyclic iff a DFS of G
yields no back edges.

Proof:
 ⇒: Show that back edge ⇒ cycle.
» Suppose there is a back edge (u, v). Then v is ancestor
of u in depth-first forest.
» Therefore, there is a path v u, so v u v is a
cycle.
T T T
v u
B
 Characterizing a DAG
Lemma: A directed graph G is acyclic iff a DFS of G
yields no back edges.
Proof (Contd.):
 ⇐ : Show that a cycle implies a back edge.
» c : cycle in G, v : first vertex discovered in c, (u, v) :
preceding edge in c.
» At time d[v], vertices of c form a white path v u.
» By white-path theorem, u is a descendent of v in depth-
T T T
first forest. v u
» Therefore, (u, v) is a back edge. B
 Topological Sort
Want to “sort” a directed acyclic graph (DAG).

A B D

C E

A B C D E

Think of original DAG as a partial order.

Want a total order that extends this partial order.

 Topological Sort
 Performed on a DAG.
 Linear ordering of the vertices of G such that if (u, v) ∈
E, then u appears somewhere before v.

Topological-Sort (G)
1. call DFS(G) to compute finishing times f [v] for all v ∈ V
2. as each vertex is finished, insert it onto the front of a
linked list
3. return the linked list of vertices

Time: Θ(V + E).

 Example

A B D
1/

C E

Linked List:
 Example

A B D
1/

2/
C E

Linked List:
 Example

A B D
1/

2/3
C E

Linked List:
2/3
E
 Example

A B D
1/4

2/3
C E

Linked List:
1/4 2/3
D E
 Example

A B D
5/ 1/4

2/3
C E

Linked List:
1/4 2/3
D E
 Example

A B D
5/ 1/4

6/ 2/3
C E

Linked List:
1/4 2/3
D E
 Example

A B D
5/ 1/4

6/7 2/3
C E

Linked List:
6/7 1/4 2/3
C D E
 Example

A B D
5/8 1/4

6/7 2/3
C E

Linked List:
5/8 6/7 1/4 2/3
B C D E
 Example

A B D
9/ 5/8 1/4

6/7 2/3
C E

Linked List:
5/8 6/7 1/4 2/3
B C D E
 Example

A B D
9/10 5/8 1/4

6/7 2/3
C E

Linked List:
9/10 5/8 6/7 1/4 2/3
A B C D E