IS CS-2017S1-02

题目来源：Problem 2 日期：2024-08-09 题目主题: CS-算法-图论-最小生成树

解题思路

这道题目考察了最小生成树算法的实现和复杂度分析。我们需要理解算法 $A$ 的工作原理,分析不同图表示方法下的最佳实现,并证明算法的正确性。关键点包括贪心策略、图的表示方法对算法效率的影响,以及最小生成树的性质。

Solution

1. Completing the algorithm description

The appropriate phrase to fill in (a) is:

“all edges connecting a vertex in $G^{\prime }$ to a vertex not in $G^{\prime }$”

This choice ensures that we always select an edge that connects the current partial spanning tree to a new vertex, maintaining the tree structure and gradually including all vertices.

2. Implementation for dense graphs

For dense graphs represented by an adjacency matrix:

1. Initialize a Union-Find set to keep track of connected components. $O(V)$
2. Initialize an array minCost[1..V] to store the minimum cost edge from $G^{\prime }$ to each vertex not in $G^{\prime }$. $O(V)$
3. Choose an arbitrary starting vertex and mark it as in $G^{\prime }$.
4. Repeat $V-1$ times: a) Scan minCost array to find the minimum cost edge to a vertex not in $G^{\prime }$. $O(V)$ b) Add this edge to $G^{\prime }$ and mark the new vertex as in $G^{\prime }$. $O(1)$ c) Update minCost for vertices not in $G^{\prime }$ by checking if there’s a cheaper edge from the newly added vertex. $O(V)$

Time complexity: $O(V^2)$

Explanation: We perform $V-1$ iterations, each involving a scan of the minCost array ($O(V)$) and an update of minCost ($O(V)$). For dense graphs, $E\approx V^2$, so this $O(V^2)$ implementation is optimal as it matches the input size.

3. Implementation for sparse graphs

For sparse graphs represented by adjacency lists:

1. Initialize a priority queue $Q$ to store edges, keyed by their costs, implemented as a min-heap.
2. Choose an arbitrary starting vertex and add all its incident edges to $Q$.
3. Repeat until $Q$ is empty: a) Extract the minimum cost edge $(u,v)$ from $Q$. $O(\log E)$ b) If $v$ is already in $G^{\prime }$, discard this edge and continue. c) Otherwise, add $(u,v)$ to $G^{\prime }$ and add all edges incident to $v$ to $Q$. $O(deg(v)\ast \log E)$

Time complexity: $O(E\log E)$

Explanation: The time complexity is dominated by operations on the priority queue $Q$, which is implemented as a min-heap. Each vertex is added to $G^{\prime }$ once, and when it’s added, we process all its incident edges. In total, we process at most $2E$ edges (each edge is encountered from both its endpoints). Each edge operation (insert or extract-min) on the priority queue takes $O(\log E)$ time as a min-heap. Since the graph is sparse, $E\approx V$, so the time complexity can also be written as $O(E\log V)$.

4. Proof of correctness

To prove that Algorithm $A$ (Kruskal’s Algorithm) produces a minimum spanning tree, we need to establish that the algorithm satisfies the greedy choice property and the optimal substructure property. The proof can be outlined as follows:

1. Greedy Choice Property: Kruskal’s algorithm always adds the smallest edge that does not form a cycle. We need to prove that this choice is safe and that it does not exclude the possibility of obtaining the MST.

2. Optimal Substructure Property: A subgraph of a minimum spanning tree is also a minimum spanning tree for its vertices. Therefore, if the MST has been built partially, adding the next smallest edge that does not form a cycle will lead to the global MST.

Detailed Proof

Greedy Choice Property

Let’s consider a step in Kruskal’s algorithm where the edge $\mathbf{e}=(u,v)$ is added to the MST. Assume $\mathbf{T}$ is the MST being constructed by Kruskal’s algorithm, and ${\mathbf{T}}^{\prime }$ is some other MST that includes a different edge ${\mathbf{e}}^{\prime }\ne \mathbf{e}$.

1. Case 1: ${\mathbf{e}}^{\prime }$ is not in $\mathbf{T}$. If we add ${\mathbf{e}}^{\prime }$ to $\mathbf{T}$, then $\mathbf{T}$ will form a cycle. Since ${\mathbf{T}}^{\prime }$ is also a spanning tree, it must contain another edge $\mathbf{f}$ in the cycle that is not in ${\mathbf{T}}^{\prime }$. If we replace $\mathbf{f}$ with $\mathbf{e}$ in ${\mathbf{T}}^{\prime }$, the resulting tree ${\mathbf{T}}^{\prime \prime }$ will still be a spanning tree, and the weight will be less than or equal to the weight of ${\mathbf{T}}^{\prime }$ because $w(\mathbf{e})\le w(\mathbf{f})$. Therefore, the new tree ${\mathbf{T}}^{\prime \prime }$ is also an MST.

