以最便宜的边缘成本从多图中提取树

-1

我想要这样，我有每个节点的4个边，并且有附加成本。假设我有a，b，c和d节点。并且我有成本附加到它以这种方式，如果我在节点的顶部，下部，左侧或右侧连接了b个节点，那么它们对于每个边连接的成本都不相同。现在我想要一棵树给我最小的生成树成本？如果您想要进一步xplaination然后我可以提供你只是给我发消息。以最便宜的边缘成本从多图中提取树

来源

2015-09-06 Ahmed Ashraf Butt

我对每个节点都有4条边，并且有附加成本。

这就是我们所说的加权图。

现在我想要一棵树给我最低成本生成树？

为此目的有几种算法，解释它们将远远超出SO的目的。通常，这些算法在“算法&数据结构” - 如课程中讨论。

查看Prim's，Kruskal's ...算法。我个人最喜欢的是Kruskal算法，因为它很容易实现并且相对高性能（O（E log V），E =＃边缘，V =＃节点）。

Here是一些算法。

如果你想进一步xplaination，那么我可以提供你只是给我发消息。

我们不打算为您实施它。看看我指出的算法，他们不应该很难实现。如果您采用克鲁斯卡尔算法，您只需执行或搜索set数据结构（支持调用union和find）的实现。一旦你拥有了设定的数据结构，实现Kruskal将会很简单。

来源

2015-09-06 09:58:37 HyperZ

尊敬的先生，我不希望任何人实现它。我知道krushkal，prims算法。但我认为你没有正确地得到我的问题。我想从多图中找到最小生成树即更具体的每个节点都有4条边。我只想知道算法的名称。 –

我没有看到解决方案会有什么不同，因为每个节点都有4条边。它仍然是一个图形，这就是这些算法的工作原理（也许你可以使用每个节点有4个边的信息来选择更高性能的算法或改进算法，然而Prim's，Kruskal's ...算法仍然可用。 – HyperZ

亲爱的主席先生， Prim和krushkal算法是贪婪算法。他们不保证你成功，但它会给你贪婪的结果。我想确保结果是100％肯定的。这就是这两个算法不起作用的原因我。 –

以最便宜的边缘成本从多图中提取树

回答

相关问题