Graphs Traversal and Topological Sort
David Weir (U of Sussex) Program Analysis Term 1, 2015 141 / 192
Traversing Graphs
Goal: visit each node in a graph in a systematic way
Non trivial because: Non-linear
Non-hierarchical
David Weir (U of Sussex) Program Analysis Term 1, 2015 142 / 192
Breadth-first Search
Exploring one layer at a time
Nodes are visited in order of increasing distance from s First visit nodes at distance 1 from s
Then visit nodes at distance 2 from s
Continue until all nodes have been visited.
How can this be achieved?
Put nodes that have been discovered but not yet explored in a
queue
Keep a record of which nodes have been discovered Construct a search tree that records search
David Weir (U of Sussex) Program Analysis Term 1, 2015 143 / 192
Breadth-first Search
BFS(G, s) :
let Q be a queue containing just the node s let discovered(s) = true
let discovered(v) = false for all v ∈ V − {s} letT =(V,{})
while Q is not empty
remove v from the front of Q
for each edge {v,w} in E where not discovered(w)
let discovered(w) = true addw tothebackofQ
add edge {v,w} to edges in T
David Weir (U of Sussex) Program Analysis Term 1, 2015 144 / 192
Illustration of BFS
v5 v2 v1
v8 v4 v7 v3
v6 Run BFS starting at v7
David Weir (U of Sussex) Program Analysis Term 1, 2015 145 / 192
Illustration of BFS
v5 v2 v1
v8 v4 v7 v3
v6 Initialize Q
David Weir (U of Sussex) Program Analysis Term 1, 2015 145 / 192
Illustration of BFS
v5 v2 v1
v8 v4 v7 v3
Q = [v7]
v6
Let discovered(v7) = true
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2 v1
v8 v4 v7 v3
Q = [v7]
v6 Remove v7 from front of Q
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2 v1
v8 v4 v7 v3
Q=[] Consider edge {v7,v4} since v4 not yet discovered
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 145 / 192
Illustration of BFS
v5 v2 v1
v8 v4 v7 v3
Q=[]
Let discovered(v4) = true, add {v7,v4} to T and v4 to Q
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 145 / 192
Illustration of BFS
v5 v2 v1
v8 v4 v7 v3
Q = [v4] Consider edge {v7,v5} since v5 not yet discovered
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 145 / 192
Illustration of BFS
v5 v2 v1
v8 v4 v7 v3
Q = [v4]
Let discovered(v5) = true, add {v7,v5} to T and v5 to Q
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v4,v5]
v6
No more edges from v7
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5
v2
v1
v8 v4
v7
v3
Q = [v4,v5]
v6 Remove v4 from front of Q
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v5] Consider edge {v4,v6} because v6 not yet discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v5]
Let discovered(v6) = true, add {v4,v6} to T and v6 to Q
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v5,v6] Don’t consider {v4,v7} because v7 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
v6
No more edges from v4
Q = [v5,v6]
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5
v2
v1
v8 v4
v7
v3
v6 Remove v5 from front of Q
Q = [v5,v6]
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v6] Consider edge {v5,v2} because v2 not yet discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v6]
Let discovered(v2) = true, add {v5,v2} to T and v2 to Q
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v6,v2] Consider {v5,v8} because v8 not yet discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v6,v2] Let discovered(v8) = true, add {v5,v8} to T and v8 to Q
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v6,v2,v8] Don’t consider {v5,v7} because v7 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v6,v2,v8]
v6
No more edges from v5
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5
v2
v1
v8 v4
v7
v3
Q = [v6,v2,v8]
v6 Remove v6 from front of Q
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v2,v8] Consider edge {v6,v3} because v3 not yet discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v2,v8] Let discovered(v3) = true, add {v6,v3} to T and v3 to Q
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v2,v8,v3] Don’t consider {v6,v4} because v4 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v2,v8,v3] Don’t consider {v6,v8} because v8 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
v6
No more edges from v6
Q = [v2,v8,v3]
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5
v2
v1
v8 v4
v7
v3
v6 Remove v2 from front of Q
Q = [v2,v8,v3]
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7 v3
Q = [v8,v3] Consider edge {v2,v1} because v1 not yet discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v8,v3] Let discovered(v1) = true, add {v2,v1} to T and v1 to Q
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v8,v3,v1] Don’t consider {v2,v3} because v3 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q = [v8,v3,v1] Don’t consider {v2,v5} because v5 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
v6
No more edges from v2
Q = [v8,v3,v1]
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5
v2
v1
v8 v4
v7
v3
Q = [v8,v3,v1]
v6 Remove v8 from front of Q
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7 v3
Q = [v3,v1] Don’t consider {v8,v5} because v5 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7 v3
Q = [v3,v1] Don’t consider {v8,v6} because v6 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
v6
No more edges from v8
Q = [v3,v1]
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5
v2
v1
v8 v4
v7
v3
Q = [v3,v1]
v6 Remove v3 from front of Q
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7 v3
Q = [v1] Don’t consider {v3,v1} because v1 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7 v3
Q = [v1] Don’t consider {v3,v2} because v2 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
v6
No more edges from v3
Q = [v1]
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5
v2
v1
v8 v4
v7
v3
Q = [v1]
v6 Remove v1 from front of Q
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7 v3
Q=[]
Don’t consider {v1,v2} because v2 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7 v3
Q=[]
Don’t consider {v1,v3} because v3 already discovered
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2
v1
v8 v4 v7
v3
Q=[]
v6
No more edges from v1
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2 v1
v8 v4 v7 v3
v6
Q is empty so traversal complete
David Weir (U of Sussex) Program Analysis
Term 1, 2015
145 / 192
Illustration of BFS
v5 v2 v1
v8 v4 v7 v3
v6
Here is the breadth first search tree for this run
David Weir (U of Sussex) Program Analysis Term 1, 2015 145 / 192
Illustration of BFS
v7
v4
v5
v6 v2 v8
v3 v1
Same tree, but arranged in more usual way
David Weir (U of Sussex) Program Analysis Term 1, 2015 145 / 192
Example for You
v2
Draw the breadth-first search tree Consider vertices in order of subscript Begin traversal at v1
v4
v1
v3
David Weir (U of Sussex)
Program Analysis Term 1, 2015 146 / 192
Example for You
v2
Draw the breadth-first search tree Consider vertices in order of subscript Begin traversal at v1
v1
v4
v2
v3
v1
v4
v3
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
146 / 192
Breadth-first Search
BFS(G, s) :
let Q be a queue containing just the node s let discovered(s) = true
let discovered(v) = false for all v ∈ V − {s} letT =(V,{})
while Q is not empty
remove v from the front of Q
for each edge {v,w} in E where not discovered(w)
let discovered(w) = true addw tothebackofQ
add edge {v,w} to edges in T
David Weir (U of Sussex) Program Analysis Term 1, 2015 147 / 192
Components of Graphs
v2
v5
v7
v1 v4 v3
Is this one or two graphs?
v6
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
148 / 192
Components of Graphs
v2
v5
v7
v1
v4
v6
v3
This is one of the components
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
148 / 192
Components of Graphs
v2
v5
v7
v1
v4
v6
v3
And this is the other components
David Weir (U of Sussex) Program Analysis
Term 1, 2015
148 / 192
Components of Graphs
v2
v5
v7
v1
v4
v6
v3
But remember, its all one graph
David Weir (U of Sussex) Program Analysis
Term 1, 2015
148 / 192
Components of Graphs (cont.)
Definition of a component of a graph G = (V,E)
A subset of the vertices in G and all associated edges from G
Must be connected
— path between any pair of vertices
Must be maximal
— cannot be enlarged and remain connected
David Weir (U of Sussex) Program Analysis Term 1, 2015 149 / 192
BFS and Multiple Component Graphs
v2
v5
v7
v1
v4
v6
v3
Question: Suppose BFS run on this graph starting at v3?
David Weir (U of Sussex) Program Analysis Term 1, 2015 150 / 192
Components of Graphs (cont.)
v2
v5
v7
v1
v4
v6
v3
Answer: BFS would find only nodes in the component containing v3
David Weir (U of Sussex) Program Analysis Term 1, 2015 151 / 192
Revised BFS Algorithm
BFS(G) :
let discovered(v) = false for all v ∈ V letT =(V,{})
foreachv ∈V
if not discovered(v) BFS(G,v)
David Weir (U of Sussex) Program Analysis Term 1, 2015 152 / 192
Revised BFS Algorithm (cont.)
BFS(G, s) :
let Q be a queue containing just the node s let discovered(s) = true
while Q is not empty
remove v from the front of Q
for each edge {v,w} in E where not discovered(w)
let discovered(w) = true addw tothebackofQ
add edge {v,w} to edges in T
David Weir (U of Sussex) Program Analysis Term 1, 2015 153 / 192
BFS Forest
T can consist of more than one tree
One tree in T for each component of G
T is actually Breadth-First Search Forest
NumberofedgesinT willben−k — where G contains k components
David Weir (U of Sussex) Program Analysis Term 1, 2015 154 / 192
Running Time of BFS
What is a good measure of progress?
Number of vertices whose edges have been considered Increases by 1 on each iteration of the while loop
This means that there n iterations of the loop
How much time spent on each iteration?
Depends on number of edges to be considered
David Weir (U of Sussex) Program Analysis Term 1, 2015 155 / 192
Running Time of BFS (cont.)
Number of steps within loop is Θ(max(1, outdegree(v ))) outdegree(v) is number of edges from v to some other vertex w We know that in total there are m edges to consider
Total across all iterations of loop:
max(1, outdegree(v )) = Θ(n + m) v∈V
David Weir (U of Sussex)
Program Analysis Term 1, 2015 156 / 192
Depth-first Search
A different strategy for systematic exploration of a graph.
Uses a stack to hold discovered nodes
Record nodes as explored once popped from stack
Only explore nodes taken from stack that haven’t already been explored
Record edges in search tree by remembering the latest parent of each node
Parent of a node can change up to the point it is explored
David Weir (U of Sussex) Program Analysis Term 1, 2015 157 / 192
Depth-first Search
DFS(G, s) :
let S be a stack containing just the node s let explored(v) = false for all v ∈ V
while S is not empty
pop v from the top of S if not explored(v) then
for each edge {v,w} in E where not explored(w) push w onto S
let parent(w) = v
let explored(v) = true
David Weir (U of Sussex) Program Analysis Term 1, 2015 158 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
v6 Run DFS starting at v7
David Weir (U of Sussex) Program Analysis Term 1, 2015 159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
v6 Initialize S
David Weir (U of Sussex) Program Analysis Term 1, 2015 159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v7]
v6 Pop v7 from top of S
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S=[]
v6
v7 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S=[] Consider edge {v7,v4} since v4 not yet explored
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S=[] Push v4 onto S and let parent(v4) = v7
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v4] Consider edge {v7,v5} since v5 not yet explored
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v4] Push v5 onto S and let parent(v5) = v7
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v5,v4]
v6
No more edges from v7
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v5,v4]
v6
Let explored(v7) = true
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
v6 Pop v5 from top of S
S = [v5,v4]
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v4]
v6
v5 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v4] Consider edge {v5,v2} since v2 not yet explored
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v4] Push v2 onto S and let parent(v2) = v5
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v2,v4] Consider {v5,v8} since v8 not yet explored
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v2,v4]
v6
Push v8 onto S and let parent(v8) = v5
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v8,v2,v4] Don’t consider {v5,v7} because v7 already explored
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v8,v2,v4]
v6
No more edges from v5
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v8,v2,v4]
v6
Let explored(v5) = true
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v8,v2,v4]
v6 Pop v8 from top of S
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
S = [v2,v4]
v6
v8 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4] Don’t consider {v8,v5} because v5 already explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4] Consider edge {v8,v6} since v6 not yet explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4]
v6
Push v6 onto S and let parent(v6) = v8
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v6,v2,v4]
v6
No more edges from v8
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v6,v2,v4]
v6
Let explored(v8) = true
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v6,v2,v4]
v6 Pop v6 from top of S
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4]
v6
v6 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4] Consider edge {v6,v4} since v4 not yet explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4]
v6
Push v4 onto S and let parent(v4) = v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v4,v2,v4] Don’t consider {v6,v8} because v8 already explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v4,v2,v4]
v6
No more edges from v6
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v4,v2,v4]
v6
Let explored(v6) = true
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v4,v2,v4]
v6 Pop v4 from top of S
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4]
v6
v4 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4] Don’t consider {v4,v6} because v6 already explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4] Don’t consider {v4,v7} because v7 already explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4]
v6
No more edges from v4
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4]
v6
Let explored(v4) = true
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v2,v4]
v6 Pop v2 from top of S
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v4]
v6
v2 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v4] Consider edge {v2,v1} since v1 not yet explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v4] Push v1 onto S and let parent(v1) = v2
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v4] Consider edge {v2,v3} since v3 not yet explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
v6
Push v3 onto S and let parent(v3) = v2
S = [v1,v4]
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v3,v1,v4] Don’t consider {v2,v5} because v5 already explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v3,v1,v4]
v6
No more edges from v2
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v3,v1,v4]
v6
Let explored(v2) = true
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v3,v1,v4]
v6 Pop v3 from top of S
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v4]
v6
v3 not yet explored so let’s explore it
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v4] Consider edge {v3,v1} since v1 not yet explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
v6
Push v1 onto S and let parent(v1) = v3
S = [v1,v4]
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v1,v4] Don’t consider {v3,v2} because v2 already explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v1,v4]
v6
No more edges from v3
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v1,v4]
v6
Let explored(v3) = true
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
v6 Pop v1 from top of S
S = [v1,v1,v4]
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
v6
v1 not yet explored so let’s explore it
S = [v1,v4]
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v4] Don’t consider {v1,v2} because v2 already explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v4] Don’t consider {v1,v3} because v3 already explored
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v4]
v6
No more edges from v1
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v4]
v6
Let explored(v1) = true
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v1,v4]
v6 Pop v1 from top of S
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v4] v1 already explored so no need to consider it
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S = [v4]
v6 Pop v4 from top of S
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4 v7
v3
S=[] v4 already explored so no need to consider it
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2
v1
v8 v4
v7
v3
S=[]
v6
S is empty so search is complete
David Weir (U of Sussex) Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v5 v2 v1
v8 v4 v7 v3
v6
Obtain tree by reversing directionality of all parent edges
David Weir (U of Sussex) Program Analysis Term 1, 2015 159 / 192
Illustration of DFS
v5
v2 v1
v8 v4
v7
v3
v6 Re-position nodes for clarity
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
159 / 192
Illustration of DFS
v7 v5
v8
v6
v4
David Weir (U of Sussex)
v2 v3 v1
Program Analysis
Term 1, 2015
159 / 192
Example for You
v2
Draw the depth-first search tree Consider vertices in order of subscript Begin traversal at v1
v4
v1
v3
David Weir (U of Sussex)
Program Analysis Term 1, 2015 160 / 192
Example for You
v2
Draw the depth-first search tree Consider vertices in order of subscript Begin traversal at v1
v1
v4
v2
v3
v1
v4
v3
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
160 / 192
DFS Algorithm
DFS(G, s) :
let S be a stack containing just the node s let explored(v) = false for all v ∈ V
while S is not empty
pop v from the top of S if not explored(v) then
for each edge {v,w} in E where not explored(w) push w onto S
let parent(w) = v
let explored(v) = true
David Weir (U of Sussex) Program Analysis Term 1, 2015 161 / 192
Running Time of DFS
What is a good measure of progress?
Number of vertices whose edges have been considered not adequate
For some iterations this will not increase
— when explored vertex removed from stack
Number of edge destinations considered always increases Each directed edge is directed into the destination vertex Increases by at least 1 on each iteration of the while loop
David Weir (U of Sussex) Program Analysis Term 1, 2015 162 / 192
Running Time of DFS (cont.)
This means that there O(m) iterations of the loop
How much time spent on each iteration?
Depends on number of edges to be considered
Number of steps within loop is Θ(max(1, outdegree(v ))) We know that in total there are m edges to consider Total across all iterations of loop:
max(1, outdegree(v )) = Θ(n + m) v∈V
David Weir (U of Sussex)
Program Analysis Term 1, 2015 163 / 192
Topological Sorting
David Weir (U of Sussex) Program Analysis Term 1, 2015 164 / 192
Working with Dependencies
EBA
HDGC
F
Directed Graphs often used to encode dependencies
David Weir (U of Sussex) Program Analysis Term 1, 2015 165 / 192
Working with Dependencies
EBA
HDGC
F
Nodes correspond to tasks
David Weir (U of Sussex) Program Analysis Term 1, 2015 165 / 192
Working with Dependencies
EBA
HDGC
F
Edges encode constraints on order in which tasks can be scheduled
David Weir (U of Sussex) Program Analysis Term 1, 2015 165 / 192
Working with Dependencies
E B A
H D G C
F
Task E must be completed before task G is started
David Weir (U of Sussex) Program Analysis Term 1, 2015 165 / 192
Working with Dependencies
EBA
HDGC
F
Cycles are undesirable
David Weir (U of Sussex) Program Analysis Term 1, 2015 165 / 192
Working with Dependencies
EBA
HDGC
F
No scheduling would be possible that satisfies constraints
David Weir (U of Sussex) Program Analysis Term 1, 2015 165 / 192
Topological Sorting of DAGs
Topological Sorting Problem:
Given a DAG, G = (V,E), find a topological sort of G.
Topological Ordering:
A topological ordering of a DAG, G = (V , E ), is a permutation
of the vertices in V that is compatible with each edge in E A permutation (v1, . . . , vn) is compatible with edge (v, w) if
v=vi, w=vj and i