Problem One

Write a C++ program that uses the approach outlined in problem 20.4-5 to do topological sorting. Demonstrate that your program works correctly by giving it the DAG in Figure 20.7 as its input.

How to do this

To help you get started, here is my code for the pointer version of BFS. You can use the code I provided for reading a graph from a file to make it easier to construct your graph. You can remove the code to do BFS and the code to print paths - you won't need either of these for the program you are going to write.

The main challenge you are going to face is making an algorithm that does the topological sorting in time O(V+E). To illustrate how tricky this can be, here is a naive implementation of the algorithm.

1. Compute the in-degree of each vertex in the graph. Doing this will require you to examine each edge in the graph, and will take time at least O(E).
2. Run the algorithm described in 20.4-5. On each round of the algorithm you will have to find a vertex with in-degree 0 and then remove it. Removing the vertex will require you to process each of its out-going edges, which will add a further O(E) over the entire algorithm.
3. The naive way to find a vertex of in-degree 0 on each round is to simply do a linear search through the list of remaining vertices. If you do this, just searching for the vertices to remove can add total time O(V²), which exceeds your runtime budget for the algorithm.

To beat the run time of O(V² + E) you will need to replace the idea in step 3 above with something smarter.

Problem Two

Write a C++ program that implements an efficient solution to the following problem:

Suppose you are given a set of edges that form a spanning tree for a graph. Suppose now someone gives you a new edge that was not in the original list of edges. Construct an efficient algorithm to determine whether or not it is possible to remove an existing edge from the spanning tree and replace it with the new one to make a new spanning tree that has a lower total edge weight than the original.

One very obvious way to solve this problem is to take the original set of edges in the spanning tree, add the new edge to the list, and then just run Kruskal's algorithm on that set of edges. For the purposes of this problem that is not efficient enough: find a more efficient way to solve the problem.

Your program should start by reading a list of vertices and weighted edges from a text file. Put just enough edges into the file to make a spanning tree. Then, have your program prompt the user to enter a new edge and a weight for that edge. Your program will then determine whether or not it is possible to make a cheaper spanning tree with the new edge: if it is possible your program should print the old edge you should discard to make the cheaper tree.