1回答
任意无向加权图的反馈集是边的子集，在去除子集中的边后，剩下的图是无圈的。
给定G= (V，E)，一个无向加权图和一个整数k，我如何确定是否有一个总权重不超过k的反馈集？
谢谢!
浏览 5提问于2020-03-17得票数 0
回答已采纳
1回答
在加权图中将循环图转换为无圈图
、、、、
我得到了一个具有非负权重的连通加权图。我想把它转换成一个连通的非循环图，这样被移除的边的权重之和就会最小化。输出将是移除的边。 我的想法是:由于一个连通的非循环图是一棵树，我可以简单地获取最大的n-1边，然后删除所有其他边。但是，这并不总是正确的。它可能导致不连通的图。 然后，我想到了使用dfs。我知道如何使用dfs检测图是否有圈，但我不知道如何检测涉及到的所有边，以及如何将其转换为非循环图。任何帮助(代码/伪代码/文字中的算法)都将不胜感激。谢谢..。
浏览 36提问于2019-06-12得票数 1
回答已采纳
算法设计手册中的练习
6-10。4.设G= (V，E)是无向图。一个边的集F⊆E称为反馈边集，如果G的每个圈在F (b)中至少有一个边，设G是一个带正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
我建议的解决方案(b)是运行DFS，获得最大重量作为平局断路器。然后，每一个后边缘将始终是其周期中的最低加权边。我想知道这是否是一个有效的解决方案。
浏览 0提问于2014-11-05得票数 1
我真的很纠结于这个证据，我很想得到详细的解释：
给出一个具有n个顶点的完备图，MST的权重小于或等于通过所有顶点的圈的最小权(也称为hamiltonian圈)？
浏览 2提问于2016-03-28得票数 0
回答已采纳
2回答
使用BGL创建生成树
、、、、
我有一个BGL图，想用BGL创建一个生成树。
从指定的顶点开始，我想将最短的边添加到与此顶点连接的图中。从那时起，我希望总是选择与到目前为止存在的图相连接的最短边。
因此，我想添加这样的约束，即每条新的边都必须已经连接到图，同时保持生成树标准，即没有圈。
手工操作并不是很难；但是由于我想学习一些关于BGL的知识，所以我想知道哪种算法最适合我的问题。
浏览 2提问于2010-10-29得票数 1
回答已采纳
2回答
有人能解释一下什么是最小的叶子生成树吗？我对一棵树上的叶子究竟是什么感到困惑。我知道生成树包含没有圈的简单路径，它跨越图G中的所有顶点，但是最小叶树是什么呢？
浏览 3提问于2014-10-18得票数 1
回答已采纳
2回答
我正在使用对JS中的图执行拓扑排序。问题是，在极少数情况下，图中会包含圈。这些都是结构的次要部分，因此丢弃一些边缘不会对最终结果产生太大影响。然而，当它们出现时，算法就会中断。更新它的最有效方法是什么，这样如果有一两个周期，它就不会崩溃？
浏览 3提问于2013-08-17得票数 1
4回答
我正在研究寻找最小生成树(在加权图的情况下)和查找图是否有哈密顿路径(这取决于哈密顿圈的存在)的算法。我把一切都搞砸了。那么哈密顿路径和生成树之间有什么区别呢？两者都覆盖了图中的所有顶点。虽然我们可以有高效的算法来寻找生成树(可能是最小生成树)，但为什么我们就不能有寻找哈密顿回路的算法呢？我们可以一次增加和删除一条边，直到我们到达一个循环，也许我们可以找到哈密顿循环？？
浏览 1提问于2011-07-23得票数 14
起源问题来自于的练习，算法的引入。
23.1-5设e是连通图G=(V, E)的某个圈上的最大权边.证明了G'=(V, E - {e})的最小生成树也是G的最小生成树。也就是说，有一个G的最小生成树，它不包括e。
问题是:我认为G 的所有最小生成树不包括 e 的命题是正确的。e 是某些周期上唯一的最大权边.是吗？
更新：2016-10-28 20:21
添加e是的限制，这是某个循环中唯一的最大权重边.
浏览 1提问于2016-10-28得票数 1
回答已采纳
1回答
正如维基百科所说：
最小生成林是其连通部分的最小生成树的结合。
为了找到最小生成树，我们可以使用例如、或。
我们可以用什么算法来寻找最小生成森林？
浏览 2提问于2017-05-16得票数 2
回答已采纳
3回答
我目前正在优化电网规划，而MST没有很好地解决这个问题，因为如果到主电网的连接是一个辐射点，所有的电力都必须流经一条边，并将经过很长的“电气距离”到达每个耗电量点。
我正在研究的问题可能是最小化MW*distance或有功功率矩，但这会产生一个非线性问题。
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的距离)。
通过这种方式，我只是购买更长更细的电缆，这是一种更便宜的解决方案，较短，较厚的电缆。
浏览 1提问于2013-06-27得票数 6
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
3回答
假设有一个图G，它的所有边都有对应于不同整数的权重。所以没有两条边具有相同的权重。设E是G的所有边，emax是E中具有最大权重的边。图G的另一个性质是每条边e都属于图G中的某个圈。
我必须证明G的最小生成树不包含边emax。
我可以理解为什么这是真的，因为所有的边都是不同的，并且每条边都属于一个循环，所以最小生成树算法可以简单地选择包含emax的循环中权重较低的边。但我不确定如何具体证明这一点。
浏览 2提问于2013-11-28得票数 6
回答已采纳
这是一个复习问题，我想知道我的答案是否正确。
以下是原问题的要点：
你有一个加权无向图的MST，T，然后在原始图的节点(u和v)之间引入一条新的边，以创建一个新的图G‘。给出了判定T是否是G‘的MST的线性时间算法。
我的答案是：
原始图的MST T不包含任何圈。从节点u到节点v应该只有一条路径。我们可以将新的边添加到MST中，这可以在O(1)时间内完成，从而生成我们的新树T‘。然后，我们可以在从u到v的T‘上运行DFS，它在O(|V| + |E|)时间内完成。添加了新的边之后，我们最多只能在u和v之间找到2条路径。我们可以在O(1)时间内比较这两条路径。如果两个图中较短的一个使用了新的边，那
浏览 2提问于2019-10-26得票数 0
5回答
设G= (V，E)是无向图。若F.中G的每个圈至少有一条边，则称边的F⊆E集为⊆反馈边集。
(a)假设G未加权。设计了一种有效的求最小大小反馈边缘集的算法.
(b)设G是一个具有正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
我的解决方案(需要建议)：
( a) 最小大小反馈边集：，由于图是不加权的，我们可以使用DFS。我们像往常一样从任何顶点开始DFS。当我们遇到一个后边缘，我们把它插入到一组反馈边。当DFS完成时，这个集合将是答案。
( b) 最小权反馈边集：由于图是加权的，所以我们可以使用Kruskal。但是Kruskal通常以最小重量的边缘开始。如果我们可以否定所有的
浏览 6提问于2012-05-29得票数 15
1回答
我得找出堵车的降雨门槛。
所以，我必须打印降水的阈值来阻止交通。
(前)
3 3
0 1 2
1 2 3
0 2 6
产出:3
对于这个问题有什么好的算法或关键字吗？
谢谢
浏览 0提问于2019-04-02得票数 1
回答已采纳
1回答
我只能想出一个简单的解决方案，找到图中的所有圈，然后找到每个圈中的边数，然后返回最大边的边。
如何使用贪婪算法找到最长的周期？
浏览 4提问于2020-03-22得票数 0
如果最小生成树是贪婪的，为什么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回答
我需要得到一个完整图的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
回答已采纳
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
回答已采纳
2回答
我需要编写一种算法，以求给定无向图的最小命中集F，即包含图的每个圈中的最小边的集合，使F与任意给定圈的交集不为空。我编写了一种算法，它首先使用深度搜索来查找图中所有可能的循环，然后在每个循环中取最小边缘，并将其放入一个集合中(在该集合中，我删除重复的循环)。
然而，我被要求在多项式时间内完成这项任务，但我不太确定我的算法是否完成了。例如，我添加了一个计数器来解决从A开始的以下图，我的DFS方法被调用了34次：
有人能帮我算出我写的算法的运行时间吗？它是功能性的，但它似乎效率很低。谢谢
下面是我的DFS方法的代码。MHS是起类似节点作用的基本数据结构。它们有一个标记和一个链接列表，其中包含
浏览 1提问于2016-02-15得票数 0
回答已采纳
1回答
我们如何找到最小化节点v度的最小生成树(在所有最小生成树中)？
修改Kruskal算法，如果有几条边具有相同的权重，我们会选择不接触v的那条边来解决问题吗？
浏览 14提问于2017-02-22得票数 2
1回答
我正在学习MST算法。我很好奇想要找到prims和boruvka算法之间的关键区别，但在线资源除了它们的实现和算法之外，没有太多关于它们的内容。如果有人能解释，那将是很大的帮助。谢谢!
浏览 4提问于2021-07-18得票数 2
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回答
如何将Dijkstra算法应用于图，以使生成的树在两个给定顶点之间必须有一条边？(例如: MST必须包含X和Y之间的边)
谢谢
浏览 2提问于2011-06-01得票数 1
回答已采纳
什么是一个很好的算法来删除一个图的所有边，而这些边不是至少一个圈的一部分？基本上，我想“修剪所有的树”从一个任意的图形。
我从头顶上想到的算法并不是很有效，而且也是不正确的：
给定一个图G，设C是至少一个循环中的一组边。通过图遍历在G中找到一个循环，并用它的边作为种子C。
对于每个边e (不是在C中，而是在C中的一个边的顶点)，执行从e开始的遍历，以找到在C中的边缘顶点中终止的路径P。
如果存在这样的路径P，那么将P的边缘添加到C和goto 2中，否则e是树的根，所以删除e及其所有子树。
上面的语句效率很低，但更重要的是，“否则e是树的根”的语句是不正确的:如果两个循环都不
浏览 4提问于2020-10-30得票数 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
我正在做我的研究，并继续问一个问题：
我有一个最小生成树(prim算法)，现在我的树中的一个节点被删除了，我想知道是否有一种方法可以重新组织我的树，使它仍然保持最优性？
我在这里寻求一些建议，我将感谢你的帮助。
谢谢!
注:所有边权值为1(单位图)。
浏览 0提问于2011-03-23得票数 6
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频
腾讯云开发者
