Lab 13 | CS 61B Fall 2021 Main Course Info Staff Beacon Resources Piazza Navigation Navigation A. Intro B. Union Find Quick Union Find SamePartition Union Path Compression Exercise: Implementing UnionFind C. Minimum Spanning Trees Kruskal's Algorithm Exercise: Implementing Kruskal's Algorithm Hints Testing D. Submission Lab 13: Union Find & MSTs Due Date: Friday 11/19 11:59PM. Navigation A. Intro B. Union Find C. Minimum Spanning Trees D. Submission A. Intro In this lab, we will be exploring the union find data structure (also called disjoint sets), and you will be implementing your own weighted quick union data structure. We will then explore minimum spanning trees (MSTs) of graphs, and you will be implementing Kruskal's Algorithm to find the MST of a graph. Union Find and MSTs are covered in lecture 34, so you can look at the lecture for a quick refresher, or the lab spec will also reintroduce the topics. As always, you can get the skeleton of this lab with: git fetch shared
git merge shared/lab13 -m "get lab13 skeleton" B. Union Find Suppose we have a collection of companies that have gone under mergers or acquisitions. We want to develop a data structure that allows us to determine if any two companies are in the same conglomerate. For example, if company X and company Y were originally independent but Y acquired X, we want to be able to represent this new connection in our data structure. How would we do this? One way we can do this is by using the union find, or disjoint, sets data structure. The disjoint sets data structure represents a collection of sets that are disjoint, meaning that any item in this data structure is found in no more than one set. When discussing this data structure, we often limit ourselves to two operations, union and find, which is also why this data structure is also called the union-find data structure. We will be using these two names interchangeably. The union operation will combine two sets into one set. The find operation will take in an item, and tell us which set that item belongs to by returning the representative item of its set. With this data structure, we will be able to keep track of the acquisitions and mergers that occur! Let's run through an example of how we can represent our problem using disjoint sets with the following companies: To start off, each company is in its own set with only itself and a call to find(X) will return $X$ (and similarly for all the other companies). If $Y$ acquired $X$, we will make a call to union(X, Y) to represent that the two companies should now be linked. In this call to union, one of the companies is picked to be the representative of this set. If the representative is picked to be $Y$, a call to find(X) will return $Y$, and a call to find(Y) will also return $Y$. If the representative is picked to be $X$, a call to find(X) will return $X$, and a call to find(Y) will also return $X$. Quick Union For the rest of the lab, we will work with positive integers as the items in our union find. We will represent each set as its own tree. Each tree will have the following qualities: The nodes in the tree will be the items in the same set. Each node only needs a reference to its parent rather than a direct reference to the representative of the set. The top of each tree (we refer to this top as the "root" of the tree) will be the representative its set. Example: We have a union find data structure for the numbers 1 to 7. Here, there are three distinct sets: Set #1 with items 1, 2, 4, and 7. The root of this set is 1. Set #2 with item 3. The root of this set is 3. Set #3 with items 5 and 6. The root of this set is 5. In code, we can conveniently represent these trees as an array parents. The $i$th item in parents contains the parent of that item. For example, 7's parent is 4, so the value at index 7 in parents is 4. An item that doesn't have a parent (i.e. an item that is the root of its tree) has itself as its parent. Find We want to define an operation find(u) that takes in an item and returns the representative of the set it belongs to. In this case, the representative of the set is the root of the tree that u belongs to. In the example above, find(1), find(4), and find(7) should all return 1 because 1 is the root of the tree they belong to. find(3) should return 3, and find(6) should return 5. SamePartition We also want to define an operation samePartition(u, v) that takes in two items and returns whether or not they are in the same set. In the example above, samePartition(2, 4) should return true, while samePartition(3, 6) should return false. To see if two items are in the same set, we see if the representatives of the sets that each item belongs to are the same by checking if the roots of the trees each item belongs to are the same. Union Lastly, we want to define the opreation union(u, v) that will take the two items and union the two sets that the two items belong to. It will do nothing if the two items are already in the same set. In the example above, if we called union(4, 5) we should end up with 2 sets: set #1 with items 1, 2, 4, 5, 6, and 7, and set #2 with item 3. To do this, we take the roots of the trees of the two items, and make one root the child of the other root. Below are two valid results of calling union(4, 5) (changes highlighted in red): Option 1 Option 2 Looking at the two results, it seems like option 1 is superior to option 2 since it leads to a bushier tree. This leads us to the weighted quick union data structure. In a regular quick union, both option 1 and option 2 are valid results. In a weighted quick union, when unioning, you should always put the root of the tree with more nodes as the parent of the root of the tree with fewer nodes. (If the two trees have the same size, break ties arbitrarily.) In the example above, the result of unioning should be option 1. To achieve this, for each item that is the root of its tree, we keep track of the size of its tree in an array sizes. Here is an example: 1, 3, and 5 are the roots of their trees so their corresponding values in sizes are 4, 1, and 2 respectively. For other non-root items, the asterisks signify that that the sizes array may have a value there, but we don't care about what they are. After calling union(4, 5), we get the following (changes highlighted in red): Note that the size associated with item 1 is now 6. The size associated with 5 may still be 2, but it is no longer relevant. To recap, the algorithm for union(u, v): Find the root of u and root of v. If they are the same, you are done. Find the sizes of the trees of each root. Make the root with the larger size the parent of the root with the smaller size. If there is a tie in size, we pick the parent arbitrarily. Update the size of the root with the larger size that became the parent. Path Compression Even though we have made a speedup by using a weighted quick union data structure, there is still yet another optimization that we can do. What would happen if we had a tall tree and called find repeatedly on the deepest leaf? Each time, we would have to traverse the tree from the leaf to the root. A clever optimization is to move the leaf up the tree so it becomes a direct child of the root. That way, the next time you call find on that leaf, it will run much more quickly. Remember that we do not care if a node has a certain parent; we care more about general connectivity (and therefore only what the root is), which is why we can move the leaf up to be a child of the root without losing important information about our disjoint sets structure. An even more clever idea is that we could do the same thing to every node that is on the path from the leaf to the root, connecting each node to the root as we traverse up the tree. This optimization is called path compression. Once you find an item, path compression will make finding it (and all the nodes on the path to the root) in the future faster. Example: We have the following tree with 1 as the root. We call find(7): When we call find(7), we find that 1 is its root so we set 7's parent to be 1. Next, we call find(8): When we call find(8), we find that 1 is its root, so we set 8's parent to be 1. However, along the way, we also find that 3's root is also 1, so we set 3's parent to be 1. (We also find along the way that 5's root is 1, but 5's parent is already 1 so there is no change.) Since the find operation is used when calling union, if path compression is implemented in find, union will also be optimized. Hint: We recommend implementing find recursively, which would then only require a 1-2 line change for path compression. Exercise: Implementing UnionFind Fill out the FIXMEs UnionFind.java. You should be implementing a weighted quick union with path compression. The path compression is optional and ungraded. Suggested order of completion: Add instance attributes and fill out the constructor. Complete find without path compression. Complete union. Be sure to use find and not repeat code, and make sure you are joining trees based on their sizes. All tests in UnionFindTest.java should now pass. (Optional) Add path compression to find. Depending on your implementation, this should be a 1-2 line change! All tests in UnionFindTest.java should still pass. C. Minimum Spanning Trees We assume you already know what a MST is. If not, review lecture 34. Kruskal's Algorithm Kruskal's algorithm is an algorithm that can calculate the MST of a weighted graph $G$. It goes as follows: Create a new graph $T$ with the same vertices as $G$, but no edges (yet). Make a list of all the edges in $G$. Sort the edges from smallest weight to largest weight. Iterate through the edges in sorted order. For each edge $(u, w)$, if $u$ and $w$ are not already connected by a path in $T$, add $(u, w)$ to $T$. This is the same as saying: for each edge $(u, w)$, if adding $(u, w)$ to $T$ would not create a cycle in $T$, add $(u, w)$ to $T$. The new graph $T$ with the same vertices as $G$ and a subset of the edges from $G$ is the MST of $G$. If you would like to see a visual demonstration of Kruskal's algorithm, see the Kruskal's Demo slides. Note that this demo has vertices starting at 0 but in this lab vertices start at 1. (It shouldn't make a difference). The trickier part of Kruskal's is determining if two vertices $u$ and $w$ are already connected. We can revisit the data structure that specializes in determining if connections exist, the union find data structure! Each of the vertices of $G$ will be an item in our data structure. Whenever we add an edge $(u, w)$ to $T$, we can union the sets that $u$ and $w$ belong to. To check if there is already a path connecting $u$ and $w$, we see if $u$ and $w$ are in the same set. Exercise: Implementing Kruskal's Algorithm 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 that includes edges from the input graph. For this problem, we'll represent the input and output graphs using only arrays and ints. The graph is given as an array of edges, where each "edge" is a 3-item array where the first two items are the vertices the edge connects and the third item is the edge's weight. Fill in the file MST.java to use Kruskal's Algorithm to create this MST. Hints You will find the following tools useful: The UnionFind class you implemented in the first half of the lab. The Arrays.sort method. The EDGE_WEIGHT_COMPARATOR given to you. It compares "edges" (three-element arrays) based on their weights. Testing 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 for the main program that generate the graph in the test case. Executing the following command (after replacing the arguments with the printed out parameters) prints the corresponding test case and the MST your program produces from it. (Note: Before running the following command, make sure you compiles Utils.java first by runningg javac Utils.java.) java Utils V MINEDGES MAXWEIGHT RANDOM-SEED true (The arguments V through RANDOM-SEED tell Utils.randomConnectedGraph what graph to generate). This is less helpful on really large test cases, of course. D. Submission You will be required to submit: UnionFind.java with union() and find() implemented. MST.java which implements Kruskal's Algorithm. partner.txt if you worked with a partner. The grading scheme is as follows (maximum 2pts total): 1.5pt: Passing UnionFind correctness tests. The AG UnionFind correctness tests are very similar to the provided UnionFindTest class. 1.5pt: Passing MST correctness and efficiency tests. These are the same as those provided in the MSTTest class. You will need a working UnionFind implementation to complete this portion. If you are seeing timeout errors in Gradescope, that means your code is taking too long to run. Don't forget to push both your commits and tags for your final submission. git add lab13 # or equivalent add command
git commit -m "submitting lab13"
git tag lab13-x # x is the next highest submission number
git push
git push --tags
