Homework Seven
Problem Set 7 Solutions
Problem 1 The BFS (Breadth-First Search) algorithm given in the lecture notes uses
multiple lists. Modify the algorithm so that it uses only one queue to replace multiple
lists.
Solution:
The main algorithm remains the same. The breadth-first search algorithm starting with
a vertex is modified as follows:
Algorithm BFS(G, s)
{
Create an empty queue L;
L.enqueue(s);
setLabel(s, VISITED);
while ( ! L.isEmpty() )
{
v = L.dequeue();
for all e ∈ G.incidentEdges(v)
if ( getLabel(e) = UNEXPLORED )
{ w = opposite(v,e);
if ( getLabel(w) = UNEXPLORED )
{
setLabel(e, DISCOVERY);
setLabel(w, VISITED);
L.enqueue(w);
}
else
setLabel(e, CROSS);
}
}
}
Problem 2 Describe, in pseudo code, an O(n+m)-time algorithm for computing all the
connected components of an undirected graph G with n vertices and m edges.
Solution:
Algorithm connectedComponents(G)
Input: An undirected graph G
Output: All the connected components of G
{
for each vertex v in G do
visited(v)=0;
i=0;
for each vertex v in G do
{
if ( visited(v)=0 )
{
create a new list Li ; // Each Li stores a connected component
perform the depth-first search or the width-first search starting with v;
for each vertex u visited in the search do
{ add u to Li;
visited(u)=1;
}
i=i+1;
}
}
}
Problem 3 Given an undirected graph G and a vertex vi, describe an algorithm for
finding the shortest paths from vi to all other vertices. The shortest path from a vertex
vs to a vertex vt is a path from a vertex vs to a vertex vt with the minimum number of
edges. What is the running time of your algorithm?
Solution: For each vertex v we introduce a list Q(v) to store the shortest path from vi
to v. We can modify the breadth–first search algorithm given in Q1 to compute the
shortest path from vi to v as follows:
Algorithm BFS(G, vi)
{
for each vertex v of G do
Create an empty list Q(v);
Create an empty queue L;
L.enqueue(vi);
setLabel(vi, VISITED);
while ( ! L.isEmpty() )
{
v = L.dequeue();
for all e ∈ G.incidentEdges(v)
if ( getLabel(e) = UNEXPLORED )
{ w = opposite(v,e);
if ( getLabel(w) = UNEXPLORED )
{
setLabel(e, DISCOVERY);
setLabel(w, VISITED);
L.enqueue(w);
Q(w)=Q(v)+{v,w};
}
else
setLabel(e, CROSS);
}
}
}
The first for loop takes O(n) time, and “Q(w)=Q(s)+{v,w}” takes O(1) time. Hence,
the running time of the algorithm is O(m+n).
Problem 4 A connected undirected graph is said to be biconnected if it contains no
vertex whose removal would divide G into two or more connected components. Give
an O(n+m)-time algorithm for adding at most n edges to a connected graph G, with
n>3 vertices and m>n-1 edges, to guarantee that G is biconnected.
Solution: Number the vertices 0 to n − 1. Now add an edge from vertex i to vertex (i
+ 1) mod n, if that edge does not already exist. This connects all the vertices in a
cycle, which is itself biconnected.
Time complexity analysis:
We can use an adjacency list to represent G.
1. It takes O(n) time to number all the n vertices.
2. Adding an edge from vertex i to vertex (i+1) mod n takes O(degree(i)) time,
where degree(i) is the degree of vertex i. Since the total degree of all the
vertices is 2m, where m is the number of edges in G. Therefore, the time
complexity of adding all the edges is O(2m)=O(m).
As a result, the time complexity of this algorithm is O(n)+O(m)=O(n+m).
Problem 5 An n-vertex directed acyclic graph G is compact if there is some way of
numbering the vertices of G with the integers from 0 to n-1 such that G contains the
edge (i, j) if and only if i