京都大学 情報学研究科 知能情報学専攻 2025年8月実施 情報学基礎 F2-2

标签：

• Kyoto-University
• Minimum-Spanning-Tree
• Prim-Algorithm
• Kruskal-Algorithm
• Union-Find-Path-Compression

Author

祭音Myyura

Description

Fig. 1 shows a weighted undirected graph $G$. The vertex set of $G$ is $V = \{a, b, c, d, e, f\}$, and the edge set of $G$ is $E = \{(a, b), (a, c), (a, e), (b, c), (b, d), (d, e), (d, f), (e, f)\}$. For each edge $(u, v) \in E$, the order of $u$ and $v$ is not distinguished. In Algorithms 1 and Algorithm 2, $V$ and $E$ are referred to as $G.V$ and $G.E$, respectively. The weight $w(u, v)$ of each edge in $G$ is given in Fig. 1. A minimum spanning tree of $G$ is a connected subgraph that contains all vertices in $G$, has no cycles, and minimizes the total weight of its edges.

Figure 1.

Q.1

Answer the following questions.

(1) List all the edges of the minimum spanning tree of $G$, and answer the total weight of those edges.

(2) Suppose that a cut $(S, V - S)$ of $G$ is defined by the vertex set $S = \{d, f\}$. List all the edges between $S$ and $V - S$.

(3) Prove by contradiction that the edge $(b, d)$ is included in the minimum spanning tree of $G$.

Q.2

Prim's algorithm is a greedy method for constructing a minimum spanning tree. The algorithm starts from an arbitrary root $r \in V$ and grows the tree by iteratively selecting edges with the smallest weights $w(u, v)$, until the tree includes all vertices in $V$. To select the next vertex to add, the algorithm manages the vertices using a min-priority queue $Q$. Each vertex $v \in V$ in the queue has an attribute $v.key$, which stores the weight of the smallest edge weights between $v$ and the tree. For each step, the vertex with the smallest $key$ is extracted from $Q$ and added to the tree. The parent of a vertex $v$ in the tree is denoted by $v.parent$. 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 $\fbox{(a)}$ and $\fbox{(b)}$. In Algorithm 1, $Q$ denotes the set of vertices stored in the min-priority queue. The following operations are used:

• $\operatorname{Insert}(Q, u)$ inserts a vertex $u$ into $Q$.
• $\operatorname{Extract-Min}(Q)$ removes and returns the vertex in $Q$ that has the smallest $key$.
• $\operatorname{Decrease-Key}(Q, v, w(u, v))$ updates the value of $v.key$ to $w(u, v)$ for vertex $v$ in $Q$. Assume that the priority queue $Q$ maintains its order so that the vertex with the smallest $key$ can always be extracted without searching. This reordering is performed after each of the operations $\operatorname{Insert}$, $\operatorname{Extract-Min}$, and $\operatorname{Decrease-Key}$.

$$\begin{array}{l} \hline \textbf{Algorithm 1: } \text{:MST-PRIM}(G, w, r) \\ \hline \mathbf{1}\phantom{0} \quad \textbf{for each } \textit{vertex } u \in G.V \\ \mathbf{2}\phantom{0} \quad \vert \quad u.key = \infty \\ \mathbf{3}\phantom{0} \quad \vert \quad u.parent = \text{NIL} \\ \mathbf{4}\phantom{0} \quad r.key = 0 \\ \mathbf{5}\phantom{0} \quad Q = \emptyset \\ \mathbf{6}\phantom{0} \quad \textbf{for each } \textit{vertex } u \in G.V \\ \mathbf{7}\phantom{0} \quad \vert \quad \text{INSERT}(Q, u) \\ \mathbf{8}\phantom{0} \quad \textbf{while } Q \neq \emptyset \\ \mathbf{9}\phantom{0} \quad \vert \quad u = \text{EXTRACT-MIN}(Q) \\ \mathbf{10} \quad \vert \quad \textbf{for each } v \in G.V \textit{ adjacent to } u \\ \mathbf{11} \quad \vert \quad \vert \quad \textbf{if } v \in \text{\fbox{(a)}} \textit{ and } w(u, v) < \text{\fbox{(b)}} \\ \mathbf{12} \quad \vert \quad \vert \quad \quad v.parent = u \\ \mathbf{13} \quad \vert \quad \vert \quad \quad v.key = w(u, v) \\ \mathbf{14} \quad \vert \quad \vert \quad \quad \text{DECREASE-KEY}(Q, v, w(u, v)) \\ \hline \end{array}$$

