Prim算法和Kruskal算法之间的区别

在本文中，我们将了解Prim算法和Kruskal算法之间的差异。

最小生成树(MST)的Kruskal算法

• 给定一个连通图和无向图时，此类图的生成树就是子图，该子图是连接所有顶点的树。

• 单个图可以具有多个生成树。

• 加权图，连接图和无向图的最小生成树(MST)（也称为最小权重生成树）是一种生成树，其权重小于或等于其他所有生成树的权重。

• 生成树的权重是通过将与生成树的每个边缘关联的权重相加来确定的。

• 最小生成树可以从图中权重最小的顶点构建。

• 一个节点仅被遍历一次。

• 它可以在稀疏图中快速运行。

• 时间复杂度为O(E log V)，其中V是顶点数。

• 它也可以与断开的组件一起使用。

使用Kruskal算法查找MST的步骤：

• 按其相关权重的升序对边缘进行排序。

• 选择最小的边缘。

• 检查它是否与在该时间点之前已经形成的生成树形成一个循环。

• 如果尚未形成循环，则必须包括该边。

• 否则，可以将其丢弃。

• 重复步骤2、3、4，直到生成树包含V-1边为止。

Prim的算法最小生成树(MST)

• 这类似于Kruskal算法，i.e它是一个贪婪算法。

• 它从一棵空的生成树开始。保留了两组顶点。

• 第一组包含已包含在MST中的顶点，而另一组包含尚未包含的顶点。

• 在每一步中，算法都会考虑将两组连接的所有边。然后，在这些边缘中选择最小的权重边缘。

• 此步骤之后，算法移至包含MST的集合边缘的另一个端点。

• 最小生成树可以从图中的任何顶点构建。

• 一个节点经过多次移动以获得最小距离值。

• 它的时间复杂度为O(V2)，其中V是顶点数。使用斐波那契堆可以将此时间复杂度提高到O（E + log V）。

• 它可以在密集图形中快速运行。

• 它提供了连接的组件，并且仅与连接的图形一起使用。

使用Prim's算法查找MST的步骤：

• 创建了一个mstSet，该跟踪记录了MST中已经包含的顶点。

• 键值分配给输入图的所有顶点。

• 键值最初分配为“ INFINITE”。

• 将键值0分配给第一个顶点，以便可以首先选择它。

• 当mstSet不包括所有顶点时，请执行以下步骤。

• 选择的顶点'u'在mstSet中不存在，并且具有最小的键值。

• 现在，此“ u”包含在mstSet中。

• 'u'的所有相邻顶点的键值都会更新。

• 这可以通过迭代所有相邻的顶点来完成。

• 对于每个相邻顶点“ v”，如果边“ u”-“ v”的权重小于先前键值“ v”的权重，则将键值更新为“ u-v”的权重。