2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。
我用Prim算法找到了最小生成树。。
我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树吗？
浏览 1提问于2019-03-17得票数 0
回答已采纳
2回答
考虑到我们试图将prim算法应用于不连通图上。考虑这个不连通图有顶点a，b，c和d，其中这个顶点d是不连通的。现在我需要检查我的理解，如果我们在这个不连通图上应用prim算法，算法不会到达顶点d，因此只返回a，b和c点的MST。那么，这个假设是对的吗？
浏览 4提问于2020-03-29得票数 0
当我找到一个“临界边缘”问题的解决方案时，我遇到了这个问题。我已经解决的最初(C++)问题是：
考虑一个图G=(V，E)。找出有多少边属于所有的 MST，有多少边不属于属于任何MST，有多少边属于一些MST，但不是全部。
让我们分别将“绿色”、“红色”和“黄色”称为上述3种情况下的边缘。
在进行我的研究之后，我偶然发现了，它解决了这个问题。一个将运行Kruskal算法的修改版本:如果两个或多个相同权重的边缘连接相同的组件，从而形成一个循环，那么所有这些都是黄色边缘，即可以包含在MST中的边缘(或不包括)。无可争辩地被选中的边缘是“绿色”的，在同一组件中创建循环的边缘是“红色”的。原来的
浏览 3提问于2014-12-31得票数 4
回答已采纳
我正在做我的研究，并继续问一个问题：
我有一个最小生成树(prim算法)，现在我的树中的一个节点被删除了，我想知道是否有一种方法可以重新组织我的树，使它仍然保持最优性？
我在这里寻求一些建议，我将感谢你的帮助。
谢谢!
注:所有边权值为1(单位图)。
浏览 0提问于2011-03-23得票数 6
1回答
假设我们有一个无向图G=(V，E)，我们有两个节点S和X。
我们能给出一个算法，使从S到X的路径上的边的最大权重最小化吗？注意，这不是最短路径算法，因为我们对最小化它们的和不感兴趣。
这个算法的复杂度是多少？
最小生成树算法(如Prim)是否是该问题的解决方案？
浏览 0提问于2018-11-14得票数 0
我正在修改一个测试，并遇到了两个问题，与最小生成树在图中，我不确定，并想测试我的答案。
第一个问题是:如果一个图有多个最小生成树，那么Kruskal和Prim的最小生成树算法会生成相同的树吗？我认为它们不一定是因为算法不同而产生的。Kruskal依赖于按权重排序的边，而Prim则不这样做，因此它们可以从不同的顶点开始，从而生成不同的树。
第二个问题是:如果一个图有多个最小生成树，那么Kruskal的算法应该如何才能产生所有这些？我认为，我们需要允许一个循环结构穿过顶点，这样开始顶点每次都会发生变化，因为边缘值可能是相同的。因此，通过将每个顶点依次作为起始顶点来生成树。换句话说，按顶点编号进行排
浏览 3提问于2014-04-29得票数 2
回答已采纳
2回答
我不想找到所有的最小生成树，但是我想知道其中有多少树，下面是我考虑过的方法：
用prim或kruskal算法求出最小生成树，然后求出所有生成树的权值，当最小生成树的权重等于最小生成树的权重时，增加运行计数器。
我找不到任何方法来求出所有生成树的权重，而且生成树的数目也可能很大，所以这种方法可能不适合这个问题。由于最小生成树的数目是指数的，将它们计算起来不是一个好主意。
所有的重量都是正数。
我们还可以假设，在图中不会出现超过三次的权重。
顶点的数目将小于或等于40,000。
边数将小于或等于100,000。
图中只有一个最小生成树，其中顶点的权重是不同的。我
浏览 4提问于2012-12-13得票数 9
回答已采纳
1回答
加权有向图的Prim算法
、、、
我在学习最小生成树。我研究了Prim关于加权有向图的算法。
算法简单
您有两个顶点集，已访问的和未访问的。
将所有边的距离设为无穷远
从未访问集中的任意顶点开始，并探索其边缘。
在所有边缘中，如果目标顶点没有被访问，并且如果边缘的权重小于目标顶点的距离，则使用该边缘的权重更新目标顶点的距离。
选择距离最小的未访问顶点，然后再做一次，直到所有顶点都被访问。
通过上述算法，我可以在所有的生成树中找到代价最小的生成树，即最小生成树。
但是我把它应用到下面的例子中，我认为它失败了。
请考虑以下示例
顶点是{v1，v2，v3，v4，v5}和带权的边。
(x，y)：W
浏览 2提问于2014-03-18得票数 0
1回答
空间高效的最小生成树
、、、、
我遇到了一个任务，基本上是要求你找到给定图的MST，其中所有的顶点都是相连的。我尝试使用Kruskal的算法，但我很快就发现空间限制太紧，无法以兆字节存储所有的边，所以我也放弃了Prim和Boruvka的算法。有没有办法实现这些算法(或任何其他MST算法)，空间复杂度比O(E)更好，在本例中是O(V^2)？
浏览 4提问于2018-06-12得票数 2
Prim和Kruskal的算法用于寻找连通和无向图的最小生成树。为什么不能在有向图上使用它们呢？
浏览 1提问于2014-03-26得票数 23
回答已采纳
我认为这是真的。考虑到Prim的算法，顶点的最小边缘要么已经在树中，要么最终会被选择。
我也尝试了很多图表，它们看起来都是正确的。
如果这句话是假的，谁能给我举个反例？
谢谢。
浏览 3提问于2022-03-25得票数 0
回答已采纳
2回答
我试图将Prim或Kruskal的算法应用于某些情况。据我所知，当图是稠密的时使用Prim (例如:作为具有优先级队列的邻接矩阵作为无序数组，对于E = O(V^2)中的稠密树是很好的。当图稀疏时使用Kruskal (例如:在E = O(V)中作为具有快速排序的邻接列表)。我不确定的是两者之间。例如，一个边数适中的图，
E = O(V log V)
是Prim还是Kruskal？我认为这可能是因为Prim O(E log V)和Kruskal O(E log E)有相似的时间复杂性。
浏览 0提问于2018-11-26得票数 0
回答已采纳
1回答
我正在阅读有关最小生成树算法的文章。这里提到了cut。无向图G= ( V，E)的割集(S，V-S)是V的一部分，如果它的权重是与割线相交的任何边的最小值，则称它是与割线相交的一条轻边。
上述定义在Kruskal和Prims算法中是如何使用的？
我不明白在Kruskals和Prim的算法中cut是如何使用的
谢谢
浏览 1提问于2011-11-25得票数 0
回答已采纳
假设您使用Kruskal或Prim的算法来计算第一个MST，您希望检查是否还有其他的MST。我可以在O(E/V)时间内做到这一点。
该算法使用了一个优先级队列(可以用O(N)构造)。Kruskal和Prim已经使用优先级队列，但它们比下面列出的线性时间算法慢。
我知道已经有一些算法可以在线性时间内找到单个MST：
随机算法可以在线性期望时间内求解。Karger，Klein和Tarjan，“寻找最小生成树的随机线性时间算法”，J. ACM，第42卷，1995年，第321-328页。
当权值为小整数时，可在线性最坏情况下求解。弗雷德曼和威拉德，“最小生成树和最短路径的跨-二重算法”，第31
浏览 2提问于2013-12-20得票数 0
回答已采纳
我想知道对于dijkstra和prim的算法，当他们在多个顶点之间进行选择时会发生什么，并且有多个顶点具有相同的权重。
例如
浏览 1提问于2010-04-28得票数 5
1回答
求循环图的最小加权生成树
、、、
我正试图解决上述问题，以下是我的尝试：
尝试：我们可以使用Dijkstra的最短路径算法代替Prim和Kruskal的算法来寻找MST，因为Dijkstra将访问最小加权距离内的所有节点。复杂度:对于G= (V，E)，O(E log(V))
问题：
(1)我的方法正确吗？(2)这是否最有效的答案？
如果我完全错了，我会感激一个正确有效的解决方案。
浏览 2提问于2015-12-15得票数 0
回答已采纳
1回答
我试图实现Prim的算法，一个由城市作为顶点组成的图，但我被卡住了。如有任何建议，将不胜感激。
我正在从txt文件中读取数据，并试图获得分数(总距离)的输出和元组中的边缘列表。例如，从休斯顿开始，第一个优势将是(‘休斯顿’，‘圣安东尼奥’)。
我使用具有相邻顶点及其距离的字典实现了图/树，如下所示：
{'HOUSTON': [('LUBBOCK', '535'), ('MIDLAND/ODESSA', '494'), ('MISSION/MCALLEN/EDINBURG', '346'
浏览 3提问于2019-11-12得票数 2
1回答
假设我们得到了
一个无向图g，其中每个节点i,1 <= i<n都连接到所有j，i<j <=n
和一个源s。
我们希望找到与s最小距离树(即在s上运行prim/dijkstra获得的最小距离树)不同的最便宜最小生成树的总成本(定义为所有边的权重之和)。
解决这个问题的最好方法是什么？因为目前，我只能想到某种定点迭代。
在(g,s)上运行dijkstra以获得我们需要与之不同的参考图r
costs := sum(edge_weights_of(r))
change := 0
对于r中的每个顶点v，运行一个bfs，并对每个到达顶点v(从u到v的路径上最长的边)
浏览 2提问于2015-12-27得票数 1
4回答
正如我的问题所说，我想知道为什么我们要在中使用优先级队列？它如何将我们从天真的方式中拯救出来(是的，我听说过，但不知道为什么)。
如果有人能一步一步地解释邻接表，我会很高兴的。我在用科尔曼的书。
伪代码：
Prim(G,w,r) //what is w (weight?) and r?
For each u in V[G]
do key[u] ← ∞ // what is key?
π[u] ← NIL
key[r] ← 0
Q ← V[G]
While Q ≠ Ø
do u ← EXTRACT-MIN(Q)
for each
浏览 0提问于2011-08-12得票数 6
回答已采纳
3回答
如果使用邻接矩阵表示，Prim算法的时间复杂度为O(|V|^2)。
我试图用邻接矩阵实现Prim的算法。我正在使用作为参考。
V = {1,2...,n}
U = {1}
T = NULL
while V != U:
/*
Now this implementation means that
I find lowest cost edge in O(n).
How do I do that using adjacency list?
*/
let (u, v) be the lowest cost e
浏览 4提问于2010-08-06得票数 5
我希望有人能给我一个通用的方法来计算MST的问题，从输入是这样的：
<number of vertices>
<x> <y>
<x> <y>
...
我知道如何实现prim的算法，但我正在寻找一种(使用prim的算法)需要最少内存/时间来执行的方法。我应该把所有东西都存储在邻接矩阵中吗？如果顶点的数量增长到10,000，那么解决这个问题的最佳方法是什么(假设使用了prim)？
浏览 4提问于2013-04-19得票数 4
我有一个为我的一个项目构建的邻接矩阵，并且我需要能够从该矩阵构建最小生成树。从周围的阅读来看，Prim的算法看起来是最适合这种情况的，但是我们不能假设这个图是一个大的连通分量，因为我知道我们必须处理的图中至少有一个有几千个连通分量。Prim的算法在这里还可行吗?如果可行，我还需要做什么吗？
我在这里用Java编写代码，我可以很好地构造邻接矩阵，只是我被这部分卡住了。
浏览 4提问于2011-05-04得票数 1
实际上，我想知道prim和Dijkstra算法的含义。如果有人能教我如何用JAVA编写它，我将不胜感激。我试着理解某人的prim算法代码，但我在某个地方卡住了。
下面显示的代码是一个随机矩阵。我想继续写素数的算法。有谁能帮上忙吗？
import java.util.*;
class RandomGraph
{
public static Scanner br = new Scanner(System.in);
static int w [][];
static int n;
static int i, j;
public static void
浏览 0提问于2013-08-02得票数 0
回答已采纳
我要解决一个类似这样的问题：
给我一个N，代表我所拥有的点数。每个点有两个坐标：X和Y.
我可以用以下公式找出两点之间的距离：
abs(x2-x1)+abs(y2-y1)，
(x1，y1)是第一个点的坐标，(x2，y2)是第二个点的坐标，abs()是绝对值。
我必须找到最小生成树，这意味着我必须有我所有的点与边之和最小。Prim的算法很好，但速度太慢了。我读到使用可以使它更快，但我没有找到任何解释如何做到这一点的文章。
有谁能解释一下Prim的算法是如何与堆一起工作的(一些示例代码可能是好的，但不是天生的)？
浏览 1提问于2014-12-29得票数 0
回答已采纳
1回答
我在坐标平面上有n个点构成一个完整的图，边的权重是abs(x1-x2)+ abs(y1-y2)。我必须找出最小生成树的代价，我已经用Prim的算法做了，时间复杂度是O(n^2)有没有更好的方法来做这件事。
浏览 0提问于2020-10-08得票数 1
1回答
我想从这个图中知道Prim算法的顶点顺序：
我的答案是{a,c,b,e,f,g,d}，但也有人说是{a,c,b,e,d,f,g}或{a,c,d,e,b,f,g}。
哪个答案是正确的？
浏览 2提问于2016-12-16得票数 1
3回答
我的项目是使用java实现最小生成树。我的目标是使用Prim的算法来完成任务。
图的定义是G= ( v，E)，其中V是管脚的集合，E是管脚对之间可能的互连的集合，并且对于E中的每条边(u，v)，我们具有指定连接u和v的成本的权重w(u，v)。
我的想法是使用两个哈希图。首先将pin作为关键字，并将邻居列表作为值。第二个hashmap将把边(u，v)的列表作为关键字，其值将是它的权重。
你认为存储图表的最好方法是什么？
浏览 0提问于2012-03-30得票数 1
回答已采纳
1回答
对于有向图，JGraphX中是否有返回最小生成树形的方法？
我一直在使用getMinimumSpanningTree方法，为“有向”参数设置“true”，但实际上是Prim的算法，在一些有向图上失败了。
浏览 7提问于2015-01-05得票数 0
回答已采纳
我一整天都在努力理解Dijkstra的算法，并实现了，但没有明显的结果。我有一个城市及其距离的矩阵。我想要做的是给定一个起点和一个终点，找到城市之间的最短路径。
示例：
__0__ __1__ __2__
0 | 0 | 34 | 0 |
|-----|-----|-----|
1 | 34 | 0 | 23 |
|-----|-----|-----|
2 | 0 | 23 | 0 |
----- ----- -----
我开始想知道是否有其他方法来解决这个问题。如果我从原点开始应用Prim算法，然后遍历创建的整个树
浏览 2提问于2011-03-21得票数 4
回答已采纳
3回答
我目前正在优化电网规划，而MST没有很好地解决这个问题，因为如果到主电网的连接是一个辐射点，所有的电力都必须流经一条边，并将经过很长的“电气距离”到达每个耗电量点。
我正在研究的问题可能是最小化MW*distance或有功功率矩，但这会产生一个非线性问题。
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的距离)。
通过这种方式，我只是购买更长更细的电缆，这是一种更便宜的解决方案，较短，较厚的电缆。
浏览 1提问于2013-06-27得票数 6
2回答
我正试着把一些真假的问题做完。当我用真实的答案回答他们时，我很担心.请假定所有图都是无向，do 而不是具有不同的权重。负重应该可以。
Qa)如果G有一个具有唯一最重边e的循环，那么e不能是任何MST的一部分。
我的回答是对的。例如，我们有一个有节点A，B，C，D，E的图。
AB = 1
BC = 2
BD = 3
CD = 100
DE = 4
正如你所看到的，BCD是一个循环。我的论点是，由于这是一个循环，我们总是可以避免唯一最重的边CD通过其他路线。因此，这是真的。我的论点听起来够了吗？
由Dijkstra算法计算的最短路径树必然是MST.
我的答案是正确的，但我的直觉告诉我有什么不对劲。
浏览 3提问于2011-10-29得票数 2
3回答
我正在尝试用JGraphT实现Prim的最小生成树算法。看起来怎么样？
我遇到的一个问题是JGraphT按照指令处理一切。因此，如果g.getEdgeSource(e)和g.getEdgeTarget(e)不是正确的，有时有必要进行一些笨拙的调用来反转它们。
我最初试图用JGraphT的Fibonacci Heap实现它，但它太难了，所以我只是做了一个常规的PQ。
我没有将不存在的边的权重设置为无穷大，只是没有将其添加到队列中。
建议？风格问题？明显的低效？我应该使用的代码而不是我自己的代码？
public static Graph<String, DefaultWeightedEdge
浏览 1提问于2009-11-24得票数 1
3回答
有没有人知道如何改变prim的算法，从而处理一个没有连通的图？我知道我必须使用森林，但我不知道如何在Haskell中实现它。
浏览 3提问于2011-12-12得票数 0
3回答
我有一个无向，正边权图(V，E)，我想要一个最小生成树覆盖一个顶点的子集k( Steiner树问题)。
我并不是将生成树的大小限制为k个顶点，而是确切地知道在MST中必须包含哪些k个顶点。
从整个MST开始，我可以缩小边缘/节点，直到得到包含所有k的最小MST为止。
我可以使用Prim的算法获得整个MST，并在子集k的MST未被破坏的情况下开始删除边缘/节点；或者，我可以使用Floyd获得所有对最短路径，并以某种方式合并路径。有没有更好的方法来解决这个问题？
浏览 5提问于2011-10-07得票数 44
3回答
我试图使用prim的算法创建一个最小生成树，并且我有一个关于实际堆的主要问题。我把我的图的邻接列表构造成一个顶点向量，每个顶点都有一个边向量。边缘包含一个权重、一个连接顶点和一个键。我不确定我的堆应该是一个顶点堆还是边堆。如果我把它变成一个顶点堆，那么就无法确定权重是否来自同一个父顶点和目标顶点，这使我认为我应该为每个顶点列表创建一个边堆。因此，我的最后一个问题是，我应该创建一堆边缘，还是一堆顶点？如果是边的列表，我应该使用边上的权重作为键，还是应该有一个单独的名为key的数据成员，可以实际用于优先级队列？谢谢!
浏览 0提问于2013-12-14得票数 0
回答已采纳
我在codechef中看到了一个问题，它的目标是从图中选择边，使选定的边不形成一个循环，并且所有所选边的权积也是maximum.In，编辑给出了prim和kruskal算法工作的here.Infact，并给出了使边的任意对称单调函数最大化的工作原理。那么，什么是对称单调函数，我们还可以在哪里使用这些算法。
浏览 1提问于2015-08-01得票数 0
回答已采纳
2回答
无向图MST算法(Prim或Kruskal)是有向MST算法(Edmond/Chiu)的一般形式吗？为什么很难找到定向情况下的MST源代码？我们可以使用无向解来获得有向图中的MST吗？
这与以下内容相关：
浏览 6提问于2015-01-16得票数 8
回答已采纳
1回答
可以使用Prim算法或Kruskal算法来寻找顶点/节点和边/链路的集合的最小生成树/图。我想要的是找到这个集合的最小生成图的算法，但是结果图只需要包括任意选择的节点，而不是所有节点。如果结果图包含比所需节点更多的节点，这是可以的。
这样的算法存在吗？也许在修改图以仅包括所需节点后，可以只使用Prim(或Kruskal)算法？但是，我不确定如何修改图形来做到这一点，同时保持它的连通性。
例如，假设我们有一个菱形的起始图(在括号中有链接的成本)：
A
(2)/ \(1)
B C
(2)\ /(5)
D
现在，我们任意决定只需要节点A和D。如果我们从A开始，我们仍然希望它走
浏览 1提问于2012-10-31得票数 7
回答已采纳
3回答
所有最小生成树的实现
、、、、
我一直在寻找一个实现(我正在使用库)。这将找到一个无向加权图的所有最小生成树(MST)。
我只能找到Kruskal算法和Prim算法的实现，这两种算法都只返回一个MST。
我看过解决这个问题的论文(比如)，但我的头在思考如何将其转换成代码时往往会以某种方式爆炸。
事实上，我找不到任何语言的实现！
浏览 1提问于2010-05-30得票数 23
1回答
我得找出堵车的降雨门槛。
所以，我必须打印降水的阈值来阻止交通。
(前)
3 3
0 1 2
1 2 3
0 2 6
产出:3
对于这个问题有什么好的算法或关键字吗？
谢谢
浏览 0提问于2019-04-02得票数 1
回答已采纳
2回答
给定一个带权的无向连通图。w:E->{1,2,3,4,5,6,7} -意味着只有7个权重。我需要使用O(n+m)中的Prim算法和O( m*a(m，n))中的Kruskal算法找到一棵生成树。
我不知道如何做到这一点，真的需要一些指导，如何权重可以帮助我在这里。
浏览 4提问于2012-05-28得票数 0
如果最小生成树是贪婪的，为什么Kruskal的算法会找到它呢？最小生成树不是一个全局优化问题吗？贪婪的意义不是在于你有可能找不到最优的解决方案吗？那么，Kruskal如何在贪婪的情况下找到最小生成树呢？
浏览 2提问于2016-12-10得票数 5
2回答
我有一个问题：
给定无向图G= (V，E)，V∋v和非负权W，求出存在最小生成树，其中v是叶，如果有，则返回它。
我考虑用prim算法找到MST，并检查v是否是其中的一片叶子。如果v不是叶子，我会找到第二个MST并检查它。问题是时间的复杂性会太高。我相信还有另外一种方法来解决这个问题，但我不知道如何解决。你能给我一些关于如何处理这个问题的线索吗？
浏览 0提问于2020-01-23得票数 1
回答已采纳
1回答
请帮助理解prims，所有伪码(如在核心和维基) 。
MST-PRIM (G, w, r) {
for each u ∈ G.V
u.key = ∞
u.parent = NIL
r.key = 0
Q = G.V
while (Q ≠ ø)
//1
u = Extract-Min(Q)
for each v ∈ G.Adj[u]
if (v ∈ Q) and w(u,v) < v.key
v.parent = u
v.key = w(u,v)}
我能理解到直到1或同时循环，r.key=0保证首先扫描根的近邻或邻接，但由于u已经属于Q (到目前为止还不包括在素数最小生成树
浏览 2提问于2014-10-22得票数 0
1回答
我正在阅读一本算法教科书，以提高我的算法技能，但我在这个问题上完全被困住了，这让我很困扰。我认为底层的数据结构是一个图表，但我甚至不知道从哪里开始这个问题。有人能给点见解吗？谢谢
给出了一个地形图，该地形图提供了任意两个相邻城市和两个城市a和b之间的直接道路上的最大高度。提出了一个线性时间算法，该算法可以找到从s到t的路径，从而使最大高度最小化。道路可以双向通行。
浏览 3提问于2013-10-01得票数 1
1回答
有没有人能解释一下，在PRIM的处理最小生成树问题的算法中，我们为什么要使用键数组(即key[])，或者使用键数组的重要性是什么？
PRIM_MST(G,W,R)//G->graph,W->weighted matrix,R->root vertex
-------------------------
for v<-v[G]
key[v]<-infinity
pred[v]<-NIL //pred[]-->predecessor array
key[v]=0
Q<-v[G] //Q-->p
浏览 1提问于2013-08-01得票数 0
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
腾讯云开发者
