利用克鲁斯卡尔算法判断最小生成树是否成环

本文主要是介绍利用克鲁斯卡尔算法判断最小生成树是否成环，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前提背景：

1、最小生成树内不含有环

2、在使用克鲁斯卡尔算法生成最小生成树时，找到了最小边需要判断是否会成环（若成环则不并入）

概念介绍：

1、并查集：

        并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

2、克鲁斯卡尔算法

        在图中按照权值的大小顺序选择n-1条边；将图中的n个顶点构造为n个只含有一个节点的树，按照权值的大小选择边加入n棵树构成的森林中，直至森林变成一棵树。

判断方法：

        当我们加入一条边时，判断这条边的邻接点的根节点是否相同。如果这两条邻接点可以追溯到同一个根节点，则证明，加入这条边成环了，那么我们就不并入这条边。否则，保留这条边进行下一步分析。

1、下图为分析的图（上）和它的并查集，我们将它的并查集视为一棵棵树

2、 最短边（A1,A2）的两个顶点不在同一棵树（邻接点没有相同的根节点，在并查集中可以观察到），将其并入，并在并查集中将A1、A2构成一棵树

3、最小边（A2,A5） 的两个邻接点不属于同一棵树（邻接点没有相同的根节点），将其并入，并在并查集中将A5、A2构成一棵树

4、 最小边（A3,A4） 的两个邻接点不属于同一棵树（邻接点没有相同的根节点），将其并入，并在并查集中将A3、A4构成一棵树

 5、接下来最小边（A2,A3）的两个邻接点不属于同一棵树（在并查集中A2和A3所在的树没有相同的根节点），将其并入，并在并查集中将A2，A3所在树连接构成一棵树

 6、从并查集可观察到，接下来最小边（A3,A5）的两个邻接点A3,A5有共同的根节点，所以不并入，不生成树

7、从并查集可观察到，接下来最小边（A1，A4）的两个邻接点A1,A4有共同的根节点，所以不并入，不生成树

8、接下来的最小边（A5,A6）的两个邻接点A5,A6没有相同的根节点，所以将这条边并入，并在并查集中生成树

9、我们可以看出并查集中只有一个树，这个时候就说明已经生成了最小生成树

 注意事项：

        并查集的作用是辅助我们去判断两个邻接点是否有相同的根（在并查集观察更加直观），如果不使用并查集直接从生成树寻找是否是具有相同的根节点也可以

这篇关于利用克鲁斯卡尔算法判断最小生成树是否成环的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！