(2) Suppose that Algorithm 1 is applied to the graph $G$ with $r = d$. List all the vertices $v$ remaining in $Q$ at the end of each iteration of the while loop as pairs $(v, v.key)$, sorted in ascending order of $key$. In the answer, write each state of $Q$ on a separate line, in execution order, until $Q = \emptyset$. If multiple vertices have the same $key$, list them in alphabetical order. The state of $Q$ just before entering the while loop is as follows (do not include this in your answer):

$$(d, 0), (a, \infty), (b, \infty), (c, \infty), (e, \infty), (f, \infty)$$

(3) Answer the asymptotic upper bound of the worst-case running time when Algorithm 1 is executed on the graph $G = (V, E)$. Use the Big-O notation and express the answer using $|V|$ and $|E|$, where $|\cdot|$ denotes the number of elements in a set. Assume that the reorganization of the priority queue associated with each of the operations $\operatorname{Insert}$, $\operatorname{Extract-Min}$, and $\operatorname{Decrease-Key}$ takes $O(|V|)$ time. Answer with the smallest order.

Q.3

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 $G$ with the weights $w$ 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 $v.parent$ denote a parent node of a node $v$ in a tree structure. Assume $v.parent = v$ when $v$ is a root. Express the tree $T$ shown in Fig. 2 in the format of $\{(v_i, v_i.parent)\}, i = 1, 2, 3, 4$, where the root of $T$ is $v_2$.

(3) Fill in the blank $\fbox{(c)}$ to complete Algorithm 2.

(4) The computing efficiency can be improved when the line 14 in Algorithm 2 is replaced with $v.parent = \operatorname{FindSet}(v.parent)$. Explain the reason. You may use diagrams.

$$\begin{array}{l} \hline \textbf{Algorithm 1: } \text{:MST-KRUSKAL}(G, w) \\ \hline \mathbf{1}\phantom{0} \quad \text{Assume that } G.E \text{ is given with a list structure} \\ \mathbf{2}\phantom{0} \quad MST = \emptyset \\ \mathbf{3}\phantom{0} \quad \textbf{for each } v \in G.V \\ \mathbf{4}\phantom{0} \quad \quad v.parent = v \\ \mathbf{5}\phantom{0} \quad \text{Sort } G.E \text{ into ascending order by weight } w \\ \mathbf{6}\phantom{0} \quad \textbf{for each } (u, v) \in G.E \\ \mathbf{7}\phantom{0} \quad \quad \textbf{if } \text{\fbox{(c)}} \\ \mathbf{8}\phantom{0} \quad \quad \quad MST = MST \cup \{(u, v)\} \\ \mathbf{9}\phantom{0} \quad \quad \quad \text{Union}(u, v) \\ \mathbf{10} \quad \textbf{return } MST \\ \mathbf{11} \quad \text{FindSet}(v) \\ \mathbf{12} \quad \quad \textbf{if } v \neq v.parent \\ \mathbf{13} \quad \quad \quad \textbf{return } \text{FindSet}(v.parent) \\ \mathbf{14} \quad \quad \textbf{return } v.parent \\ \mathbf{15} \quad \text{Union}(u, v) \\ \mathbf{16} \quad \quad ru = \text{FindSet}(u) \\ \mathbf{17} \quad \quad rv = \text{FindSet}(v) \\ \mathbf{18} \quad \quad \textbf{if } ru == rv \\ \mathbf{19} \quad \quad \quad \textbf{return} \\ \mathbf{20} \quad \quad ru.parent = rv \end{array}$$

Figure 2.

题目描述

图 1 给出带权无向图 $G$。其顶点集与边集分别为

