1回答
正如维基百科所说：
最小生成林是其连通部分的最小生成树的结合。
为了找到最小生成树，我们可以使用例如、或。
我们可以用什么算法来寻找最小生成森林？
浏览 2提问于2017-05-16得票数 2
回答已采纳
3回答
我目前正在优化电网规划，而MST没有很好地解决这个问题，因为如果到主电网的连接是一个辐射点，所有的电力都必须流经一条边，并将经过很长的“电气距离”到达每个耗电量点。
我正在研究的问题可能是最小化MW*distance或有功功率矩，但这会产生一个非线性问题。
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的距离)。
通过这种方式，我只是购买更长更细的电缆，这是一种更便宜的解决方案，较短，较厚的电缆。
浏览 1提问于2013-06-27得票数 6
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
1回答
我得找出堵车的降雨门槛。
所以，我必须打印降水的阈值来阻止交通。
(前)
3 3
0 1 2
1 2 3
0 2 6
产出:3
对于这个问题有什么好的算法或关键字吗？
谢谢
浏览 0提问于2019-04-02得票数 1
回答已采纳
如果最小生成树是贪婪的，为什么Kruskal的算法会找到它呢？最小生成树不是一个全局优化问题吗？贪婪的意义不是在于你有可能找不到最优的解决方案吗？那么，Kruskal如何在贪婪的情况下找到最小生成树呢？
浏览 2提问于2016-12-10得票数 5
1回答
聚类最小生成树的数据集
、、、
最近我遇到了最小生成树的概念，发现它在聚类中有一个应用程序。我正在寻找一个真实的数据集(最好是干净的)，它可以作为各种聚类算法的数据源。有一种信息表明，MST聚类在球面和非球面数据上工作得足够好。这就是为什么非球面数据集也被追求的原因。
我心目中的数据集应该包含地面真相信息(标签)，因此各种标志的有效性可以通过与WSS不同的东西来衡量。
浏览 1提问于2018-06-12得票数 0
回答已采纳
1回答
加权有向图的Prim算法
、、、
我在学习最小生成树。我研究了Prim关于加权有向图的算法。
算法简单
您有两个顶点集，已访问的和未访问的。
将所有边的距离设为无穷远
从未访问集中的任意顶点开始，并探索其边缘。
在所有边缘中，如果目标顶点没有被访问，并且如果边缘的权重小于目标顶点的距离，则使用该边缘的权重更新目标顶点的距离。
选择距离最小的未访问顶点，然后再做一次，直到所有顶点都被访问。
通过上述算法，我可以在所有的生成树中找到代价最小的生成树，即最小生成树。
但是我把它应用到下面的例子中，我认为它失败了。
请考虑以下示例
顶点是{v1，v2，v3，v4，v5}和带权的边。
(x，y)：W
浏览 2提问于2014-03-18得票数 0
1回答
我很难找到Dijkstra最小生成树的示例算法。我已经知道Dijkstra的单最短路径算法，但不知道生成树。我在课堂上有一个简单的解释，就是：
对于每个边缘，将其添加到树中。如果检测到循环，则移除最重的边缘。
我在互联网上搜索了一下，却找不到算法。
我可能需要为自己编写代码，但我想我会问是否有人有一个好的例子。
有人能帮忙吗？
浏览 0提问于2018-04-08得票数 4
回答已采纳
1回答
我需要得到一个完整图的MST，其中所有的边都默认为权重3，而且我还得到了有权重1的边。
下面是一个例子
5 4 (N, M)
1 5
1 4
4 2
4 3
Resulting MST = 3 -> 5 -> 1 -> 4 -> 2
如果第一行有总节点数(N)，则1权重边(M)的数量和以下所有行(M)都包含权重为1的边。
我试着构造一个完整的图并将给定边的权值更新为1，但是对于一个包含10^5 1权边的问题来说，空间复杂度太大了。
浏览 4提问于2021-11-28得票数 1
回答已采纳
1回答
我正在阅读一本算法教科书，以提高我的算法技能，但我在这个问题上完全被困住了，这让我很困扰。我认为底层的数据结构是一个图表，但我甚至不知道从哪里开始这个问题。有人能给点见解吗？谢谢
给出了一个地形图，该地形图提供了任意两个相邻城市和两个城市a和b之间的直接道路上的最大高度。提出了一个线性时间算法，该算法可以找到从s到t的路径，从而使最大高度最小化。道路可以双向通行。
浏览 3提问于2013-10-01得票数 1
我可以使用什么算法来解决这样的问题：
有一个图的正权重，我想知道每个节点连接的权重的最小和(像网络一样连接，其中每个节点是一个eg。网络设备)。
在这个网络中，每个节点都可以通过其他节点以某种方式与其他节点相连。但输入图中的所有节点都必须位于网络中。
浏览 1提问于2010-04-26得票数 0
回答已采纳
1回答
在加权图中将循环图转换为无圈图
、、、、
我得到了一个具有非负权重的连通加权图。我想把它转换成一个连通的非循环图，这样被移除的边的权重之和就会最小化。输出将是移除的边。 我的想法是:由于一个连通的非循环图是一棵树，我可以简单地获取最大的n-1边，然后删除所有其他边。但是，这并不总是正确的。它可能导致不连通的图。 然后，我想到了使用dfs。我知道如何使用dfs检测图是否有圈，但我不知道如何检测涉及到的所有边，以及如何将其转换为非循环图。任何帮助(代码/伪代码/文字中的算法)都将不胜感激。谢谢..。
浏览 36提问于2019-06-12得票数 1
回答已采纳
2回答
我不想找到所有的最小生成树，但是我想知道其中有多少树，下面是我考虑过的方法：
用prim或kruskal算法求出最小生成树，然后求出所有生成树的权值，当最小生成树的权重等于最小生成树的权重时，增加运行计数器。
我找不到任何方法来求出所有生成树的权重，而且生成树的数目也可能很大，所以这种方法可能不适合这个问题。由于最小生成树的数目是指数的，将它们计算起来不是一个好主意。
所有的重量都是正数。
我们还可以假设，在图中不会出现超过三次的权重。
顶点的数目将小于或等于40,000。
边数将小于或等于100,000。
图中只有一个最小生成树，其中顶点的权重是不同的。我
浏览 4提问于2012-12-13得票数 9
回答已采纳
1回答
当我看到时，这个问题突然浮现在我的脑海中。为了简单起见，我们可以将讨论限制在无向、加权、连通图上。显然，如果从图中选择任意节点作为源，Dijkstra不能保证生成MST。然而，它是否保证在一个无向、加权、连通图中必须存在一个节点，如果我们选择它作为源并应用Dijkstra的算法，它将为该图生成一个MST？也许你可以给出一个证据或者一个反例。谢谢!
浏览 1提问于2020-12-16得票数 2
回答已采纳
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。
我用Prim算法找到了最小生成树。。
我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树吗？
浏览 1提问于2019-03-17得票数 0
回答已采纳
当我找到一个“临界边缘”问题的解决方案时，我遇到了这个问题。我已经解决的最初(C++)问题是：
考虑一个图G=(V，E)。找出有多少边属于所有的 MST，有多少边不属于属于任何MST，有多少边属于一些MST，但不是全部。
让我们分别将“绿色”、“红色”和“黄色”称为上述3种情况下的边缘。
在进行我的研究之后，我偶然发现了，它解决了这个问题。一个将运行Kruskal算法的修改版本:如果两个或多个相同权重的边缘连接相同的组件，从而形成一个循环，那么所有这些都是黄色边缘，即可以包含在MST中的边缘(或不包括)。无可争辩地被选中的边缘是“绿色”的，在同一组件中创建循环的边缘是“红色”的。原来的
浏览 3提问于2014-12-31得票数 4
回答已采纳
2回答
我得到了一张上面有成本和字母的图表。我的任务不是寻找从一个节点到另一个节点的最佳路径，而是寻找最小生成树。 为此，我做了一些表格，并标记了这棵树的最佳路径。 ? ? 但我不知道是否应该从K个节点进一步到另一个节点。尽管如此，目的不是找到从A到K的最佳路径，而是MST。
浏览 58提问于2019-02-05得票数 2
我不确定如何处理这个问题。
给定一个无向图，每条边的颜色不是红色就是蓝色。如何在时间复杂度(O(m + n) log )内找到包含尽可能少红色边的最小生成树。其中m个顶点和n个是边。
任何帮助都将不胜感激。
浏览 1提问于2015-12-07得票数 1
假设我们有一个问题，其中有几个城市之间的路径成本(在时间上)是可变的，并且我们有两个推销员，他们两个之间必须至少访问每个城市一次。
现在，假设我们有一个算法，给定一个推销员和一组城市，可以为这个推销员设计一条最优路径。我们想要做的是以这样的方式划分城市，将一套分配给第一个推销员，另一套分配给另一名推销员，这样我们就可以得到一个解决方案，使总时间尽可能地短。做这件事的好方法是什么？我们想要一个很好的解决方案，但不一定是最优的。
我的想法是，我们可以使用某种启发式方法来确定给定的拆分是好是坏，但有很多城市，所以选择拆分是困难的。我不完全确定该怎么做。
需要澄清的是:每个城市必须至少有一个推销员到访
浏览 1提问于2014-05-01得票数 0
Kruskal算法在每次迭代时选择最小的边。虽然最终的目标是获得一个MST，但是解决的子问题是什么呢？是为了让森林有最小的重量，也是完全连接起来的吗？
浏览 5提问于2020-07-03得票数 1
回答已采纳
1回答
我们如何找到最小化节点v度的最小生成树(在所有最小生成树中)？
修改Kruskal算法，如果有几条边具有相同的权重，我们会选择不接触v的那条边来解决问题吗？
浏览 14提问于2017-02-22得票数 2
1回答
我正在学习MST算法。我很好奇想要找到prims和boruvka算法之间的关键区别，但在线资源除了它们的实现和算法之外，没有太多关于它们的内容。如果有人能解释，那将是很大的帮助。谢谢!
浏览 4提问于2021-07-18得票数 2
2回答
我有一个连通的无向图，每个图的边都是黑色或白色的，还有一个整数k。我正在尝试编写一个算法，来判断是否存在恰好有k条黑边的生成树(不一定要找到真正的树)。
我使用Kruskal的算法来找到生成树中可能的最小和最大黑边数量。如果k不在此范围内，则不可能存在具有k条边的生成树。
但我很难去思考，在这个范围内，是否每个k都必须有一棵生成树。我的直觉是肯定的，它对我尝试过的每个例子都有效，但我不知道如何证明这一点。
有什么建议吗？提前谢谢。
浏览 0提问于2010-12-06得票数 3
2回答
首先，请注意，这个问题是而不是询问MST，而只是all possible spanning trees。
所以这是，而不是，与或一样
我只需要从一个图表中生成所有可能的spanning trees。
我认为蛮力的方式是直接的：
假设我们有V节点和E边。
获取图的所有边
将V-1的所有可能组合从E边缘提取出来。
从组合中筛选出non-spanning-tree (对于生成树，一组V-1边缘中的所有节点都应该出现一次)
但是我觉得面对大图的时候太慢了。
我们有更好的方法吗？
浏览 4提问于2014-03-02得票数 9
回答已采纳
1回答
任意无向加权图的反馈集是边的子集，在去除子集中的边后，剩下的图是无圈的。
给定G= (V，E)，一个无向加权图和一个整数k，我如何确定是否有一个总权重不超过k的反馈集？
谢谢!
浏览 5提问于2020-03-17得票数 0
回答已采纳
4回答
最小生成树子图
、、、、
我正在阅读我的书中的所有练习，准备下周复习一次课堂考试，我真的对这个子图问题感到困惑。
目前我的想法使我相信，既然我们已经有了最小生成树G，那么既然我们在最小生成树中有子节点，就必须存在G‘。就目前情况而言，我有点不知所措。
如果X‘的节点集和边集分别是X的节点集和边集的子集，则X’是图X的子图。设(V，T)是G的最小生成树，G‘=(V’，E‘)是G的连通子图。
(a)证明了(V‘，E’∩T)是G‘的最小生成树的子图.
(b)在什么条件下(V‘，E’∩T)是G‘的最小生成树？证明你的主张。
提前谢谢！
浏览 2提问于2012-10-29得票数 4
回答已采纳
1回答
如何将Dijkstra算法应用于图，以使生成的树在两个给定顶点之间必须有一条边？(例如: MST必须包含X和Y之间的边)
谢谢
浏览 2提问于2011-06-01得票数 1
回答已采纳
算法设计手册中的练习
6-10。4.设G= (V，E)是无向图。一个边的集F⊆E称为反馈边集，如果G的每个圈在F (b)中至少有一个边，设G是一个带正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
我建议的解决方案(b)是运行DFS，获得最大重量作为平局断路器。然后，每一个后边缘将始终是其周期中的最低加权边。我想知道这是否是一个有效的解决方案。
浏览 0提问于2014-11-05得票数 1
1回答
我需要根据它们的余弦相似性来聚类(假设作为参数k)，单词(我存储在数组列表中)。我已经将我所有的单词作为顶点存储在一个完整的、加权的、无向图(使用邻接列表)中，并将它们的余弦相似度值放在边上。据我所知，我需要使用MST (Kruskals算法)进行聚类处理。
然而，由于我的图是完全图，而MST用于连通图，我有点困惑如何在完全图上使用它？还是我用完全图做错了？
这是我的wordList：
[directors, producers, film, movie, black, white, man, woman, person, man, young, woman, science, fictio
浏览 2提问于2018-04-28得票数 0
回答已采纳
给定一个无向加权图，边的实际权重是未知的；相反，每条边都被分类为轻、中或重。
所有轻边的权重都小于任何中边或重边。
所有中边的权重都比任何重边小。
通常，对于同一权重类中的两条边之间的关系一无所知。那么，如何识别这个图的每个MST中必须存在的所有边？以下是我的想法: 1.确定强连通分量的数量。2. MST中必须存在由铰接点组成的边。3.每个连接组件中最亮的边必须存在于MST中。
我不确定我的想法是否正确？如果是正确的，如何用java实现代码？非常感谢。
浏览 1提问于2018-10-20得票数 1
1回答
最短路径练习
、、、、
我正在尝试解决以下问题：
我们的银河系里有N颗行星。你可以在不同的行星之间旅行，但并不是每个行星都通过一条安全的路线连接到另一个行星。每条路线都有一个以光年为单位的给定长度。您的任务是在给定的一组行星T(其中0
输入包括N(行星数量)、R(行星之间安全路线的数量)、三元组A B L形式的R路径，其中A和B表示行星的恒星in，L表示它们之间的距离(以光年为单位)，T(需要建立基地的行星的数量)，后跟表示需要建立基地的行星的in的T数字。
您总是从ID为0的行星开始。在行星0上建立基地可能需要也可能不需要。
我试着解决了这个练习，并设法得到了一个有效的解决方案，但它太慢了。我使用弗洛伊德·沃肖尔算
浏览 3提问于2015-04-07得票数 1
2回答
考虑到我们试图将prim算法应用于不连通图上。考虑这个不连通图有顶点a，b，c和d，其中这个顶点d是不连通的。现在我需要检查我的理解，如果我们在这个不连通图上应用prim算法，算法不会到达顶点d，因此只返回a，b和c点的MST。那么，这个假设是对的吗？
浏览 4提问于2020-03-29得票数 0
我正在做我的研究，并继续问一个问题：
我有一个最小生成树(prim算法)，现在我的树中的一个节点被删除了，我想知道是否有一种方法可以重新组织我的树，使它仍然保持最优性？
我在这里寻求一些建议，我将感谢你的帮助。
谢谢!
注:所有边权值为1(单位图)。
浏览 0提问于2011-03-23得票数 6
5回答
通常用于查找图中两个节点之间的最短距离。它能用来找出最小的吗？如果是这样的话，是怎么做的？
编辑:这不是家庭作业，但我正在尝试理解一个旧的练习考试中的一个问题。
浏览 5提问于2009-12-16得票数 20
回答已采纳
假设您使用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
回答已采纳
1回答
当图有多个连通分量时，我不知道如何实现Kruskal算法
根据我对Kruskal算法的理解，它多次向集合中添加最小边。然后，当所有的边都被检查时，它会返回一组最充分的边。
但是，如果我的图是断开的呢？说我有：
A - B - C - D
E - F
假设成本( are )=成本(E)= 1，其余的边大于1。
当我运行Kruskal时，我会得到所有的边的成本，但是我想得到每个连接组件的成本，所以我对所有连接的组件做了一个平均最小的成本。
浏览 0提问于2014-03-07得票数 3
1回答
算法：
图表：
(注:缺边权，(T，Y，8))
在第一次迭代之前：
最小优先级队列(启动时的最小键)
Q= (S，0)，(T，∞)，(X，∞)，(Y，∞)，(Z，∞)
迭代1：
U=S
Q= (T，6)，(Y，7)，(X，∞)，(Z，∞)
更新T和Y的键
迭代2：
U=T
Q= (Z，-4)，(X，5)，(Y，7)
更新X，Y，Z的键
迭代3：
U=Z
Q= (X，5)，(Y，7)
没有更新
迭代4：
U=X
Q= (Y，7)
没有更新
迭代5：
U=Y
Q= []
没有更新
队列为空，循环终止
我们的最小生成树中有以下几个边：
(S，T，6)，(T，Z，5)，(T，Z，-4)，(
浏览 3提问于2017-04-14得票数 2
回答已采纳
1回答
我希望算法的名称可以用来从有向循环图中寻找具有平行边的最小权生成树。关于任何c++库的信息，这些库可以用于获取它们对运行时和效率的分析。
浏览 3提问于2019-03-30得票数 0
回答已采纳
我是一个新手程序员，试图在文本冒险中添加一个不必要的、复杂的元素！...and，我遇到了一个问题，我不知道如何进一步研究(我怀疑是因为缺乏恰当的术语知识)。
我正在处理一个使用11x11数组的小文本冒险。玩家能够用1移动到空间，而不能移动到0。我需要( a)保留外部边界0，b)将边界内的内容随机化，以及( c)确保有一个1s的链接路径，最终连接到一个2(出口)：
0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 1 0 0 0
0 0 1 1 1 1 1 1 1 1 0
0 0 1 0 0 0 0 0 0 1 0
0 0 1 1 1 1 1 1 1 1 0
0 1 1 0
浏览 0提问于2017-01-14得票数 1
回答已采纳
2回答
无向图的最小代价路径并
、、、、
我必须为一个经过所有节点的加权无向图创建一个总成本最低的解决方案。没有定义起始节点的多条路径应在一个相交节点结束并相交。路径的数目和包括在路径中的节点的数目不是预先确定的。节点可以多次传递。
我在处理什么类型的问题，可能的算法作为解决方案？我认为它应该是最小生成树的变体(意思是使用相交节点作为路径的起点，而不是终点)
浏览 1提问于2012-12-14得票数 3
我正在尝试编写一个洪水模拟程序。
为了找到从起始顶点到顶点的最小权重路径，我们直观地使用Dijkstra's。如果路径的权重现在是它的边的最大权重，该怎么办？我们可以修改Dijkstra的来使用这个图吗？
浏览 18提问于2019-12-04得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议活动推荐
腾讯云开发者
