minimum-spanning-tree

0热度

2回答

我目前正在学习C语言，并且最近编写了一个程序来使用Prim算法找到最小生成树。这个程序工作正常，但需要每个边缘的成本（当然）。如果我想为大量的2D坐标（例如50）找到MST，我需要先找到点的欧几里得距离矩阵。我的问题是：这可以在没有计算的情况下在C中完成 distance = sqrt((x2-x1)^2+(y2-y1)^2) 对于每个单点，例如通过使用循环？我一直在尝试使用 arrayX

2热度

1回答

递归最小生成树算法

这是寻找最小生成树的正确算法。将图划分为2个等同连接的部分。找到它最小的生成树。用连接它们的最小边连接它们。我试图得到这个算法的反例，但是不能。

1热度

2回答

什么是最小叶生成树？

有人可以解释为最小的叶子生成树是什么吗？我很困惑，在生成树中究竟是一片叶子。我知道生成树包含简单的没有循环的路径，它跨越图G中的所有顶点，但是最小的叶是什么？

0热度

1回答

关于MST的一些问题

我现在正在学习最小生成树的主题，并且我理解它的大部分内容，但是我仍然有一些我不明白的东西。我正在处理无向加权图。首先，我知道找到MST花费O（E * log V）。现在，当我们处理平面图时，我想优化它到线性时间 - O（V + E）。其次，我看到了单位平方中有n个点的例子，并且我成功地证明了存在权重为O（sqrt n）的MST。问题是我找不到找到这个MST的算法。感谢所有，或者

0热度

2回答

克鲁斯卡尔算法如何贪婪？

据说Kruskal的MST构造算法是贪婪的，但算法选择全局最小值而不是局部最小值，而不像Prim算法。有人可以解释克鲁斯卡尔算法是如何被认为是一种贪婪的方法吗？

0热度

2回答

如何使用堆来优化Prim的最小生成树算法？

我必须解决一个类似这样的问题：我给了一个数字N来表示我拥有的点数。每个点具有两个坐标：X和Y 我能找到用下列公式两个点之间的距离： ABS（X2-X1）+ ABS（Y2-Y1），（ x1，y1）为第一点的坐标，（x2，y2）为第二点的坐标，绝对值为abs()。我必须找到最小生成树，这意味着我必须让所有的点与边的总和最小。 Prim的算法很好，但它太慢了。我读到，我可以使用heap使其更快，但

4热度

1回答

查找MST的关键边缘：可以使用修改后的Prim算法吗？

我遇到了这个问题，同时找到了一个“关键边”问题的解决方案。我已经解决的原始（C++）问题是：考虑图G =（V，E）。查找有多少边缘属于全部 MST，有多少边缘不是属于任何 MST和有多少边缘属于某些MST，但不是全部。让我们分别在上述三种情况下分别称为“绿色”，“红色”和“黄色”边缘。进行我的研究后，我遇到了Find all critical edges of an MST，它解决了这个问题

1热度

2回答

Prim算法得到图的最小生成树

我需要Prim算法问题的一些帮助：设T是由Prim算法得到的图G的最小生成树。让Gnew是通过添加至G新的顶点和配重一些的边缘，新的顶点与G中一些顶点，我们可以通过添加新的边缘T的一个构造Gnew的最小生成树获得的图？如果你回答是，请解释如何;如果不是，请解释原因。预先感谢您！

2热度

1回答

查找跨越给定的最小生成树的最小权重完整图形

让T =（V，E）是|V|顶点树和|E| = |V-1|边，具有已知成本。我们要构建一个最小权重完整图G =（V，E'）跨越牛逼其独特的最小生成树。示例：考虑以下树T。红色的边缘有给定的成本。虚线边将被添加以构造来自该树的完整图。最小重量完全图摹跨越牛逼其独特的MST如下：我试图找到一个（多项式时间）算法来生成该图。我期待的主要是小费，而不是完整的解决方案。到目前为止，我已经设计了以下算法

0热度

1回答

在Minimax路径寻找解决方案中寻找路径和最大称量的边缘？

我目前正在进行编程分配：给定大的加权无关图（1 < V < 2000, E < 100000）。沿着从“源”到点“目的地”的最小加权路径查找最大加权边缘。到目前为止我所得到的是将图存储在AdjacencyList（IntegerPair向量的向量中，其中第一个整数是邻居，第二个是边的权重）。我也用Prim算法获得的最小生成树： private static void process(int v