1回答
正如维基百科所说：
最小生成林是其连通部分的最小生成树的结合。
为了找到最小生成树，我们可以使用例如、或。
我们可以用什么算法来寻找最小生成森林？
浏览 2提问于2017-05-16得票数 2
回答已采纳
3回答
我目前正在优化电网规划，而MST没有很好地解决这个问题，因为如果到主电网的连接是一个辐射点，所有的电力都必须流经一条边，并将经过很长的“电气距离”到达每个耗电量点。
我正在研究的问题可能是最小化MW*distance或有功功率矩，但这会产生一个非线性问题。
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的距离)。
通过这种方式，我只是购买更长更细的电缆，这是一种更便宜的解决方案，较短，较厚的电缆。
浏览 1提问于2013-06-27得票数 6
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
1回答
如何将Dijkstra算法应用于图，以使生成的树在两个给定顶点之间必须有一条边？(例如: MST必须包含X和Y之间的边)
谢谢
浏览 2提问于2011-06-01得票数 1
回答已采纳
1回答
我得找出堵车的降雨门槛。
所以，我必须打印降水的阈值来阻止交通。
(前)
3 3
0 1 2
1 2 3
0 2 6
产出:3
对于这个问题有什么好的算法或关键字吗？
谢谢
浏览 0提问于2019-04-02得票数 1
回答已采纳
3回答
我正试图为一棵“几乎”50,000个顶点的树获得一个顶点覆盖。该图形生成为一棵具有随机边的树，使其“几乎”成为一棵树。
我使用了近似方法，你把两个顶点结合起来，把它们加到盖子上，然后把它们从图中删除，然后转移到另一组顶点上。在此之后，我试图通过删除顶点覆盖中的所有邻接点来减少顶点的数量。
我的问题是如何使顶点覆盖更小？我正试着往下走。
浏览 15提问于2016-03-20得票数 0
回答已采纳
1回答
加权有向图的Prim算法
、、、
我在学习最小生成树。我研究了Prim关于加权有向图的算法。
算法简单
您有两个顶点集，已访问的和未访问的。
将所有边的距离设为无穷远
从未访问集中的任意顶点开始，并探索其边缘。
在所有边缘中，如果目标顶点没有被访问，并且如果边缘的权重小于目标顶点的距离，则使用该边缘的权重更新目标顶点的距离。
选择距离最小的未访问顶点，然后再做一次，直到所有顶点都被访问。
通过上述算法，我可以在所有的生成树中找到代价最小的生成树，即最小生成树。
但是我把它应用到下面的例子中，我认为它失败了。
请考虑以下示例
顶点是{v1，v2，v3，v4，v5}和带权的边。
(x，y)：W
浏览 2提问于2014-03-18得票数 0
如果最小生成树是贪婪的，为什么Kruskal的算法会找到它呢？最小生成树不是一个全局优化问题吗？贪婪的意义不是在于你有可能找不到最优的解决方案吗？那么，Kruskal如何在贪婪的情况下找到最小生成树呢？
浏览 2提问于2016-12-10得票数 5
1回答
聚类最小生成树的数据集
、、、
最近我遇到了最小生成树的概念，发现它在聚类中有一个应用程序。我正在寻找一个真实的数据集(最好是干净的)，它可以作为各种聚类算法的数据源。有一种信息表明，MST聚类在球面和非球面数据上工作得足够好。这就是为什么非球面数据集也被追求的原因。
我心目中的数据集应该包含地面真相信息(标签)，因此各种标志的有效性可以通过与WSS不同的东西来衡量。
浏览 1提问于2018-06-12得票数 0
回答已采纳
Kruskal算法在每次迭代时选择最小的边。虽然最终的目标是获得一个MST，但是解决的子问题是什么呢？是为了让森林有最小的重量，也是完全连接起来的吗？
浏览 5提问于2020-07-03得票数 1
回答已采纳
2回答
我不想找到所有的最小生成树，但是我想知道其中有多少树，下面是我考虑过的方法：
用prim或kruskal算法求出最小生成树，然后求出所有生成树的权值，当最小生成树的权重等于最小生成树的权重时，增加运行计数器。
我找不到任何方法来求出所有生成树的权重，而且生成树的数目也可能很大，所以这种方法可能不适合这个问题。由于最小生成树的数目是指数的，将它们计算起来不是一个好主意。
所有的重量都是正数。
我们还可以假设，在图中不会出现超过三次的权重。
顶点的数目将小于或等于40,000。
边数将小于或等于100,000。
图中只有一个最小生成树，其中顶点的权重是不同的。我
浏览 4提问于2012-12-13得票数 9
回答已采纳
当我找到一个“临界边缘”问题的解决方案时，我遇到了这个问题。我已经解决的最初(C++)问题是：
考虑一个图G=(V，E)。找出有多少边属于所有的 MST，有多少边不属于属于任何MST，有多少边属于一些MST，但不是全部。
让我们分别将“绿色”、“红色”和“黄色”称为上述3种情况下的边缘。
在进行我的研究之后，我偶然发现了，它解决了这个问题。一个将运行Kruskal算法的修改版本:如果两个或多个相同权重的边缘连接相同的组件，从而形成一个循环，那么所有这些都是黄色边缘，即可以包含在MST中的边缘(或不包括)。无可争辩地被选中的边缘是“绿色”的，在同一组件中创建循环的边缘是“红色”的。原来的
浏览 3提问于2014-12-31得票数 4
回答已采纳
我可以使用什么算法来解决这样的问题：
有一个图的正权重，我想知道每个节点连接的权重的最小和(像网络一样连接，其中每个节点是一个eg。网络设备)。
在这个网络中，每个节点都可以通过其他节点以某种方式与其他节点相连。但输入图中的所有节点都必须位于网络中。
浏览 1提问于2010-04-26得票数 0
回答已采纳
2回答
无向图的最小代价路径并
、、、、
我必须为一个经过所有节点的加权无向图创建一个总成本最低的解决方案。没有定义起始节点的多条路径应在一个相交节点结束并相交。路径的数目和包括在路径中的节点的数目不是预先确定的。节点可以多次传递。
我在处理什么类型的问题，可能的算法作为解决方案？我认为它应该是最小生成树的变体(意思是使用相交节点作为路径的起点，而不是终点)
浏览 1提问于2012-12-14得票数 3
1回答
我正在阅读一本算法教科书，以提高我的算法技能，但我在这个问题上完全被困住了，这让我很困扰。我认为底层的数据结构是一个图表，但我甚至不知道从哪里开始这个问题。有人能给点见解吗？谢谢
给出了一个地形图，该地形图提供了任意两个相邻城市和两个城市a和b之间的直接道路上的最大高度。提出了一个线性时间算法，该算法可以找到从s到t的路径，从而使最大高度最小化。道路可以双向通行。
浏览 3提问于2013-10-01得票数 1
1回答
当我看到时，这个问题突然浮现在我的脑海中。为了简单起见，我们可以将讨论限制在无向、加权、连通图上。显然，如果从图中选择任意节点作为源，Dijkstra不能保证生成MST。然而，它是否保证在一个无向、加权、连通图中必须存在一个节点，如果我们选择它作为源并应用Dijkstra的算法，它将为该图生成一个MST？也许你可以给出一个证据或者一个反例。谢谢!
浏览 1提问于2020-12-16得票数 2
回答已采纳
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。
我用Prim算法找到了最小生成树。。
我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树吗？
浏览 1提问于2019-03-17得票数 0
回答已采纳
1回答
我们如何找到最小化节点v度的最小生成树(在所有最小生成树中)？
修改Kruskal算法，如果有几条边具有相同的权重，我们会选择不接触v的那条边来解决问题吗？
浏览 14提问于2017-02-22得票数 2
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回答
在加权图中将循环图转换为无圈图
、、、、
我得到了一个具有非负权重的连通加权图。我想把它转换成一个连通的非循环图，这样被移除的边的权重之和就会最小化。输出将是移除的边。 我的想法是:由于一个连通的非循环图是一棵树，我可以简单地获取最大的n-1边，然后删除所有其他边。但是，这并不总是正确的。它可能导致不连通的图。 然后，我想到了使用dfs。我知道如何使用dfs检测图是否有圈，但我不知道如何检测涉及到的所有边，以及如何将其转换为非循环图。任何帮助(代码/伪代码/文字中的算法)都将不胜感激。谢谢..。
浏览 36提问于2019-06-12得票数 1
回答已采纳
2回答
我得到了一张上面有成本和字母的图表。我的任务不是寻找从一个节点到另一个节点的最佳路径，而是寻找最小生成树。 为此，我做了一些表格，并标记了这棵树的最佳路径。 ? ? 但我不知道是否应该从K个节点进一步到另一个节点。尽管如此，目的不是找到从A到K的最佳路径，而是MST。
浏览 58提问于2019-02-05得票数 2
1回答
任意无向加权图的反馈集是边的子集，在去除子集中的边后，剩下的图是无圈的。
给定G= (V，E)，一个无向加权图和一个整数k，我如何确定是否有一个总权重不超过k的反馈集？
谢谢!
浏览 5提问于2020-03-17得票数 0
回答已采纳
假设我们有一个问题，其中有几个城市之间的路径成本(在时间上)是可变的，并且我们有两个推销员，他们两个之间必须至少访问每个城市一次。
现在，假设我们有一个算法，给定一个推销员和一组城市，可以为这个推销员设计一条最优路径。我们想要做的是以这样的方式划分城市，将一套分配给第一个推销员，另一套分配给另一名推销员，这样我们就可以得到一个解决方案，使总时间尽可能地短。做这件事的好方法是什么？我们想要一个很好的解决方案，但不一定是最优的。
我的想法是，我们可以使用某种启发式方法来确定给定的拆分是好是坏，但有很多城市，所以选择拆分是困难的。我不完全确定该怎么做。
需要澄清的是:每个城市必须至少有一个推销员到访
浏览 1提问于2014-05-01得票数 0
3回答
有谁能解释为什么Kruskal产生的树与Dijkstra不同？
我知道kruskal工作在边的非降序上，但是Dijkstra利用优先级队列，但仍然不明白为什么从它们得到的树是不同的？
浏览 2提问于2013-12-05得票数 7
回答已采纳
我不确定如何处理这个问题。
给定一个无向图，每条边的颜色不是红色就是蓝色。如何在时间复杂度(O(m + n) log )内找到包含尽可能少红色边的最小生成树。其中m个顶点和n个是边。
任何帮助都将不胜感激。
浏览 1提问于2015-12-07得票数 1
算法设计手册中的练习
6-10。4.设G= (V，E)是无向图。一个边的集F⊆E称为反馈边集，如果G的每个圈在F (b)中至少有一个边，设G是一个带正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
我建议的解决方案(b)是运行DFS，获得最大重量作为平局断路器。然后，每一个后边缘将始终是其周期中的最低加权边。我想知道这是否是一个有效的解决方案。
浏览 0提问于2014-11-05得票数 1
1回答
如何修剪R中的树？
、、、
我正在使用R中的rpart进行分类。树模型的训练方法是：
> tree <- rpart(activity ~ . , data=trainData)
> pData1 <- predict(tree, testData, type="class")
此树模型的精度为：
> sum(testData$activity==pData1)/length(pData1)
[1] 0.8094276
我读了一个通过交叉验证修剪树的：
> ptree <- prune(tree,cp=tree$cptable[which.min(tree$cpt
浏览 1提问于2013-03-10得票数 13
回答已采纳
给定一个无向加权图，边的实际权重是未知的；相反，每条边都被分类为轻、中或重。
所有轻边的权重都小于任何中边或重边。
所有中边的权重都比任何重边小。
通常，对于同一权重类中的两条边之间的关系一无所知。那么，如何识别这个图的每个MST中必须存在的所有边？以下是我的想法: 1.确定强连通分量的数量。2. MST中必须存在由铰接点组成的边。3.每个连接组件中最亮的边必须存在于MST中。
我不确定我的想法是否正确？如果是正确的，如何用java实现代码？非常感谢。
浏览 1提问于2018-10-20得票数 1
1回答
空间高效的最小生成树
、、、、
我遇到了一个任务，基本上是要求你找到给定图的MST，其中所有的顶点都是相连的。我尝试使用Kruskal的算法，但我很快就发现空间限制太紧，无法以兆字节存储所有的边，所以我也放弃了Prim和Boruvka的算法。有没有办法实现这些算法(或任何其他MST算法)，空间复杂度比O(E)更好，在本例中是O(V^2)？
浏览 4提问于2018-06-12得票数 2
1回答
我正在学习MST算法。我很好奇想要找到prims和boruvka算法之间的关键区别，但在线资源除了它们的实现和算法之外，没有太多关于它们的内容。如果有人能解释，那将是很大的帮助。谢谢!
浏览 4提问于2021-07-18得票数 2
1回答
我希望算法的名称可以用来从有向循环图中寻找具有平行边的最小权生成树。关于任何c++库的信息，这些库可以用于获取它们对运行时和效率的分析。
浏览 3提问于2019-03-30得票数 0
回答已采纳
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
回答已采纳
2回答
首先，请注意，这个问题是而不是询问MST，而只是all possible spanning trees。
所以这是，而不是，与或一样
我只需要从一个图表中生成所有可能的spanning trees。
我认为蛮力的方式是直接的：
假设我们有V节点和E边。
获取图的所有边
将V-1的所有可能组合从E边缘提取出来。
从组合中筛选出non-spanning-tree (对于生成树，一组V-1边缘中的所有节点都应该出现一次)
但是我觉得面对大图的时候太慢了。
我们有更好的方法吗？
浏览 4提问于2014-03-02得票数 9
回答已采纳
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回答
假设我们有一个无向图G=(V，E)，我们有两个节点S和X。
我们能给出一个算法，使从S到X的路径上的边的最大权重最小化吗？注意，这不是最短路径算法，因为我们对最小化它们的和不感兴趣。
这个算法的复杂度是多少？
最小生成树算法(如Prim)是否是该问题的解决方案？
浏览 0提问于2018-11-14得票数 0
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
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
回答已采纳
学习GradientBoostingRegressor：
📷
我在看GradientBoostingRegressor的scikit学习文档。
这里说，我们可以使用'ls‘作为一个损失函数，这是最小二乘回归。但是我很困惑，因为最小二乘回归是一种最小化SSE损失函数的方法。
所以他们不应该在这里提到SSE吗？
浏览 0提问于2020-10-22得票数 1
回答已采纳
1回答
当图有多个连通分量时，我不知道如何实现Kruskal算法
根据我对Kruskal算法的理解，它多次向集合中添加最小边。然后，当所有的边都被检查时，它会返回一组最充分的边。
但是，如果我的图是断开的呢？说我有：
A - B - C - D
E - F
假设成本( are )=成本(E)= 1，其余的边大于1。
当我运行Kruskal时，我会得到所有的边的成本，但是我想得到每个连接组件的成本，所以我对所有连接的组件做了一个平均最小的成本。
浏览 0提问于2014-03-07得票数 3
1回答
给定一棵k-ary树，我希望将其转换为具有最少更改次数的最小堆。更改被定义为重新标记节点。
我发现的一种解决方案是，我可以尝试更改节点值或不更改节点的dp解决方案。但是它在时间复杂度上会是指数级的？任何想法，(最好有最优性证明)。
例如:假设树是1-3，3-2，1-4，4-5。其中1是根。然后我可以将节点3重新标记为1或2，也就是说，在1个更改中，它变成了一个最小堆。
浏览 7提问于2017-12-16得票数 1
3回答
查找连接所有节点的最短路径集
、、、、
我在二维坐标空间中有一组点。
我想找出一组总长度最短的连接它们的路径。(启发式解决方案ok，不需要精确。)
这可能听起来像旅行推销员的问题，但它是不同的。我不是在寻找一个周期，它将访问每个点一次并且只有一次。我只需要每个点连接到至少一个其他点，这样集合中的所有点至少间接地彼此连接，所选连接的长度之和将被最小化。因此，它应该是非循环的，以最小化连接长度的总和。
简单的最近邻居算法(即，将每个点连接到尚未连接到它的最近邻居)不起作用，因为彼此相距较远的小集群最终将被隔离，而您最终将最终创建循环。
浏览 6提问于2020-01-31得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
