Homework 10 is a programming assignment
based on Homework 9
Due date: Midnight, April 29, 2007.
-
Write a program that finds the components of a graph.
-
Here are two sample input files: a small one
and
a big one. The first line of each file gives
the number of vertices, n.
Each other line gives one edge, written as a pair of numbers in the range
1 to n.
-
Here are the output files of my program:
output for the small file and
output for the big file.
Each line lists the vertices of one component. The components may be
listed in any order, and the vertices of a component
may be listed in any order.
-
You are required to use the disjoint set data structure described in
Homework 9, and the union-find algorithm described there.
You must use path compression in your program.
-
Estimated number of lines in your code (not counting comments): 80.
-
Estimated programming time (together with debugging): 30 minutes.
-
Clues.
-
Write a program that uses Dijkstra's algorithm to solve the single pair
minimum weight path problem in a directed graph with no negative weight
edges.
-
Here are two sample input files: a tiny one
and
a big one. The first line of each file gives
the number of vertices, n.
Each other line gives one weighted edge,
written as a pair of numbers in the range
1 to n, followed by a non-negative weight. For example, the line 1 2 4
means that there is an edge from vertex 1 to vertex 2 of weight 4.
-
The output of your program should be a path of minimum weight from 1 to n.
For the tiny file, my output is:
1 3 2 5: Weight = 5
For the big file, my output is:
1 8 16 21 30 40 43 51 50 59 64 69 79 89 99 100: Weight = 44
-
If there is no path from 1 to n, your program must output a message stating
that.
The output of my program with input
this file with no path from 1 to n is:
There is no path from 1 to 4
-
Estimated number of lines in your code (not counting comments): 180.
-
Estimated programming time (together with debugging): 125 minutes.
-
Clues.