CSE 2331/5331 Minimum Spanning Tree Greedy Method Questions

1) To implement the union-find data structure, instead of using a negative number to indicate the height of a tree, suppose we store the actual height value at the root and use an additional array [1. . ] to indicate whether a node is a root, where [ ] = 1 if node is a root and [ ] = 0 otherwise. For instance, in the following example, [7] = 1 and [7] = 2, indicating that node 7 is a root and the height of the tree rooted at node 7 is 2.

2) Suppose we run Prim’s algorithm on the following graph. Suppose we start with vertex s and have included edges ( , ), ( , ), and ( , ) in T. Suppose we use a min-priority queue Q to implement U.