Homework 8: Graphs

A. Union-Find

Consider a partition of a contiguous set of integers 1 to V. Initially, the partition consists of a set of V sets, each containing a single integer. We want to support the operations of finding which partition any given integer belongs to and merging two partitions into one ("union"). We identify partitions by choosing one representative member for each. Fill in the file UnionFind.java to implement the find and union operations. Do not use any data structures from the Java library (the utilities in the Arrays class are OK), and do not define any classes other than UnionFind. Just use arrays and primitive values.

B. Minimal Spanning Trees

Consider an undirected graph whose vertices are numbered 1 to V and whose edges are labeled with non-negative integer weights. Given such a graph, we would like to find a minimal spanning tree in the form of a list of edges from the graph that are included in the tree. To give you some exercise in true data-structure hacking, for this problem we'll represent the graph using only arrays and ints. Fill in the skeleton file MST.java to use Kruskal's Algorithm to create this tree. Assume that we will be giving you large graphs to operate on. As for part A, do not use any data structures from the Java library.

The class MSTTest runs some JUnit tests on your MST algorithm. If a test case fails, you can use the main program of Utils.java to see exactly what graph was fed to it, if desired. The test cases will print out parameters to the main program that generate the graph in the test case. Executing

    java Utils V MINEDGES MAXWEIGHT RANDOM-SEED true

prints the corresponding test case and the MST your program produces from it,. (The arguments V through RANDOM-SEED tell Utils.randomConnectedGraph what graph to generate). This is less helpful on really large test cases, of course.