Tutoring Section 11: Disjoint Sets and MSTs
Disjoint Sets and MSTs
Second to last tutoring section this week, you are almost done with CS61BL. Today we are going to go over Disjoint Sets and Minimum Spanning Trees. Disjoint sets are data structures that focus on keeping track of which elements in a certain set belong to each other. We will try to optimize this to accommodate for the exhaustive functions: union and find. In order to implement a very efficient UnionFind, we will be using path compression and union by height/rank. This will ultimately yield a very nice O(Mlog*(N)) runtime. With this data structure in mind, we can also start finding the minimum spanning tree. The tree with the lowest edge weights possible that reaches all the vertices in the Graph. For this, we will be running Prim’s and Kruskal’s algorithms, which heavily depend on the efficient implementation of the UnionFind that we implemented earlier.
Resources