2. Case 2: ${\mathbf{e}}^{\prime }$ is already in $\mathbf{T}$. Then $\mathbf{T}$ and ${\mathbf{T}}^{\prime }$ differ only by the edges added after ${\mathbf{e}}^{\prime }$. By the inductive hypothesis, adding $\mathbf{e}$ will not exclude any edge from $\mathbf{T}$, so $\mathbf{T}$ remains an MST.

This shows that adding $\mathbf{e}$ does not prevent us from achieving the MST, and hence, the greedy choice made by Kruskal’s algorithm is safe.

Optimal Substructure Property

Assume that ${\mathbf{T}}_k$ is the tree formed after the first $k$ steps of Kruskal’s algorithm. We need to show that ${\mathbf{T}}_k$ is part of some MST.

1. When $k=0$, ${\mathbf{T}}_0$ is empty, which trivially satisfies the property.

2. Suppose ${\mathbf{T}}_k$ is a subgraph of an MST ${\mathbf{T}}^{\ast }$. Let ${\mathbf{e}}_{k+1}$ be the edge added in the $(k+1)$-th step by Kruskal’s algorithm.

   • If ${\mathbf{e}}_{k+1}$ is also in ${\mathbf{T}}^{\ast }$, then ${\mathbf{T}}_{k+1}={\mathbf{T}}_k+{\mathbf{e}}_{k+1}$ is still a subgraph of ${\mathbf{T}}^{\ast }$.
   • If ${\mathbf{e}}_{k+1}$ is not in ${\mathbf{T}}^{\ast }$, adding ${\mathbf{e}}_{k+1}$ to ${\mathbf{T}}^{\ast }$ would create a cycle, and one of the edges ${\mathbf{e}}^{\prime }$ in the cycle must not be in ${\mathbf{T}}_k$. Since ${\mathbf{e}}^{\prime }$ is not in ${\mathbf{T}}_k$ and ${\mathbf{e}}_{k+1}$ is the smallest edge that does not form a cycle in ${\mathbf{T}}_k$, we have $w({\mathbf{e}}_{k+1})\le w({\mathbf{e}}^{\prime })$. By replacing ${\mathbf{e}}^{\prime }$ with ${\mathbf{e}}_{k+1}$ in ${\mathbf{T}}^{\ast }$, we obtain another MST that contains ${\mathbf{T}}_{k+1}$.

This inductive argument ensures that each intermediate step ${\mathbf{T}}_k$ is part of some MST, and when the algorithm terminates, $\mathbf{T}={\mathbf{T}}_{|V|-1}$ is an MST.

By satisfying both the greedy choice property and the optimal substructure property, Kruskal’s algorithm is guaranteed to produce a minimum spanning tree. The algorithm’s correctness hinges on the fact that it always selects the smallest available edge that does not form a cycle, which is a necessary and sufficient condition for obtaining the MST.

知识点

最小生成树Kruskal算法贪心算法图论数据结构复杂度分析

难点思路

1. 理解稀疏图和稠密图对算法实现的影响
2. 分析不同数据结构 (如优先队列) 在算法中的应用
3. 使用归纳法和切割性质证明算法的正确性

解题技巧和信息

1. 在分析图算法时,要考虑图的表示方法 (邻接矩阵 vs 邻接表) 对算法效率的影响
2. 时间复杂度分析中,要注意图的特性 (稀疏 vs 稠密) 对复杂度的影响
3. 证明贪心算法正确性时,可以使用归纳法和反证法
4. 最小生成树问题中,切割性质是一个强有力的工具

常见图算法的时间复杂度:

• Kruskal’s MST: $O(E\log E)$
• Prim’s MST (binary heap): $O((V+E)\log V)$
• Prim’s MST (Fibonacci heap): $O(E+V\log V)$
• Dijkstra’s (binary heap): $O((V+E)\log V)$
• Dijkstra’s (Fibonacci heap): $O(E+V\log V)$
• Bellman-Ford: $O(VE)$
• Floyd-Warshall: $O(V^3)$

重点词汇

• Minimum Spanning Tree (MST) 最小生成树
• adjacency matrix 邻接矩阵
• adjacency list 邻接表
• dense graph 稠密图
• sparse graph 稀疏图
• greedy algorithm 贪心算法
• Cut Property 切割性质
• time complexity 时间复杂度
• priority queue 优先队列

参考资料

1. Introduction to Algorithms (CLRS), Chapter 23: Minimum Spanning Trees
2. Algorithm Design (Kleinberg & Tardos), Chapter 4: Greedy Algorithms
3. The Algorithm Design Manual (Skiena), Section 6.1: Minimum Spanning Trees