最小支撑树_计算机术语 - 线报百科mbji.cn

最小支撑树

计算机术语

设G=（V，E）是一个无向连通网，生成树上各边的权值之和为该生成树的代价，在G的所有生成树中，代价最小的生成树就称为最小支撑树，或称最小生成树。

结构介绍

生成树

由图遍历的过程中经过的边加上图的所有顶点所构成的子图。

生成树的特点

（1）n个顶点的连通子图的生成树是一个极小连通子图，它包含图中所有顶点和n-1条边（但有n-1条边的图不一定是生成树）。

（2）生成树中任意两个顶点间的路径是唯一的。

树的权

生成树T各边的权值总和称为该树的权。

最小生成树

将权最小的生成树称为图的最小生成树。

Krusal算法和Prim算法是两个构造最小生成树的著名算法。

普里姆算法

设为 N=(V,E,C)连通网，TE是N的最小支撑树的边的集合。

① 算法开始时， U= {u o }(u o ∈ V), TE= ○ ；

② 找到满足

weight(u,v)=min{weight(u 1 ,v 1 )| u 1 ∈ U, v 1 ∈ V-U }, 的边，把它并入集合

TE中，v同时并入U。

③ 反复执行② ,直至 V=U 时终止算法。

普里姆算法执行过程示例

由上述图解算法的过程知，构造的最小生成树不一定唯一，但最小生成树的权值之和一定是相同的。

参考资料

最新修订时间：2023-08-10 11:58

条目作者

概述

结构介绍

普里姆算法

参考资料