Starting from:
$25
Homework 3 Topological sort algorithm
1 Manually run the topological sort algorithm
Run the DFS-based topological sort algorithm taught in class (not the algorithm given in the textbook, which removes an in-degree zero node each time) using the example given in Figure 3.8 part
(a) (page 103) of the textbook (for your convenience, also provided here; ignore the shades of the
nodes). When performing DFS, when there are multiple choices, use the alphabetical order. For
example, you should begin with v1 (the alphabetically smallest). From v1, you should first visit v4.
Note: you should show the DFS timestamps and the order of the output nodes.
2 Semiconnected graph
A directed graph G = (V; E) is semiconnected if, for all pairs of vertices u; v 2 V , there is a path
from u to v or from v to u. That is, different from the strongly connected components where you
can go from u to v and then back, here you only need to either go from u to v or from v to u but
don’t have to get back. Give an efficient algorithm to determine whether or not G is semiconnected.
Prove that your algorithm is correct and then analyze its running time. Note: to get full credit, your
algorithm needs to run in O(jV j + jEj) time.
3 A distance problem
Do problem 3.9 on page 110. For your convenience, here is the problem description.
Suppose a n-node undirected (and unweighted) graph G = (V; E) contains two nodes s and t
such that the distance between s and t is strictly greater than n2 . Show that there must exist some
node v (different from s and t) such that deleting v (and all edges incident to v) from G will destroy
all paths between s and t. In other words, the new graph by deleting v from G contains no path
between s and t. Given an algorithm with running time O(m + n) to find such v (m is the number
of edges).
Hint: since this problem concerns distance in a unweighted graph, this leads naturally to BFS...
10% extra credits: paths on a tree
This problem is for students who are looking for some challenge.
You are given T, a undirected tree (i.e. connected and acyclic graph). The objective is finding
two nodes u; v of T s.t. the distance (i.e. the number of edges along the unique path between u and
1
v) is the maximum. Na¨ıvely, you can try all possible pairs of nodes but this is very slow. Here is a
very simple algorithm for this problem that runs in linear time.
You start from any node s as the source and perform BFS. Let u be the node with the largest
distance from s (i.e. at the largest level). Then you perform a second BFS: this time you use u as
the source. Let v be the node with the largest distance from u.
Now, prove this claim: the distance between u and v is the largest possible distance between any
two nodes on the tree.
Run the DFS-based topological sort algorithm taught in class (not the algorithm given in the textbook, which removes an in-degree zero node each time) using the example given in Figure 3.8 part
(a) (page 103) of the textbook (for your convenience, also provided here; ignore the shades of the
nodes). When performing DFS, when there are multiple choices, use the alphabetical order. For
example, you should begin with v1 (the alphabetically smallest). From v1, you should first visit v4.
Note: you should show the DFS timestamps and the order of the output nodes.
2 Semiconnected graph
A directed graph G = (V; E) is semiconnected if, for all pairs of vertices u; v 2 V , there is a path
from u to v or from v to u. That is, different from the strongly connected components where you
can go from u to v and then back, here you only need to either go from u to v or from v to u but
don’t have to get back. Give an efficient algorithm to determine whether or not G is semiconnected.
Prove that your algorithm is correct and then analyze its running time. Note: to get full credit, your
algorithm needs to run in O(jV j + jEj) time.
3 A distance problem
Do problem 3.9 on page 110. For your convenience, here is the problem description.
Suppose a n-node undirected (and unweighted) graph G = (V; E) contains two nodes s and t
such that the distance between s and t is strictly greater than n2 . Show that there must exist some
node v (different from s and t) such that deleting v (and all edges incident to v) from G will destroy
all paths between s and t. In other words, the new graph by deleting v from G contains no path
between s and t. Given an algorithm with running time O(m + n) to find such v (m is the number
of edges).
Hint: since this problem concerns distance in a unweighted graph, this leads naturally to BFS...
10% extra credits: paths on a tree
This problem is for students who are looking for some challenge.
You are given T, a undirected tree (i.e. connected and acyclic graph). The objective is finding
two nodes u; v of T s.t. the distance (i.e. the number of edges along the unique path between u and
1
v) is the maximum. Na¨ıvely, you can try all possible pairs of nodes but this is very slow. Here is a
very simple algorithm for this problem that runs in linear time.
You start from any node s as the source and perform BFS. Let u be the node with the largest
distance from s (i.e. at the largest level). Then you perform a second BFS: this time you use u as
the source. Let v be the node with the largest distance from u.
Now, prove this claim: the distance between u and v is the largest possible distance between any
two nodes on the tree.
1 file (315.3KB)
