CS 170
DISCUSSION 4
GRAPHS AND PATHS
Raymond Chan
UC Berkeley Fall 17
DEPTH FIRST SEARCH
• Explore all and only nodes reachable from current node.
recursive_DFS (G, v): iterative_DFS (G, v):
previsit(v) stack.push(v)
mark v as visited while stack not empty:
for all v’s neighbors w: v = pop from stack
if vertex w has not been visited: if v not visited
recursive_DFS (G, w) mark v as visited:
postvisit(v) for all v’s neighbors w:
push vertex w to stack
• Visits all vertices once. Uses all edges once.
• O(|V| + |E|)
Raymond Chan, UC Berkeley Fall 2017
DEPTH FIRST SEARCH
• From last discussion
(1, 6)
T A
T C (7, 20)
(2, 3)
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D
I
T T
T
B T T (8, 19)
G H F J
(14, 15) (12, 17) 9, 18
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT
• Previsit() and Postvisit() increments a global count
(1, 6)
T A
T C (7, 20)
(2, 3)
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D
I
T T
T
B T T (8, 19)
G H F J
(14, 15) (12, 17) 9, 18
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT T/F
• If (u, v) is an edge in an indirect graph and during DFS, post(v) <
post(u), then u is an ancestor of v in the DFS tree.
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT T/F
• If (u, v) is an edge in an indirect graph and during DFS, post(v) <
post(u), then u is an ancestor of v in the DFS tree.
• 2 cases (since pre < post):
• pre(u) < pre(v) < post(v) < post(u)
• u is an ancestor v. Explore u’s neighbors before postvisiting u
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT T/F
• If (u, v) is an edge in an indirect graph and during DFS, post(v) < post(u),
then u is an ancestor of v in the DFS tree.
• 2 cases (since pre < post):
• pre(u) < pre(v) < post(v) < post(u)
• u is an ancestor v. Explore u’s neighbors before postvisiting u
• pre(v) < post(v) < pre(u) < post(u)
• Looks at all of v’s neighbors before looking at u.
• Contradiction since there is an edge.
• True
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT
• For any two nodes, u, v, [pre(u), post(u)] and [pre(v), post(v)] are
either disjoint or one is contained in the other.
(1, 6)
T A
T C (7, 20)
(2, 3)
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D
I
T T
T
B T T (8, 19)
G H F J
(14, 15) (12, 17) 9, 18
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT T/F
• In a directed graph, if there is a path from u to v and pre(u) <
pre(v) then u is an ancestor of v in the DFS tree.
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT T/F
• In a directed graph, if there is a path from u to v and pre(u) <
pre(v) then u is an ancestor of v in the DFS tree.
• Consider the case when u and v are a common ancestor’s direct
children.
(1, 6) T (4, 5)
w v
T
u B
(2, 3)
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT T/F
• In a directed graph, if there is a path from u to v and pre(u) < pre(v) then
u is an ancestor of v in the DFS tree.
• Consider the case when u and v are a common ancestor’s direct children.
(1, 6) T (4, 5)
w v
T
u B
(2, 3)
• u gets visited first via w, who then visits v.
• Need information about post visit number
• False
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT T/F
• In any connected undirected graph G, there is a vertex whose
removal leaves G connected.
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT T/F
• In any connected undirected graph G, there is a vertex whose
removal leaves G connected.
• True
Raymond Chan, UC Berkeley Fall 2017
PREVISIT & POSTVISIT T/F
• In any connected indirect graph G, there is a vertex whose
removal leaves G connected.
• True
• Removing any leaf from a DFS tree of the graph.
• These leaves have only one neighbor, otherwise they won’t be
leaves.
• Neighbor is connected to at least one other node.
Raymond Chan, UC Berkeley Fall 2017
DEPTH FIRST SEARCH
• Tree edge (u, v): part of DFS
• pre(u) < pre(v) < post(v) < post(u)
(1, 6)
root
T A
T C (7, 20)
(2, 3)
ancestor to F, J, D, …
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D F
I
T T
T
B T T (8, 19)
G H J F
(14, 15) (12, 17) 9, 18 child of C,
child of F,
parent of J
descendant of C
Raymond Chan, UC Berkeley Fall 2017
DEPTH FIRST SEARCH
• Forward edge (u, v): leads non-child descendant
• pre(u) < pre(v) < post(v) < post(u)
(1, 6)
root
T A
T C (7, 20)
(2, 3)
ancestor to F, J, D, …
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D F
I
T T
T
B T T (8, 19)
G H J F
(14, 15) (12, 17) 9, 18 child of C,
child of F,
parent of J
descendant of C
Raymond Chan, UC Berkeley Fall 2017
DEPTH FIRST SEARCH
• Cross edge (u, v): leads neither defendant nor ancestor
• pre(v) < post(v) < pre(u) < post(u)
(1, 6)
root
T A
T C (7, 20)
(2, 3)
ancestor to F, J, D, …
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D F
I
T T
T
B T T (8, 19)
G H J F
(14, 15) (12, 17) 9, 18 child of C,
child of F,
parent of J
descendant of C
Raymond Chan, UC Berkeley Fall 2017
DEPTH FIRST SEARCH
• Back edge (u, v): leads to ancestor
• pre(v) < pre(u) < post(u) < post(v)
(1, 6)
root
T A
T C (7, 20)
(2, 3)
ancestor to F, J, D, …
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D F
I
T T
T
B T T (8, 19)
G H J F
(14, 15) (12, 17) 9, 18 child of C,
child of F,
parent of J
descendant of C
Raymond Chan, UC Berkeley Fall 2017
CYCLE DETECTION
• There is a cycle if and only if there is a back edge.
• Run DFS.
(1, 6)
root
T A
T C (7, 20)
(2, 3)
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D F
I
T T
T
B T T (8, 19)
G H J F
(14, 15) (12, 17) 9, 18
Raymond Chan, UC Berkeley Fall 2017
STRONGLY CONNECTED COMPONENTS
• Nodes u and v are strongly connected if there is a path from u to
v and there is a path from v to u.
• Strongly connected components are a set of nodes that are
strongly connected.
• Can visit every other node in the set.
• Only applies to directed graphs.
• Single case: single node.
Raymond Chan, UC Berkeley Fall 2017
STRONGLY CONNECTED COMPONENTS
• Find the strongly connected components.
(1, 6)
T A
T C (7, 20)
(2, 3)
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D F
I
T T
T
B T T (8, 19)
G H J F
(14, 15) (12, 17) 9, 18
Raymond Chan, UC Berkeley Fall 2017
STRONGLY CONNECTED COMPONENTS
• Find the strongly connected components.
• {A}, {B}, {E}, {C, F, J, D}, {G, I, H}
(1, 6)
T A
T C (7, 20)
(2, 3)
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D F
I
T T
T
B T T (8, 19)
G H J F
(14, 15) (12, 17) 9, 18
Raymond Chan, UC Berkeley Fall 2017
STRONGLY CONNECTED COMPONENTS
• Visualize it
• https://www.cs.usfca.edu/~galles/JavascriptVisual/
ConnectedComponent.html
(1, 6)
T A
T C (7, 20)
(2, 3)
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D F
I
T T
T
B T T (8, 19)
G H J F
(14, 15) (12, 17) 9, 18
Raymond Chan, UC Berkeley Fall 2017
TOPOLOGICAL SORT
• Source and Sink in a Directed Acyclic Graph (DAG)
• Source:
• Node has no incoming edges
• Highest post order number
• First nodes in topological ordering
• Sink
• No outgoing edges
• Lowest post oder number
• Last nodes in topological ordering
• Every DAG has at least one source and one sink
Raymond Chan, UC Berkeley Fall 2017
TOPOLOGICAL SORT
• Ordering of a directed graph’s nodes v1, v2, … vn such that for
every edge (vi, vj), i < j.
• Edge arrows go one direction.
• Application: scheduling jobs if order is required.
Raymond Chan, UC Berkeley Fall 2017
TOPOLOGICAL SORT
• Sort the Strongly Connected Components into a DAG
(1, 6)
T A
T C (7, 20)
(2, 3)
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D F
I
T T
T
B T T (8, 19)
G H J F
(14, 15) (12, 17) 9, 18
Raymond Chan, UC Berkeley Fall 2017
TOPOLOGICAL SORT
• Sort the Strongly Connected Components into a DAG
• {A}, {B}, {E}, {C, F, J, D}, {G, I, H}
(1, 6)
T A
T C (7, 20)
(2, 3)
B E C
(4, 5)
B
C C
C T
(13, 16) (10,11) D F
I
T T
T
B T T (8, 19)
G H J F
(14, 15) (12, 17) 9, 18
Raymond Chan, UC Berkeley Fall 2017
TOPOLOGICAL SORT
• {A}, {B}, {E}, {C, F, J, D}, {G, I, H}
B E C
D
I
G H J F
C, D, G, J G, H, I A B E
Raymond Chan, UC Berkeley Fall 2017
ALGORITHMS
SCC(G): Linearize (G, v):
Reverse edges of graph -> GR push all sources to v
DFS on GR while stack not empty:
Run DFS on G in reverse post v = pop from stack
order number from GR for all v’s neighbors w:
remove edge (v, w)
• Reverse graph prevents crossing if w becomes a sources:
SCCs push vertex w to stack
Add v to result
• Tarjan’s SCC algorithm
Sort by reverse post order number
Raymond Chan, UC Berkeley Fall 2017
BREADTH FIRST SEARCH
• Explore node u’s neighbors, then all vertices that are adjacent to
u’s neighbors, and so on.
• Can keep distance values to find how many edges a node is away
from the root.
iterative_BFF (G, v):
• Visits all vertices once. d[v] = 0
queue.enqueue(v)
while queue not empty:
• Uses all edges once. v = pop from queue
for all v’s neighbors w:
• O(|V| + |E|) if w not visited
mark w as visited:
d[w] = d[v] + 1
queue.enqueue(w)
Raymond Chan, UC Berkeley Fall 2017
DIJKSTRA’S SHORTEST PATH
• Find shortest path from s to all other vertices.
• Once we have computed the shortest path for a vertex, we don’t
revisit it again.
dijkstra (G, s):
d[v] = infinity
d[s] = 0
prev[s] = s
PQ.add(G.V, infinity)
PQ.add(s,0)
while PQ not empty:
u = PQ.DeleteMin()
for edge (u, v):
if d[v] > d[u] + w(u, v):
d[v] = d[u] + w[u, v]
prev[v] = u
PQ.DecreaseKey(v, d[v])
Raymond Chan, UC Berkeley Fall 2017
DIJKSTRA’S SHORTEST PATH
• Keep fringe vertices.
• Look at neighbors and update distance if there is a better path.
• When we pop off a node from Priority Queue, the distance is the
shortest path from s to this node so far.
dijkstra (G, s):
d[v] = infinity
d[s] = 0
prev[s] = s
PQ.add(G.V, infinity)
PQ.add(s,0)
while PQ not empty:
u = PQ.DeleteMin()
for edge (u, v):
if d[v] > d[u] + w(u, v):
d[v] = d[u] + w[u, v]
prev[v] = u
PQ.DecreaseKey(v, d[v])
Raymond Chan, UC Berkeley Fall 2017
DIJKSTRA’S SHORTEST PATH
Demo
dijkstra (G, s):
d[v] = infinity
d[s] = 0
prev[s] = s
PQ.add(G.V, infinity)
PQ.add(s,0)
while PQ not empty:
u = PQ.DeleteMin()
for edge (u, v):
if d[v] > d[u] + w(u, v):
d[v] = d[u] + w[u, v]
prev[v] = u
PQ.DecreaseKey(v, d[v])
O(|V|) * DeleteMin + O(|E|)*DecreaseKey
Typically use binary heap for priority queue
O(|V|+|E|) * log(|V|)
Raymond Chan, UC Berkeley Fall 2017
NEGATIVE EDGE WEIGHTS
A
1
0
2
S B
-3
3
C
dijkstra (G, s):
d[v] = infinity
d[s] = 0
prev[s] = s
PQ.add(G.V, infinity)
PQ.add(s,0)
while PQ not empty:
u = PQ.DeleteMin()
for edge (u, v):
if d[v] > d[u] + w(u, v):
d[v] = d[u] + w[u, v]
prev[v] = u
PQ.DecreaseKey(v, d[v])
Raymond Chan, UC Berkeley Fall 2017
NEGATIVE EDGE WEIGHTS
A
1
Start at S
0
Process A. d[a] = 1 2
Process B. d[b] = 2 S B
-3
Process C. d[c] = 3
3
Process A. d[a] = 1. C
Process B. d[b] = 2. d[a] = 1
dijkstra (G, s):
Process C. d[c] = 3. d[b] = 0 d[v] = infinity
New distance for B, but B not in PQ d[s] = 0
prev[s] = s
PQ.add(G.V, infinity)
PQ.add(s,0)
while PQ not empty:
u = PQ.DeleteMin()
for edge (u, v):
if d[v] > d[u] + w(u, v):
d[v] = d[u] + w[u, v]
prev[v] = u
PQ.DecreaseKey(v, d[v])
Raymond Chan, UC Berkeley Fall 2017
