2回答
给定一个连通的无向图，寻找具有最小最大度的生成树的问题已经得到了很好的研究(M.F¨urer，B.Rahvachari，“近似最小度生成树到最优度的1以内”，ACM-SIAM离散算法研讨会(SODA)，这个问题是NP难的，文献中已经描述了一种近似算法。
我对以下问题感兴趣-给定一个连通无向图G= (V1，V2，E)，找出所有内部节点(非叶子节点)上具有最大最小度的生成</e
浏览 1提问于2013-03-18得票数 3
1回答
我们如何找到最小化节点v度的最小生成树(在所有最小生成树中)？
修改Kruskal算法，如果有几条边具有相同的权重，我们会选择不接触v的那条边来解决问题吗？
浏览 14提问于2017-02-22得票数 2
一个将运行Kruskal算法的修改版本:如果两个或多个相同权重的边缘连接相同的组件，从而形成一个循环，那么所有这些都是黄色边缘，即可以包含在MST中的边缘(或不包括)。上面的算法的问题是，它运行在O( {##*}*log\V# )中，这是Kruskal算法的运行时间(如果我错了，请纠正我)。我正在考虑是否也可以使用Prim算法的修改版本，因为如果使用Fibonacci堆，它具有更好的摊销复杂度的O( {##**$$}}E~*)的O(欧元E+V log log V_x )的更好的摊销复杂度
浏览 3提问于2014-12-31得票数 4
回答已采纳
1回答
我们能给出一个算法，使从S到X的路径上的边的最大权重最小化吗？注意，这不是最短路径算法，因为我们对最小化它们的和不感兴趣。
这个算法的复杂度是多少？最小生成树算法(如Prim)是否是该问题的解决方案？
浏览 0提问于2018-11-14得票数 0
如何在时间复杂度(O(m + n) log )内找到包含尽可能少红色边的最小生成树。其中m个顶点和n个是边。
任何帮助都将不胜感激。
浏览 1提问于2015-12-07得票数 1
1回答
该图由一棵生成树和一条额外的边组成。我在考虑Kruskal的算法，但它不能满足时间复杂度的要求。
浏览 0提问于2020-04-06得票数 1
回答已采纳
根据，在无向图中找到最小生成树的步骤如下：
我的方法有什么问题吗？虽然时间复杂度保持不变，因为我们仍
浏览 6提问于2020-10-07得票数 0
回答已采纳
1回答
我试图解决一个关于图的算法挑战，我已经将它分解为以下几个方面:给定一个无向生成树，找到2叶，使得它们之间的代价最小。现在我知道了Floyd算法，它可以找到具有时间复杂度O(N^3)和空间复杂度O(N^2)的所有对最短路径。问题的输入是N= 10^5，所以O(N^3)和O(N^2)太多了。有没有办法优化这个问题的时间和空间复杂度？
浏览 6提问于2017-03-07得票数 1
1回答
哪种数据结构允许如下：
将元素存储在非连续(一开始看起来像红黑树可能是一种选择，或者x快速树，但我想寻找相对简单的算法。我很高兴看到你的建议。
浏览 1提问于2020-09-02得票数 0
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树
浏览 1提问于2019-03-17得票数 0
回答已采纳
2回答
计算最小可能树
、、
给定一组节点，如何构造一棵将所有节点连接在一起的树，使最大(最大(度)，最大(深度))最小化。例如，给定一组由五个节点组成的节点，我可以这样连接它们：然而，这并不是最小的，因为最大(度) == 4和最大(深度) == 1，更好的树应该是：它具有最大(度) == 2和最大(深度) == 2
编辑：：算法不一定要快，但计算绝对最优的树是重要的。
浏览 1提问于2010-10-22得票数 3
回答已采纳
2回答
我希望我的最小生成树算法基准与最好的。有人知道在哪里可以找到这些算法的C++实现吗？我大摇大摆地搜索了一下，却什么也没找到。如果这些算法是最好的，那么肯定有一个C++实现吗？--迄今最快的最小生成树算法是由David、Philip和Robert提出的，他发现了一种线性时间随机算法，它是Borůvka算法和反向删除算法的结合。函数α增长非常慢，因此在实际应用中，它可
浏览 2提问于2011-02-07得票数 11
回答已采纳
有向图G的树状结构是有根树，使得从根点到图中的每一个顶点都有一条有向路径。给出了一种有效且正确的算法来判定图G是否含有树形图，并分析了其时间复杂度。我想过使用最小生成树算法，但这也只适用于无向图我发现了一个后续问题，对于同样的问题，有一个O(n+m)算法，有人能帮我解决吗？
浏览 1提问于2014-01-07得票数 5
2回答
有人能解释一下什么是最小的叶子生成树吗？我对一棵树上的叶子究竟是什么感到困惑。我知道生成树包含没有圈的简单路径，它跨越图G中的所有顶点，但是最小叶树是什么呢？
浏览 3提问于2014-10-18得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