$$V=\{a,b,c,d,e,f\},$$

$$E=\{(a,b),(a,c),(a,e),(b,c),(b,d),(d,e),(d,f),(e,f)\}.$$

对每条边 $(u,v)\in E$，不区分 $u,v$ 的次序。在算法中，$V,E$ 分别记作 $G.V,G.E$；边权 $w(u,v)$ 如图所示。$G$ 的最小生成树是包含 $G$ 中全部顶点、连通且无环，并使边权总和最小的子图。

1. 回答下列问题。

   （1）列出 $G$ 的最小生成树的所有边，并给出这些边的总权重。

   （2）用顶点集 $S=\{d,f\}$ 定义割 $(S,V-S)$，列出连接 $S$ 与 $V-S$ 的全部边。

   （3）使用反证法证明边 $(b,d)$ 一定包含在 $G$ 的最小生成树中。

2. Prim 算法是一种构造最小生成树的贪心算法。它从任意根 $r\in V$ 开始，每次选择权重最小的适当边扩展树，直至树包含 $V$ 中全部顶点。算法使用最小优先队列 $Q$ 管理待加入顶点；队列中每个顶点 $v$ 的属性 $v.key$ 保存 $v$ 与当前树之间最小边的权重。每一步从 $Q$ 中取出 $key$ 最小的顶点并加入树，$v$ 在树中的父顶点记作 $v.parent$。

   （1）补全下面 Prim 算法伪代码中的空格 $\fbox{(a)}$ 与 $\fbox{(b)}$。其中 $Q$ 表示最小优先队列中的顶点集合，并使用以下操作：

   • $\operatorname{Insert}(Q,u)$：把顶点 $u$ 插入 $Q$；
   • $\operatorname{Extract-Min}(Q)$：从 $Q$ 删除并返回 $key$ 最小的顶点；
   • $\operatorname{Decrease-Key}(Q,v,w(u,v))$：把 $Q$ 中顶点 $v$ 的 $v.key$ 更新为 $w(u,v)$。

   假设优先队列始终维持顺序，因而无需搜索即可取出 $key$ 最小的顶点；每次执行 $\operatorname{Insert}$、$\operatorname{Extract-Min}$ 或 $\operatorname{Decrease-Key}$ 后都会重新整理队列。

   $$\begin{array}{l} \hline \textbf{算法 1：}\operatorname{MST\text{-}PRIM}(G,w,r)\\ \hline \mathbf{1}\phantom{0}\quad \textbf{for each }\textit{ vertex }u\in G.V\\ \mathbf{2}\phantom{0}\quad |\quad u.key=\infty\\ \mathbf{3}\phantom{0}\quad |\quad u.parent=\mathrm{NIL}\\ \mathbf{4}\phantom{0}\quad r.key=0\\ \mathbf{5}\phantom{0}\quad Q=\emptyset\\ \mathbf{6}\phantom{0}\quad \textbf{for each }\textit{ vertex }u\in G.V\\ \mathbf{7}\phantom{0}\quad |\quad \operatorname{Insert}(Q,u)\\ \mathbf{8}\phantom{0}\quad \textbf{while }Q\ne\emptyset\\ \mathbf{9}\phantom{0}\quad |\quad u=\operatorname{Extract-Min}(Q)\\ \mathbf{10}\quad |\quad \textbf{for each }v\in G.V\textit{ adjacent to }u\\ \mathbf{11}\quad |\quad |\quad \textbf{if }v\in\fbox{(a)} \textit{ and }w(u,v)<\fbox{(b)}\\ \mathbf{12}\quad |\quad |\quad |\quad v.parent=u\\ \mathbf{13}\quad |\quad |\quad |\quad v.key=w(u,v)\\ \mathbf{14}\quad |\quad |\quad |\quad \operatorname{Decrease-Key}(Q,v,w(u,v))\\ \hline \end{array}$$

   （2）把算法 1 应用于图 $G$，并令 $r=d$。在 while 循环每次迭代结束时，把 $Q$ 中剩余的全部顶点写成 $(v,v.key)$，按 $key$ 升序排列。按执行顺序每行写一个 $Q$ 的状态，直至 $Q=\emptyset$；若多个顶点的 $key$ 相同，则按字母顺序排列。进入循环之前的状态如下，不要把它写入答案：

   $$(d,0),(a,\infty),(b,\infty),(c,\infty),(e,\infty),(f,\infty).$$

   （3）求算法 1 在一般图 $G=(V,E)$ 上运行时最坏情形时间复杂度的渐近上界。使用大 $O$ 记号，以 $|V|,|E|$ 表示答案，并给出可能的最小阶。假设每次 $\operatorname{Insert}$、$\operatorname{Extract-Min}$ 和 $\operatorname{Decrease-Key}$ 所伴随的优先队列重组均耗时 $O(|V|)$。

