Program Analysis Term 1, 2015 Problem Sheet 4
1. We are interested in the case where DFS is applied to directed graphs rather than undirected graphs. We need to make a call to DFS(G, v) for each vertex v that is not yet explored as follows.
Here is the algorithm.
DFS(G) :
explored(v) ← false for all v ∈ V for each v ∈ V
if not explored(v) DFS(G, v)
DFS(G, s) :
let S be a stack containing just the node s while S is not empty
pop v from the top of S if not explored(v) then
for each edge (v, w) in E if not explored(w)
push w onto S explored(v) ← true
Consider the application of this algorithm to the following graph, and convince yourself that no matter what order the vertices are considered, the algorithm will function correctly.
EBA
HDGC
F
2. This question involves adapting the above depth-first algorithm to find the in- degree of each vertex in a directed graph. The in-degree of a vertex v in a directed graph G = (V,E) is defined as the number of w ∈ V such that (w,v) ∈ E.
Program Analysis Model Answer:
ComputeInDegrees(G) :
explored(v) ← false for all v ∈ V indegree(v) ← 0 for all v ∈ V for each v ∈ V
if not explored(v) ComputeInDegrees(G, v)
ComputeInDegree(G, s) :
let S be a stack containing just the node s while S is not empty
pop v from the top of S if not explored(v) then
for each edge (v, w) in E if not explored(w)
push w onto S
indegree(w) ← indegree(w) + 1
Term 1, 2015
explored(v) ← true
3. What happens if the topological sort algorithm is given a cyclic graph as input?
Model Answer: Any vertex that is part of a cycle will never be pushed onto the stack since it will not have an indegree of zero.
4. This question concerns how to use the following variant of the above depth-first search algorithm to find the topological sort of a directed acyclic graph.
DFS(G) :
explored(v) ← false for all v ∈ V for each v ∈ V
if not explored(v) DFS(G, v)
DFS(G, v) :
for each edge (v, w) in E if not explored(w)
DFS(G, w) explored(v) ← true
First run this depth-first search algorithm on the following graph, and as you do this, try to figure out how to use the algorithm as a way of establishing a topological sort of the graph. Explain your answer.
Program Analysis Term 1, 2015 EBA
HDGC
F
Model Answer: The solution is that the order in which vertices are designated as “explored” is the reverse of a topological sort of the graph. If a vertex w ex- ists that can be reached from vertex v through depth-first search then w must be scheduled after v. DFS will visit, and complete exploration of, all vertices reach- able from a vertex v before designating v as “explored”. Hence, all vertices that should be scheduled after v will be explored before v.
5. Adapt the DFS algorithm so that it outputs a topological sort.
Model Answer:
DFS(G) :
explored(v) ← false for all v ∈ V i ← |V |
for each v ∈ V
if not explored(v) DFS(G, v)
DFS(G, v) :
for each edge (v, w) in E if not explored(w)
DFS(G, w) explored(v) ← true
schedule(v) ← i i←i−1
6. What happens if this new DFS-based topological sort algorithm is given a graph with a cycle as input? Discuss how this should be dealt with.
Program Analysis Term 1, 2015
Model Answer: It will not terminate since it will recurse infintely. It is therefore necessary to check that the graph is not cyclic before running the algorithm.