Prim和Kruskal算法如何应用于构建最小生成树？

本文共计3395个文字，预计阅读时间需要14分钟。

最小生成树（MST）概念：一个有n个节点的连通图的最小生成树是原图的最小连通子图，包含原图中的所有n个节点，并保持图连通的最少边，所谓一个带权图。

最小生成树MST（Minimum Spanning Tree） (1)概念

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边，所谓一个带权图的最小生成树，就是原图中边的权值最小的生成树，所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。

(2)性质

• 一个连通图可以有多个生成树；

• 一个连通图的所有生成树都包含相同的顶点个数和边数；

• 生成树当中不存在环；

• 移除生成树中的任意一条边都会导致图的不连通， 生成树的边最少特性；

• 在生成树中添加一条边会构成环。