一、定义

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

二、概述

在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得联通所有结点的的 w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树其实是最小权重生成树的简称。

三、生成树

要求最小生成树，先来理解什么是生成树。

生成树的定义：一个连通图的生成树是一个极小的连通子图，它包含图中全部的n个顶点，但只有构成一棵树的n-1条边。

可以看到一个包含3个顶点的完全图可以产生3颗生成树。那么对于包含n个顶点的无向完全图最多包含n^n-2 个生成树。

生成树的特点：

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

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

• 生成树当中不存在环；

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

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

• 对于包含n个顶点的连通图，生成树包含n个顶点和n-1条边

四、最小生成树

所谓一个 带权图 的最小生成树，就是原图中边的权值最小的生成树 ，所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。

比如上面这个，因为n个顶点的联通图，所以生成树包含n个顶点和n-1条边。

所以，很明显选3条边连起来肯定是1、2、3这个三个权重最小，那么1、2、3一共有两种选法，所以最小生成树有两个。

(adsbygoogle = window.adsbygoogle || []).push({});