Directed Graphs BOS
ORD
JFK
SFO
DFW
LAX
MIA
Directed Graphs 1
Outline and Reading (§6.4)
Reachability (§6.4.1)
Directed DFS
Strong connectivity
Transitive closure (§6.4.2)
The Floyd-Warshall Algorithm
Directed Acyclic Graphs (DAG’s) (§6.4.4)
Topological Sorting
Directed Graphs 2
Digraphs
A digraph is a graph E
whose edges are all
directed D
Short for “directed graph”
Applications C
one-way streets B
flights
task scheduling A
Directed Graphs 3
E
Digraph Properties D
A graph G=(V,E) such that B
Each edge goes in one direction: A
Edge (a,b) goes from a to b, but not b to a.
If G is simple, m < n(n-1).
If we keep in-edges and out-edges in separate
adjacency lists, we can perform listing of of
the sets of in-edges and out-edges in time
proportional to their size.
Directed Graphs 4
Digraph Application
Scheduling: edge (a,b) means task a must be
completed before b can be started
ics21 ics22 ics23
ics51 ics53 ics52
ics161
ics131 ics141 ics121 ics171
ics151 The good life
Directed Graphs 5
Directed DFS
We can specialize the
traversal algorithms (DFS and
BFS) to digraphs by E
traversing edges only along
their direction
D
In the directed DFS
algorithm, we have four
types of edges C
discovery edges
back edges B
forward edges
cross edges
A directed DFS starting at a
A
vertex s determines the
vertices reachable from s
Directed Graphs 6
Reachability
DFS tree rooted at v: vertices reachable
from v via directed paths
E D
E D C
A
C F
E D
A B
C F
A B
Directed Graphs 7
Strong Connectivity
Each vertex can reach all other vertices
a
g
c
d
e
b
f
Directed Graphs 8
Strong Connectivity
Algorithm
Pick a vertex v in G.
a
Perform a DFS from v in G. G: c
g
If there’s a w not visited, print “no”.
d
Let G’ be G with edges reversed. e
Perform a DFS from v in G’. f b
If there’s a w not visited, print “no”.
Else, print “yes”. a
g
G’: c
d
Running time: O(n+m). e
f b
Directed Graphs 9
Strongly Connected
Components
Maximal subgraphs such that each vertex can reach
all other vertices in the subgraph
Can also be done in O(n+m) time using DFS, but is
more complicated (similar to biconnectivity).
a
g {a,c,g}
c
d
e {f,d,e,b}
f b
Directed Graphs 10
Transitive Closure
Given a digraph G, the D E
transitive closure of G is the
digraph G* such that B
G
G* has the same vertices C
as G
A
if G has a directed path
from u to v (u ≠ v), G*
has a directed edge from D E
u to v
The transitive closure B
provides reachability
information about a digraph C
A G*
Directed Graphs 11
Computing the
Transitive Closure
If there's a way to get
We can perform from A to B and from
DFS starting at B to C, then there's a
each vertex way to get from A to C.
O(n(n+m))
Alternatively ... Use
dynamic programming:
the Floyd-Warshall
Algorithm
Directed Graphs 12
Floyd-Warshall
Transitive Closure
Idea #1: Number the vertices 1, 2, …, n.
Idea #2: Consider paths that use only
vertices numbered 1, 2, …, k, as
intermediate vertices:
Uses only vertices numbered 1,…,k
(add this edge if it’s not already in)
i
Uses only vertices j
numbered 1,…,k-1 Uses only vertices
k numbered 1,…,k-1
Directed Graphs 13
Floyd-Warshall’s Algorithm
Floyd-Warshall’s algorithm Algorithm FloydWarshall(G)
numbers the vertices of G as Input digraph G
v1 , …, vn and computes a Output transitive closure G* of G
series of digraphs G0, …, Gn i←1
for all v ∈ [Link]()
G0=G
denote v as vi
Gk has a directed edge (vi, vj)
i←i+1
if G has a directed path from G0 ← G
vi to vj with intermediate
for k ← 1 to n do
vertices in the set {v1 , …, vk}
Gk ← Gk − 1
We have that Gn = G* for i ← 1 to n (i ≠ k) do
In phase k, digraph Gk is for j ← 1 to n (j ≠ i, k) do
computed from Gk − 1 if Gk − [Link](vi, vk) ∧
Running time: O(n3), Gk − [Link](vk, vj)
assuming areAdjacent is O(1) if ¬[Link](vi, vj)
(e.g., adjacency matrix) [Link](vi, vj , k)
return Gn
Directed Graphs 14
Floyd-Warshall Example v7
BOS
ORD v4
JFK
v2 v6
SFO
DFW
LAX
v3
v1
MIA
v5
Directed Graphs 15
Floyd-Warshall, Iteration 1 v7
BOS
ORD v4
JFK
v2 v6
SFO
DFW
LAX
v3
v1
MIA
v5
Directed Graphs 16
Floyd-Warshall, Iteration 2 v7
BOS
ORD v4
JFK
v2 v6
SFO
DFW
LAX
v3
v1
MIA
v5
Directed Graphs 17
Floyd-Warshall, Iteration 3 v7
BOS
ORD v4
JFK
v2 v6
SFO
DFW
LAX
v3
v1
MIA
v5
Directed Graphs 18
Floyd-Warshall, Iteration 4 v7
BOS
ORD v4
JFK
v2 v6
SFO
DFW
LAX
v3
v1
MIA
v5
Directed Graphs 19
Floyd-Warshall, Iteration 5 v7
BOS
ORD v4
JFK
v2 v6
SFO
DFW
LAX
v3
v1
MIA
v5
Directed Graphs 20
Floyd-Warshall, Iteration 6 v7
BOS
ORD v4
JFK
v2 v6
SFO
DFW
LAX
v3
v1
MIA
v5
Directed Graphs 21
Floyd-Warshall, Conclusion v7
BOS
ORD v4
JFK
v2 v6
SFO
DFW
LAX
v3
v1
MIA
v5
Directed Graphs 22
DAGs and Topological Ordering
A directed acyclic graph (DAG) is a D E
digraph that has no directed cycles
A topological ordering of a digraph B
is a numbering
v1 , …, vn
C
of the vertices such that for every A DAG G
edge (vi , vj), we have i < j
Example: in a task scheduling v4 v5
digraph, a topological ordering a D E
task sequence that satisfies the v2
precedence constraints
B
Theorem v3
A digraph admits a topological v1 C
ordering if and only if it is a DAG Topological
A ordering of G
Directed Graphs 23
Topological Sorting
Number vertices, so that (u,v) in E implies u < v
1 A typical student day
wake up
2 3
eat
study computer sci.
4 5
nap more c.s.
7
play
8
write c.s. program 6
9 work out
make cookies
for professors
10
sleep 11
dream about graphs
Directed Graphs 24
Algorithm for Topological Sorting
Note: This algorithm is different than the
one in Goodrich-Tamassia
Method TopologicalSort(G)
H←G // Temporary copy of G
n ← [Link]()
while H is not empty do
Let v be a vertex with no outgoing edges
Label v ← n
n←n-1
Remove v from H
Running time: O(n + m). How…?
Directed Graphs 25
Topological Sorting
Algorithm using DFS
Simulate the algorithm by using Algorithm topologicalDFS(G, v)
depth-first search Input graph G and a start vertex v of G
Algorithm topologicalDFS(G) Output labeling of the vertices of G
in the connected component of v
Input dag G
setLabel(v, VISITED)
Output topological ordering of G
n ← [Link]() for all e ∈ [Link](v)
for all u ∈ [Link]() if getLabel(e) = UNEXPLORED
setLabel(u, UNEXPLORED) w ← opposite(v,e)
for all e ∈ [Link]() if getLabel(w) = UNEXPLORED
setLabel(e, UNEXPLORED) setLabel(e, DISCOVERY)
for all v ∈ [Link]() topologicalDFS(G, w)
if getLabel(v) = UNEXPLORED else
topologicalDFS(G, v) {e is a forward or cross edge}
Label v with topological number n
O(n+m) time. n←n-1
Directed Graphs 26
Topological Sorting Example
Directed Graphs 27
Topological Sorting Example
9
Directed Graphs 28
Topological Sorting Example
9
Directed Graphs 29
Topological Sorting Example
7
8
9
Directed Graphs 30
Topological Sorting Example
7
8
9
Directed Graphs 31
Topological Sorting Example
6 5
7
8
9
Directed Graphs 32
Topological Sorting Example
4
6 5
7
8
9
Directed Graphs 33
Topological Sorting Example
3
4
6 5
7
8
9
Directed Graphs 34
Topological Sorting Example
2
3
4
6 5
7
8
9
Directed Graphs 35
Topological Sorting Example
2
1
3
4
6 5
7
8
9
Directed Graphs 36