无向与有向图的最小生成树算法之间的区别是什么？

Question

无向图MST算法(Prim或Kruskal)是定向MST算法(Edmond/Chiu)的一般形式吗？为什么找到针对定向案例的MST源代码如此困难？我们可以使用无向解决方案在有向图中获取MST吗？

这与以下内容有关: 为什么不能在有向图上使用Prim或Kruskal的算法？

Answer 1

您的问题的核心似乎是在有向图中找到MST(技术上称为最佳分支或最小成本树状结构)的原因不同,因此比在无向图中找到MST更难.

Prim和Kruskal的算法都因切割属性而起作用.如果G =(V,E)是图形,那么对于G中的任何切割(S,V-S),如果存在与该切割相交的最低成本边缘{u,v},则该边缘必须属于所有MST G.不幸的是,这个属性在定向案例中并非如此.这是一个反例:

      2
  A ----> B
  |      | ^
1 |  -99 | | 1
  |      v |
  +-----> C

在这里,以A为基础的最低成本树木是这样的:

      2
  A ----> B
          |
      -99 |
          v
          C

但是,看一下切口({A},{B,C})这个切口的最低成本边缘是边缘(A,C),但是这个边缘没有出现在以A为根的任何最小成本的树枝上. .

如果没有cut属性,Prim的算法和Kruskal的算法都会失败.尝试在此处给出的图表上运行Prim算法,从节点A开始作为包含的节点.你将添加边(A,C),然后边(C,B),给出次优的树枝.现在,尝试在这里运行Kruskal的算法.您将首先添加边(B,C),然后添加边(A,C).不幸的是,这实际上并不是一个树状,因为它没有根节点.

寻找最小成本的树枝(Edmonds-Chu)的标准算法实际上可能与Boruvka的算法更接近.Boruvka的算法通过为每个节点同时选择连接到该节点的最低成本边缘并将其添加到候选MST来工作.然后,您将以这种方式形成的所有CC合并为单个节点,并重复此过程,直到您拥有树.

在定向情况下,只要边缘权重是不同的,该算法将永远不会引入一个循环(这是一个很好的练习来证明这一点),但在定向算法中并非如此.上面给出的图是一个很好的例子 - 如果你试试这个,你从A中选择(A,C),从C中选择(C,B),从B中选择(B,C),形成循环(B,C) ,B).Edmonds-Chu算法使用的校正通过将这些循环之一收缩到单个节点中,然后在缩减图中重复该过程并基于结果"取消"循环来工作.在这个意义上,它与Boruvka的算法类似,但经过适当的修改.

希望这可以帮助!