个人网站怎么做详情页,网站规划和建设方案,土建网招聘信息,网站建设与管理试题一文章目录 0. 概述1. 支撑树2. 最小支撑树3. 歧义性4. 蛮力算法5. Prim算法5.1 割与极短跨越边5.2 贪心迭代5.3 实例5.4 实现5.5 复杂度 0. 概述
学习下最小支撑树和prim算法。
1. 支撑树 最小的连通图是树。
连通图G的某一无环连通子图T若覆盖G中所有的顶点#xff0c;则称… 文章目录 0. 概述1. 支撑树2. 最小支撑树3. 歧义性4. 蛮力算法5. Prim算法5.1 割与极短跨越边5.2 贪心迭代5.3 实例5.4 实现5.5 复杂度 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 n^{n-2} nn−2棵支撑树即便忽略掉构造所有支撑树所需的成本仅为更新最低成本的记录就需要O( n n − 2 n^{n-2} nn−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 n^2 n2)。作为PFS搜索的特例Prim算法的效率也可借助优先级队列进一步提高。
