为什么不能在有向图上使用 Prim 或 Kruskal 算法? [英] Why can't Prim's or Kruskal's algorithms be used on a directed graph?

问题描述

Prim 和 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?

推荐答案

这些算法一开始就工作是一个小奇迹——大多数贪婪算法只是在某些情况下崩溃和烧毁.假设您想使用它们来找到最小跨度树状(从一个顶点到所有其他顶点的有向路径)，那么 Kruskal 的一个有问题的图看起来像这样.

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

我们将采用成本 1 的 a->b 弧，然后卡住，因为我们真的想要成本 3 的 s->b 和成本 2 的 b->a.

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.

对于 Prim，这个图是有问题的.

For Prim, this graph is problematic.

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

我们将采用成本 3 的 s->b，但我们确实想要成本 5 的 s->a 和成本 1 的 a->b.

We'll take s->b of cost 3, but we really wanted s->a of cost 5 and a->b of cost 1.

这篇关于为什么不能在有向图上使用 Prim 或 Kruskal 算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！