这些算法首先起作用是一个小奇迹- 大多数贪婪的算法只是在某些情况下崩溃并烧毁。假设您要使用它们来查找最小的跨度树状结构(从一个顶点到所有其他顶点的定向路径),那么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。