【数据结构（邓俊辉）学习笔记】图06——最小支撑树_支撑树和割

0. 概述

学习下最小支撑树和prim算法。

1. 支撑树

最小的连通图是树。

连通图G的某一无环连通子图T若覆盖G中所有的顶点，则称作G的一棵支撑树或生成树（spanning tree）。

就保留原图中边的数目而言，支撑树既是“禁止环路”前提下的极大子图，也是“保持连通”前提下的最小子图。

确切地，尽管同一幅图可能有多棵支撑树，但由于其中的顶点总数均为n，故其采用的边数也均为n - 1。

2. 最小支撑树

若图G为一带权网络，则每一棵支撑树的成本（cost）即为其所采用各边权重的总和。在G的所有支撑树中，成本最低者称作最小支撑树（minimum spanning tree, MST）。

3. 歧义性

尽管同一带权网络通常都有多棵支撑树，但总数毕竟有限，故必有最低的总体成本。然而，总体成本最低的支撑树却未必唯一。

最小支撑树允许有负数，因为它算的是total cast。

若有重边，通过强制附加某种次序即可消除这种歧义性。

4. 蛮力算法

由最小支撑树的定义，可直接导出蛮力算法大致如下：逐一考查G的所有支撑树并统计其成本，从而挑选出其中的最低者。然而根据Cayley公式，由n个互异顶点组成的完全图共有$n^{n-2}$棵支撑树，即便忽略掉构造所有支撑树所需的成本，仅为更新最低成本的记录就需要O($n^{n-2}$)时间。

事实上基于PFS搜索框架，并采用适当的顶点优先级更新策略，即可得出如下高效的最小支撑树构造算法。

5. Prim算法

5.1 割与极短跨越边

图G = (V; E)中，顶点集V的任一非平凡子集U及其补集V\U都构成G的一个割（cut），记作(U : V\U)。若边uv满足u∈U且v∈V\U，则称作该割的一条跨越边（crossing edge）。因此类边联接于V及其补集之间，故亦形象地称作该割的一座桥（bridge）。

Prim算法的正确性基于以下事实：最小支撑树总是会采用联接每一割的最短跨越边。

5.2 贪心迭代

5.3 实例

5.4 实现

这个实现无非就是一个PFS。

这棵子树上的点认为都访问过了，没有访问的点（补集上的点）手上都拥有一个优先级数，这个数就是代表它到子树的距离，这个距离在任何时刻各自都会实现于某个特定的点，每次要做的事就是在树中找到最小的把它拓展进来，接下来再update。

接下来就是为prim算法写一个优先级更新器，实现更新算法。实现流程：

在当前图g中，如果有一个点uk刚刚被扩展进来，加入到这棵树中，对于它的每个尚未被发现的邻居v，按照prim策略做松弛。首先判断下当前的提供的优先级数是否更好，如果当前的优先级数更好便会欣然接受这个。再更新下v的父亲。

5.5 复杂度

目前只是把算法将明白了，数据结构还差的很远，每次查找优先级数还比较慢，以上Prim算法的时间复杂度为O($n^2$)。作为PFS搜索的特例，Prim算法的效率也可借助优先级队列进一步提高。