目录

最小生成树(图的应用)

基本介绍

N个点用N-1条边连接成一个连通块,形成的图形只可能是树,没有别的可能。 https://gitee.com/lienhui68/picStore/raw/master/null/20200705031248.png 最小生成树(Minimum Cost Spanning Tree),简称 MST。 给定一个N个顶点的带权无向连通图,构成一颗极小连通子图,并使连通子图中n-1条边权值之和最小,则称其为连通网的最小生成树。

最小生成树用来解决什么问题

就是用来解决如何用最小的“代价”使用N-1条边连接N个点的问题。例如:

城市公交网建设问题

  • 问题描述 有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有个特点,即任一对城市都是连通的。现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少
  • 输入格式 n(城市数,1<=n<=100)   e(边数)   以下e行,每行3个数i,j,wij(表示在城市i,j之间修建高速公路的造价)。
  • 输出格式   n-1行,每行为两个城市的序号,表明这两个城市间建一条高速公路。
  • 输入样例   5 8   1 2 2   2 5 9   5 4 7   4 1 10   1 3 12   4 3 6   5 3 3   2 3 8
  • 输出样例    1 2    2 3    3 4    3 5

构建算法

Kruskal算法

Kruskal算法在找最小生成树结点之前,需要对权重从小到大进行排序。将排序好的权重边依次加入到最小生成树中(如果加入时产生回路就跳过这条边,加入下一条边),当所有的结点都加入到最小生成树中后,就找到了这个连通图的最小生成树~

kauskal适用于网比较稀疏的图 先对权重由小到大排序,依次遍历权重两边的点,如果点已经被遍历过,则跳过这个权重,继续遍历。直到遍历完成。 可以把kruskal算法理解为边优先。

Prim算法

首先以一个结点作为最小生成树的初始结点,然后以迭代的方式找出最小生成树中各结点权重最小的边,并加到最小生成树中。(加入之后如果产生回路了就要跳过这条边,选择下一个结点)当所有的结点都加入到最小生成树中后,就找出了这个连通图的最小生成树

一般来说,prim算法常用于网比较稠密的图。 对于一个点来说,找到权重最小的连接点。之后对于这两个点来说,找到这两个点中权重最小的另外一个点(即没有经过遍历的点)。之后以此类推,直到遍历完成。 可以把prim算法理解为点优先

两种算法区别 从策略上来说,Prim算法是直接查找,多次寻找邻边的权重最小值,而Kruskal是需要先对权重排序后查找的 所以说,Kruskal在算法效率上是比Prim快的,因为Kruskal只需一次对权重的排序就能找到最小生成树,而Prim算法需要多次对邻边排序才能找到