東京大学 情報理工学系研究科 電子情報学専攻 2024年8月実施 専門 第3問

https://runjp.com/docs/tokyo-university/IST/denshi/2025/denshi_202408_senmon_3

Description

The Minimum Spanning Tree (MST) problem is a problem where, given an undirected graph $G = (V, E)$ where $V$ is the set of vertices, $E$ is the set of edges, and each edge is assigned a weight, the goal is to find one subgraph that satisfies the following conditions:

• It contains all vertices $V$ of graph $G$.
• It has a tree structure with no cycles (closed loops).
• The total sum of the weights of the edges is minimized.

When answering, please assume the following conditions beforehand:

• When using a sorting function, assume a computational complexity of $O(n \log n)$ for an array of length $n$.
• Determining which set a vertex belongs to, or merging two distinct sets, can be performed in constant time using, for example, a disjoint-set data structure (Union-Find).
• When using a priority queue, use one implemented via a heap.

Answer the following questions:

(1) Briefly show the strategy and pseudocode of an algorithm to solve the minimum spanning tree problem. Note that the algorithm must be deterministic and have a time complexity of $O(|E| \log |V|)$. $|E|$ denotes the number of elements in set $E$, and $|V|$ denotes the number of elements in set $V$.

(2) Using the algorithm shown in (1), show the minimum spanning tree and the total sum of edge weights for the graph in the figure. (Note: The figure itself is not included in this image).

(3) Briefly show the strategy, pseudocode, and time complexity of an algorithm to find the spanning tree with the second smallest sum of edge weights among all spanning trees (hereinafter referred to as the Second MST).

(4) Using the algorithm shown in (3), show the Second MST and the total sum of edge weights for the graph in the figure.