3. Kruskal 算法按边权升序依次选取不会产生环的边，从而求得最小生成树。算法 2 使用并查集判断所选边是否产生环；并查集通过树结构表示集合，以高效判断两个元素是否属于同一集合。

   （1）对图 1 中的 $G$ 及其权重执行 Kruskal 算法，按被采用的先后顺序写出所得最小生成树的边。同权边可任选先后。

   （2）设 $v.parent$ 表示树中顶点 $v$ 的父结点，根结点满足 $v.parent=v$。图 2 中树 $T$ 的根为 $v_2$；用

   $$\{(v_i,v_i.parent)\},\qquad i=1,2,3,4$$

   的形式表示该树。

   （3）填写空格 $\fbox{(c)}$，补全算法 2。

   （4）若把算法 2 第 14 行替换为

   $$v.parent=\operatorname{FindSet}(v.parent),$$

   则计算效率会提高。说明原因，可以使用示意图。

   $$\begin{array}{l} \hline \textbf{算法 2：}\operatorname{MST\text{-}KRUSKAL}(G,w)\\ \hline \mathbf{1}\phantom{0}\quad \text{假设 }G.E\text{ 以列表结构给出}\\ \mathbf{2}\phantom{0}\quad MST=\emptyset\\ \mathbf{3}\phantom{0}\quad \textbf{for each }v\in G.V\\ \mathbf{4}\phantom{0}\quad |\quad v.parent=v\\ \mathbf{5}\phantom{0}\quad \text{按权重 }w\text{ 将 }G.E\text{ 升序排序}\\ \mathbf{6}\phantom{0}\quad \textbf{for each }(u,v)\in G.E\\ \mathbf{7}\phantom{0}\quad |\quad \textbf{if }\fbox{(c)}\\ \mathbf{8}\phantom{0}\quad |\quad |\quad MST=MST\cup\{(u,v)\}\\ \mathbf{9}\phantom{0}\quad |\quad |\quad \operatorname{Union}(u,v)\\ \mathbf{10}\quad \textbf{return }MST\\ \mathbf{11}\quad \operatorname{FindSet}(v)\\ \mathbf{12}\quad |\quad \textbf{if }v\ne v.parent\\ \mathbf{13}\quad |\quad |\quad \textbf{return }\operatorname{FindSet}(v.parent)\\ \mathbf{14}\quad |\quad \textbf{return }v.parent\\ \mathbf{15}\quad \operatorname{Union}(u,v)\\ \mathbf{16}\quad |\quad ru=\operatorname{FindSet}(u)\\ \mathbf{17}\quad |\quad rv=\operatorname{FindSet}(v)\\ \mathbf{18}\quad |\quad \textbf{if }ru==rv\\ \mathbf{19}\quad |\quad |\quad \textbf{return}\\ \mathbf{20}\quad |\quad ru.parent=rv\\ \hline \end{array}$$

考点

• 最小生成树的割性质：识别跨割的最轻边，并用交换论证或反证法证明边的必选性。
• Prim 算法：维护顶点键值与父结点，跟踪最小优先队列的状态并分析给定队列实现下的复杂度。
• Kruskal 算法：按权重排序边，利用并查集检测环并确定选边顺序。
• 并查集与路径压缩：理解 FindSet、Union 的树表示，以及路径压缩为何降低后续查询成本。

