Fig. 1 shows a weighted undirected graph . The vertex set of is , and the edge set of is . For each edge , the order of and is not distinguished. In Algorithms 1 and Algorithm 2, and are referred to as and , respectively. The weight of each edge in is given in Fig. 1. A minimum spanning tree of is a connected subgraph that contains all vertices in , has no cycles, and minimizes the total weight of its edges.
Prim's algorithm is a greedy method for constructing a minimum spanning tree. The algorithm starts from an arbitrary root and grows the tree by iteratively selecting edges with the smallest weights , until the tree includes all vertices in . To select the next vertex to add, the algorithm manages the vertices using a min-priority queue . Each vertex in the queue has an attribute , which stores the weight of the smallest edge weights between and the tree. For each step, the vertex with the smallest is extracted from and added to the tree. The parent of a vertex in the tree is denoted by . Answer the following questions about this algorithm.
(1) Complete Algorithm 1: MST-PRIM, which shows the pseudo-code for Prim's algorithm, by filling in the blanks and . In Algorithm 1, denotes the set of vertices stored in the min-priority queue. The following operations are used:
inserts a vertex into .
removes and returns the vertex in that has the smallest .
updates the value of to for vertex in .
Assume that the priority queue maintains its order so that the vertex with the smallest can always be extracted without searching. This reordering is performed after each of the operations , , and .
(2) Suppose that Algorithm 1 is applied to the graph with . List all the vertices remaining in at the end of each iteration of the while loop as pairs , sorted in ascending order of . In the answer, write each state of on a separate line, in execution order, until . If multiple vertices have the same , list them in alphabetical order.
The state of just before entering the while loop is as follows (do not include this in your answer):
(3) Answer the asymptotic upper bound of the worst-case running time when Algorithm 1 is executed on the graph . Use the Big-O notation and express the answer using and , where denotes the number of elements in a set. Assume that the reorganization of the priority queue associated with each of the operations , , and takes time. Answer with the smallest order.
Kruskal's algorithm derives a minimum spanning tree by sequentially adopting an edge that does not generate a cycle, in ascending order of edge weight. Algorithm 2 shows a pseudo-code of Kruskal's algorithm in which Union-find algorithm is used to evaluate whether a cycle is generated by the selected edge. Union-find can efficiently check whether two elements belong to the same set by expressing a set with a tree structure. Answer the following questions.
(1) Suppose that Kruskal's algorithm is applied to the graph with the weights shown in Fig. 1. Show the edges composing the obtained minimum spanning tree in order of being adopted. If there are multiple edges with the same weight, any of them can be selected first.
(2) Let denote a parent node of a node in a tree structure. Assume when is a root. Express the tree shown in Fig. 2 in the format of , where the root of is .
(3) Fill in the blank to complete Algorithm 2.
(4) The computing efficiency can be improved when the line 14 in Algorithm 2 is replaced with . Explain the reason. You may use diagrams.
