一、相关概念
- 连通图：图中的任意两个节点之间都是联通的，即：总能从A节点按照一定路径走到B节点。
- 生成树：为联通图的一个联通子图，包含N个结点和N-1条边。
- 最小生成树：当联通图中的每条边带有权值时，所有边权值和最小的生成树。
二、问题导向
各个城市之间修建铁路，城市之间铺设电缆、水管等，不考虑环境等复杂因素，肯定最小生成树对应的权值（对应管线、铁路等长度）和最小怎样才能成本最低。因此如何铺设的问题转化成了找到这个最小生成树的问题。如下图(A~F表示城市，线上的数字表示距离)：
三、相关算法
注：正常情况下没有办法一眼看出来该如何选择的，如果更复杂一点的话就更难用眼睛看出来的了，因此面对该问题需要有响应的算法来解决。听着很高端、实际实现的代码逻辑很复杂，但是懂了思想理解起来很容易。
最终目的： 找到我们想要的N-1条线。Prim算法：
通俗理解： - 任意选择一个结点开始（从此已有结点多了一个0到1）
- 从已有的结点中，找与已有结点和剩下的结点连线权限最小的那个
- 迭代重复第二步，直到所有结点都被连接。此时刚哈N-1条边。
举例： 假设以A为第一个点，我们依次被连接的顶点顺序为：A->F->E->D->C->B，边被选择的顺序为：4、2、3、4、3。步骤为红色12345的顺序。
Kruskal算法：
通俗理解：
- 从所有的边中找最短的边
- 保证，所有的边连起来不能构成环路，如果构成环路则选择次小的边、或者次次小的边，
- 按照第二部的要求，重复第一步的过程，直到所有的结点被连接。
举例： 依次被选择的边：2(EF)->3(D)->3(BC)->4(A)->4。步骤为红色12345的顺序。
...
...
00:00
00:00
本文为作者原创文章，未经作者允许不得转载。