Prim算法和Kruskal算法的区别

在这篇文章中，我们将了解Prim算法和Kruskal算法之间的区别。

Kruskal算法用于最小生成树 (MST)

  • 给定一个连通且无向的图，该图的生成树是连接所有顶点的子图，且该子图是一棵树。
  • 一个图可以有多棵生成树。
  • 对于一个加权的、连通的、无向的图，最小生成树 (MST)（也称为最小权重生成树）是一棵生成树，其权重小于或等于所有其他生成树的权重。
  • 生成树的权重是通过将与生成树中每条边关联的权重加起来得到的。
  • 最小生成树可以从图中权重最小的顶点构建。
  • 每个节点只遍历一次。
  • 它在稀疏图中运行速度很快。
  • 时间复杂度为 O(E log V)，其中 V 是顶点数。
  • 它也可以处理不连通的组件。

使用Kruskal算法查找MST的步骤

  • 按关联权重升序对边进行排序。
  • 选择最小的边。
  • 检查它是否与到目前为止形成的生成树构成环。
  • 如果没有形成环，则必须包含此边。
  • 否则，可以将其丢弃。
  • 重复步骤2、3、4，直到生成树包含V-1条边。

Prim算法最小生成树 (MST)

  • 这类似于Kruskal算法，即它是一种贪心算法。
  • 它从一个空的生成树开始。维护两组顶点。
  • 第一组将包含已包含在MST中的顶点，而另一组将包含尚未包含的顶点。
  • 在每一步中，算法都会考虑所有连接这两组的边。然后，它从这些边中选择权重最小的边。
  • 在此步骤之后，算法移动到包含MST的集合的边的另一端点。
  • 最小生成树可以从图中的任何顶点构建。
  • 一个节点被多次遍历以获得最小距离值。
  • 它的时间复杂度为 O(V2)，其中 V 是顶点数。使用斐波那契堆可以将此时间复杂度提高到 O(E + log V)。
  • 它在稠密图中运行速度很快。
  • 它给出连通分量，并且仅适用于连通图。

使用Prim算法查找MST的步骤

  • 创建一个mstSet，用于跟踪已包含在MST中的顶点。
  • 为输入图的所有顶点分配一个键值。
  • 键值最初设置为“INFINITE”。
  • 为第一个顶点分配键值0，以便可以首先选择它。
  • 当mstSet不包含所有顶点时，遵循以下步骤。
    • 选择一个不在mstSet中且具有最小键值的顶点“u”。
    • 此“u”现在包含在mstSet中。
    • 更新“u”的所有相邻顶点的键值。
    • 这可以通过遍历所有相邻顶点来完成。
    • 对于每个相邻顶点“v”，如果边“u”-“v”的权重小于“v”的先前键值，则将键值更新为“u-v”的权重。

更新于： 2021年3月2日

787 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告