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.


Note: The tutoring worksheets are property of CS61B(L) and are solely intended for the purpose of personal use.