24

Prim 和 Kruskal 的算法用于找到连通图和无向图的最小生成树。为什么不能在有向图上使用它们？

4

2 回答 2

37

这些算法首先起作用是一个小奇迹——大多数贪婪算法只是在某些情况下崩溃和烧毁。假设您想使用它们来找到最小跨度树状结构（从一个顶点到所有其他顶点的有向路径），那么 Kruskal 的一个有问题的图如下所示。

 5
  --> a
 /   / ^
s   1| |2
 \   v /
  --> b
 3

我们将采用成本 1 的 a->b 弧，然后卡住了，因为我们真的想要成本 3 的 s->b 和成本 2 的 b->a。

对于 Prim 来说，这张图是有问题的。

 5
  --> a
 /   /
s   1|
 \   v
  --> b
 3

我们将采用成本为 3 的 s->b，但我们确实想要成本为 5 的 s->a 和成本为 1 的 a->b。

于 2014-03-26T01:11:52.087 回答
14

Prim 和 Kruskal 的算法为连通图和“无向”图输出最小生成树。如果图没有连接，我们可以调整算法以输出最小生成森林。

在 Prim 算法中，我们将图划分为两组顶点。一组已探索的顶点已经形成了一个 MST（Set 1），另一组未探索的顶点最终将加入第一组以完成“spanning”（Set 2）。在每一时刻，我们在连接两个不相交集的切割中选择一个最小加权边缘。如果从 MST 的已探索节点到剩余的未探索节点没有有向边，即使 MST 中存在从未探索节点到已探索节点的边，算法也会卡住。

在 Kruskal 算法中，想法是按边的权重升序对边进行排序，然后按顺序将它们挑选出来，如果它们尚未与任何已探索节点形成循环，则将它们包含在已探索节点/边的 MST 中。这是使用联合查找数据结构完成的。但是这种方法无法检测有向图的循环。例如，包含边 [1->2] [2->3] [1->3] 的图将被报告为包含使用 Union-Find 方法的循环。

所以 Prim 失败了，因为它假设每个节点都可以从每个节点到达，尽管对于无向图有效，但对于有向图可能不正确。Kruskal 的失败是因为未能检测到循环，有时必须添加边制作循环以满足 MST 的“最小”加权属性。

此外，在有向图的情况下，MST 并不完全有意义。它与有向图的等价物是“最小跨度树状结构”，它将产生一棵树，其中每个顶点都可以从单个顶点到达。

于 2016-02-28T17:38:38.910 回答