minimum-spanning-tree

0热度

1回答

我有一个图G =（V，E），其中有两个权重函数w1（e）和w2（e），其中 w1（e）=（w2（e））^ 2。所有边缘权重都是独一无二的。在两个权重函数下，Kruskal的算法将返回相同的最小生成树。我知道kruskal是贪婪的，会选择最短/最低成本的路径。既然它们是肯定的，只要没有成本为1.5或者更低的路径，我们最终会选择相同的MST。在两个权重函数下，Dijkstra的算法将返回相同的

1热度

1回答

最小生成树使用Kruskal算法

我使用Kruskal算法来完成确定后问题的最小生成树的分配：我有个城市，而这一切都必须连接。我可以通过在它们之间修建道路或建造一个机场来连接它们。当我在城市建造一个机场时，它会连接到所有其他有机场的城市。我的疑问是，在未来的要求：在不止一个最佳的解决方案的情况下，我必须选择一个具有较少的机场。我如何以最有效的方式保证这一点？

0热度

1回答

阵列列表中的最小生成树

我想知道是否有可能从ArrayList中找到最小生成树。这是我目前有： import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Scanner; public class GraphReading { public static

-1热度

1回答

如何利用普里姆算法找到如下图的最小重量生成树

Prim算法查找最小生成树算法。首先选择权重最小的任意边缘，将其放入生成树中。继续向树中已经存在的最小权重的树边添加树，从不形成树中已有边的简单电路。停止添加n - 1个边。我知道你必须从节点A开始。同时给出一个列表中添加节点和/或边的顺序。但我不知道确切的步骤来找到最小权重生成树。

-1热度

1回答

有人能解释如何的std ::更大的用于实现priority_queue

std::priority_queue<int, vector<int>, std::greater<int> > pq; 我不明白性病的工作::越大优先级队列。我正在用优先级队列替换minheap。此代码取自 geeksForGeeks implementation of Prims algorithm using STL

1热度

1回答

MST in unDirected graph

我有一个未排序的图G =（V，E）和权重函数w：E→R +。我也有G的MST T. 我必须建立一个如下算法：如果我们添加一个具有权重w（e'）的新边e'给E.建议一个算法它以新图G'=（V，EUe'）的MST的方式更新T. 复杂度：O（V）。什么我建议是： 1）添加E“到T.我们得到了一个新的图形称之为T”，其中包括一个周期。 2）在T'上运行DFS并标记您访问的每个顶点。并且另外保存堆栈中的

0热度

1回答

Prims算法：图论

下面是我的代码为Prims算法，我写我自己的链表，因为我已经被要求。它适用于较小数量的顶点，但是当顶点很大时它失败（我得到812800作为所有大数字的顶点的答案）。输入格式：第一行有两个整数，表示图中的节点的数目和，表示在图中的边缘的数目。下一行每个由三个空格分隔的整数组成，其中和表示无向边存在的两个节点，表示相应节点之间的边的长度。最后一行有一个整数，表示起始节点。如果同一对节点之间存

0热度

1回答

如何在二维平面中找到连接一组坐标的最小生成树？

我已经在python中编写了Prim的算法，但是这需要输入带有节点和边的加权图，这不是我所拥有的。如何将给定的坐标转换为图形，以便程序可以接受输入，并且我得到一个有意义的答案？

0热度

1回答

Prim算法的最坏情况图

我的算法类正在讨论Prim算法，作为查找加权图的最小生成树的方法。我们的教授让我们试着想一个Prim算法需要N^2次解决的图的例子（N =顶点数）。班上没有人能够想到他们的头顶，所以我问你。我很确定Prim的算法= O（N^2），所以这将是算法的最坏情况。什么是Prim算法需要N^2个时间才能解决的图的一个很好的例子？

-4热度

1回答

关于最小生成树图

是否有比Prime更好的算法（更优化，更快）？Kruskal's algorithms？