为什么不能在有向图上使用Prim或Kruskal的算法？

Question

Prim和Kruskal的算法用于查找连接和无向图的最小生成树.为什么它们不能用于指向的图形？

Answer 1

这些算法首先起作用是一个小小的奇迹 - 大多数贪婪的算法只会在某些情况下崩溃和烧毁.假设您想要使用它们来找到最小跨越树枝(从一个顶点到所有其他顶点的有向路径),那么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,但我们确实需要s-> a成本5和a-> b成本1.

Answer 2

Prim和Kruskal的算法为连接和"无向"图输出最小生成树.如果它没有连接,我们可以调整它们以输出最小生成森林.

在Prim的算法中,我们将图分成两组顶点.已经形成MST(Set1)的一组探索顶点和另一组未探测顶点将最终连接第一组以完成"跨越"(Set2).在每个瞬间,我们选择加入两个不相交集的切割中的最小加权边.如果没有探测到的MST节点的有向边缘仍然未被探索,即使从未探测的节点到MST中探索的节点存在边缘,算法也会卡住.

在Kruskal的算法中,我们的想法是按重量按升序对边缘进行排序,然后将它们按顺序拾取并将它们包含在MST探索的节点/边缘中(如果它们已经形成了已探索节点的循环).这是由Union-Find DS完成的.但是用这种方法检测有向图的循环失败了.例如:将报告包含边[1> 2] [2-> 3] [1-> 3]的图形包含具有Union-Find方法的循环.

所以Prim失败了,因为它假定,每个节点都可以从每个节点到达,虽然对于有向图,但对于无向图可能不是真的.Kruskal由于未能检测到周期而失败,有时必须添加边缘以使周期满足MST的"最小"加权属性.

此外,在有向图的情况下,MST并不完全合理.对于有向图的等价物是"最小跨越树状",它将产生一个树,其中每个顶点可以从单个顶点到达.