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 Term 1, 2015
3. What happens if the topological sort algorithm is given a cyclic graph as input?
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.
EBA
HDGC
F
5. Adapt the DFS algorithm so that it outputs a topological sort.
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.