Question

图的应用—最小生成树

Answer 1

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

把构成联通网的最小代价的生成树成为最小生成树。

图中粗线部分，便是联通了全部顶点 代价最小的生成树。
那如何构建一个最小生成树？

从一个顶点V0开始，不断选取未遍历的边中权值最小的边。

注意:
更新lowcost 数组与adjvex 数组的条件:

创建一个图：

最小生成树：

测试：

全局贪婪最小权值的边(通过排序)，同时防止形成环。

如何防止形成环：

1: 通过一个数组，记录边的开头和结尾沿着路径到达尾部的时候的顶点。
2: 遍历边，判断边的开头和结尾沿着路径到达尾部的时候，是否会来到同一个顶点。
3: 如果来到同一个顶点，说明形成环。
4: 如果来到了不同的顶点，说明没有形成环。

遍历越靠后，n = m 的几率越来越大，后入树的顶点很容易与之前的顶点形成闭环。

边表数组结构，使用上边创建的邻接矩阵的图。

kruskal算法实现：

测试：

get：parent数组+Find函数，防止了图中新加入的顶点与已加入的顶点形成闭环。