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

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

这些算法首先起作用是一个小奇迹-

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

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

我们将采用成本1的a-> b弧，然后陷入困境，因为我们确实想要s-> b的成本3和b-> a的成本2。

对于Prim，此图是有问题的。

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

我们将s-> b的成本设为3，但我们确实希望s-> a的成本为5，而a-> b的成本为1。