| Graph Traversals and Minimum Cost Paths |
About This Exercise
This exercise is based on the information about graph algorithms introduced in lectures on November 24, November 26, November 28, and December 1.
The objectives of this exercise are
- to ensure that you understand the “Depth-First Search,” “Breadth-First Search,” and “Minimum Cost Path” algorithms well enough to be able to trace their execution by hand on small examples;
- to make you familiar with issues that must be considered when these algorithms are implemented as Java programs; and
- to ensure that you understand properties of these algorithms (related to their correctness and efficiency) well enough to be able to modify these algorithms to solve related problems.
Please read through and try to solve the problems on this exercise before attending the tutorials during the last week of classes. The problems on this exercise will be discussed during these tutorials.
Problems
-
Trace the execution of DFS(G, 0) on each of the following graphs G.
-
-
Trace the execution of BFS(G, 0) on each of the graphs given in the previous question.
-
Trace the execution of MCP(G, 0) on each of the following weighted graphs.
-
-
Implement each of the DFS, BFS, and MCP algorithms as Java programs.
Note that you will have to examine the information about “data structures” included in the notes on “Minimum Cost Paths,” and you will need to design your program carefully, if the worst-case running time of your program is to be as small as the lecture notes suggest!
If you do not have time to solve this problem then, at least, you should study the online notes and try to describe those things that you would need to do in order to make sure that your program is efficient.
-
As discussed in lectures there will generally be more than one depth-first search tree corresponding to a given undirected graph G and vertex s. Why is that the case?
Is this true for breadth-first search trees and minimum-cost paths, as well? Why (or why not)?
On the other hand, some of the other information that some of these algorithms compute is unique. Which is information is this, and why is it unique?
-
Finally, modify the MCP algorithm so that it can be used to find the minimum-cost paths from a given vertex s to all other (reachable) vertices, in a weighted directed graph.
Describe any and all modifications that must be made to the analysis of the algorithm, in order to prove that your algorithm for directed graphs is correct and efficient.
Then, if time permits, trace the execution of your program on the following weighted directed graph, using 0 as the start vertex.
|
This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F08/tutorials/tutorial15.html |