普里姆的和Kruskal的算法用于查找一个图表,连接和无向的最小生成树。他们为什么不能用在被引导图?
Prim's and Kruskal's algorithms are used to find the minimum spanning tree of a graph that is connected and undirected. Why can't they be used on a graph that is directed?
推荐答案
这是一个小小的奇迹,这些算法在首位的工作 - 最贪心算法只是和好如初了一些实例。假设您想使用它们找到一个最小生成树树状(定向路径从一个顶点到所有其他人),再一个问题图的秩看起来是这样的。
It's a minor miracle that these algorithms work in the first place -- most greedy algorithms just crash and burn on some instances. Assuming that you want to use them to find a minimum spanning arborescence (directed paths from one vertex to all others), then one problematic graph for Kruskal looks like this.
5
--> a
/ / ^
s 1| |2
v /
--> b
3
我们将采取的A->成本1 b弧线,然后被卡住,因为我们真的想S->乙成本3和B->成本2。
We'll take the a->b arc of cost 1, then get stuck because we really wanted s->b of cost 3 and b->a of cost 2.
有关普里姆,这个图是有问题的。
For Prim, this graph is problematic.
5
--> a
/ /
s 1|
v
--> b
3
我们将采取S->乙成本3,但我们真正想要的S->成本5和A->的b成本1。
We'll take s->b of cost 3, but we really wanted s->a of cost 5 and a->b of cost 1.
相关推荐
最新文章