Homework Seven
Problem Set 7
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.
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.
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?
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.
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