Kai

Q.1

(1)

The edges of the minimum spanning tree are

$$\boxed{ (a,e),\ (a,b),\ (d,f),\ (a,c),\ (b,d) }.$$

Their total weight is

$$1+2+2+3+3=\boxed{11}.$$

(2)

For

$$S=\{d,f\}, \qquad V-S=\{a,b,c,e\},$$

the edges crossing the cut $(S,V-S)$ are

$$\boxed{ (b,d),\ (d,e),\ (e,f) }.$$

(3)

Assume, for contradiction, that a minimum spanning tree $T$ does not contain $(b,d)$.

Add $(b,d)$ to $T$. This creates a cycle. Since $b\notin S$ and $d\in S$, the path from $b$ to $d$ in $T$ must contain an edge crossing the cut $(S,V-S)$. Because $(b,d)\notin T$, that edge must be either $(d,e)$ or $(e,f)$, whose weights are $5$ and $4$, respectively.

Removing that edge from the cycle and keeping $(b,d)$, whose weight is $3$, produces a spanning tree with smaller total weight. This contradicts the minimality of $T$.

Therefore,

$$\boxed{(b,d)\text{ is contained in every minimum spanning tree of }G}.$$

---

Q.2

(1)

The blanks are

$$\boxed{\text{(a)}=Q}, \qquad \boxed{\text{(b)}=v.key}.$$

Thus the condition is

$$\textbf{if }v\in Q\textbf{ and }w(u,v)<v.key.$$

(2)

Starting from $r=d$, the states of $Q$ after successive iterations of the while loop are

$$(f,2),\ (b,3),\ (e,5),\ (a,\infty),\ (c,\infty)$$

$$(b,3),\ (e,4),\ (a,\infty),\ (c,\infty)$$

$$(a,2),\ (c,4),\ (e,4)$$

$$(e,1),\ (c,3)$$

$$(c,3)$$

$$\emptyset.$$

The vertices are extracted in the order

$$d,\ f,\ b,\ a,\ e,\ c.$$

(3)

There are $|V|$ insertions and $|V|$ extractions. Since each priority-queue reorganization takes $O(|V|)$ time, these operations take

$$O(|V|^2).$$

The adjacency lists contain $O(|E|)$ entries, and $\operatorname{Decrease-Key}$ is called at most $O(|E|)$ times. Thus these updates take

$$O(|V||E|).$$

Hence the total running time is

$$O(|V|^2+|V||E|).$$

Because the graph is connected, $|E|\ge |V|-1$, so the smallest equivalent bound is

$$\boxed{O(|V||E|)}.$$

---

Q.3

(1)

One possible order in which Kruskal's algorithm adopts the edges is

$$\boxed{ (a,e),\ (a,b),\ (d,f),\ (a,c),\ (b,d) }.$$

Their weights are

$$1,\ 2,\ 2,\ 3,\ 3,$$

respectively. The order of edges having the same weight may be interchanged.

(2)

Since $v_2$ is the root, the parent representation is

$$\boxed{ \{ (v_1,v_2),\ (v_2,v_2),\ (v_3,v_2),\ (v_4,v_1) \} }.$$

(3)

An edge is adopted only when its endpoints belong to different components. Therefore,

$$\boxed{ \text{(c)}\;=\; \operatorname{FindSet}(u)\ne\operatorname{FindSet}(v) }.$$

(4)

The improved version of FindSet is

FindSet(v)
    if v != v.parent
        v.parent = FindSet(v.parent)
    return v.parent

The assignment

$$v.parent=\operatorname{FindSet}(v.parent)$$

makes every visited vertex point directly to the root. This operation is called path compression.

For example, a path

$$v_1\to v_2\to v_3\to v_4$$

is changed after FindSet(v1) into

$$v_1\to v_4,\qquad v_2\to v_4,\qquad v_3\to v_4.$$

Thus the tree becomes shallower, and later FindSet operations require fewer parent-pointer traversals. Therefore, repeated cycle tests in Kruskal's algorithm become more efficient.