7回答
如何找到最大生成树？
、、、
与Kruskal的最小生成树算法相反的算法对它有效吗？我的意思是，选择每一步的最大权重(边)？
有没有找到最大生成树的其他想法？
浏览 4提问于2011-02-14得票数 64
回答已采纳
1回答
在加权图中将循环图转换为无圈图
、、、、
我得到了一个具有非负权重的连通加权图。我想把它转换成一个连通的非循环图，这样被移除的边的权重之和就会最小化。输出将是移除的边。 我的想法是:由于一个连通的非循环图是一棵树，我可以简单地获取最大的n-1边，然后删除所有其他边。但是，这并不总是正确的。它可能导致不连通的图。 然后，我想到了使用dfs。我知道如何使用dfs检测图是否有圈，但我不知道如何检测涉及到的所有边，以及如何将其转换为非循环图。任何帮助(代码/伪代码/文字中的算法)都将不胜感激。谢谢..。
浏览 36提问于2019-06-12得票数 1
回答已采纳
1回答
我得找出堵车的降雨门槛。
所以，我必须打印降水的阈值来阻止交通。
(前)
3 3
0 1 2
1 2 3
0 2 6
产出:3
对于这个问题有什么好的算法或关键字吗？
谢谢
浏览 0提问于2019-04-02得票数 1
回答已采纳
算法设计手册中的练习
6-10。4.设G= (V，E)是无向图。一个边的集F⊆E称为反馈边集，如果G的每个圈在F (b)中至少有一个边，设G是一个带正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
我建议的解决方案(b)是运行DFS，获得最大重量作为平局断路器。然后，每一个后边缘将始终是其周期中的最低加权边。我想知道这是否是一个有效的解决方案。
浏览 0提问于2014-11-05得票数 1
1回答
任意无向加权图的反馈集是边的子集，在去除子集中的边后，剩下的图是无圈的。
给定G= (V，E)，一个无向加权图和一个整数k，我如何确定是否有一个总权重不超过k的反馈集？
谢谢!
浏览 5提问于2020-03-17得票数 0
回答已采纳
1回答
给定一个正权重的无向循环图，我如何找到最小的一组要删除的边，从而使该图成为非循环图？算法必须在O((E+V)logV)时间内运行。
我试图解决这个问题，并考虑使用贾克斯特拉的算法(因为它也在O(E+VlogV)时间内运行，但我不确定如何前进。
浏览 5提问于2021-06-08得票数 1
1回答
这是一个家庭作业问题，所以我很高兴得到一个提示。
我有一个图G，其中每个顶点v都有一个权重w(v)。
S(G)是图中所有顶点的权重之和。
我需要找到一个算法来确定是否存在一组顶点A，当G是一棵树时，它进行S(GA)=S(GV\A)。
我知道我应该遍历所有的顶点，对它们的权重求和，然后尝试找到一棵达到这个和的一半的树，但我不确定具体怎么做。我很确定这涉及到动态编程。
非常感谢,
亚伦。
浏览 0提问于2014-04-28得票数 3
1回答
我正在韦卡的皮马印第安人糖尿病数据库工作。我注意到对于决策树J48，与随机树相比，该树更小。我不明白为什么会这样？谢谢。
浏览 8提问于2022-02-21得票数 1
回答已采纳
2回答
我正在使用对JS中的图执行拓扑排序。问题是，在极少数情况下，图中会包含圈。这些都是结构的次要部分，因此丢弃一些边缘不会对最终结果产生太大影响。然而，当它们出现时，算法就会中断。更新它的最有效方法是什么，这样如果有一两个周期，它就不会崩溃？
浏览 3提问于2013-08-17得票数 1
编写了一种算法来查找具有最大叶子数的生成树。编写了一种算法来找到具有最小节点数的生成树。
我还未能就以下问题提出解决办法。
对于第一部分，我想的是找到最高度的顶点，然后把它放在第二层，最后一层得到最大的叶子数。
浏览 3提问于2020-03-20得票数 0
1回答
求最小生成树的新算法的最优性证明
、、、、
下面是查找最小生成树的算法：
MSTNew(G, w)
Z ← empty array
for each edge e in E, taken in random order do
Z ← Z ∪ e
if Z has a cycle c then
let e be a maximum-weight edge on c
Z ← Z − e
return (Z)
这个算法总是返回最优的MST解吗？
我会答应的。看起来有点像Kruskals算法。
对于图论来说，我是很新的，除了这个，我真的没有太多的想法。有
浏览 0提问于2014-11-25得票数 0
1回答
我正在阅读一本算法教科书，以提高我的算法技能，但我在这个问题上完全被困住了，这让我很困扰。我认为底层的数据结构是一个图表，但我甚至不知道从哪里开始这个问题。有人能给点见解吗？谢谢
给出了一个地形图，该地形图提供了任意两个相邻城市和两个城市a和b之间的直接道路上的最大高度。提出了一个线性时间算法，该算法可以找到从s到t的路径，从而使最大高度最小化。道路可以双向通行。
浏览 3提问于2013-10-01得票数 1
2回答
我有一个连通的无向图，每个图的边都是黑色或白色的，还有一个整数k。我正在尝试编写一个算法，来判断是否存在恰好有k条黑边的生成树(不一定要找到真正的树)。
我使用Kruskal的算法来找到生成树中可能的最小和最大黑边数量。如果k不在此范围内，则不可能存在具有k条边的生成树。
但我很难去思考，在这个范围内，是否每个k都必须有一棵生成树。我的直觉是肯定的，它对我尝试过的每个例子都有效，但我不知道如何证明这一点。
有什么建议吗？提前谢谢。
浏览 0提问于2010-12-06得票数 3
2回答
C#图算法库
、、、
我正在寻找具有下一个图形算法的.NET库：
求最小生成树的算法；
最小连接数的N个子图的图划分算法。
我可以写我自己的想法，但没有太多的时间。请告诉我，任何现有库的名称都可以做到这一点。谢谢。
浏览 0提问于2011-04-21得票数 1
回答已采纳
假设您使用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回答
请帮我解决以下问题的算法-
给定一系列事实，我们希望尽可能多地消除冗余。这个问题中涉及的事实是大写字母之间传递关系的成员。因此，每个事实都是一对大写字母，如AB，表示A与B相关。字母可能与自身相关，也可能与自身无关，但传递性成立:如果A与B相关，B与C相关，那么我们可以推断A与C相关。创建一个包含方法minFacts的类FactCount，该方法给定一个已知的String[]，并返回最小事实集的大小，使我们能够推断出所有可以从已知的事实中推断出的东西(只包括那些东西)。
每个已知元素将包含一个或多个由单个空格分隔的事实。最小的事实集可能包含可以从已知中推断出但不包含在其中的事实。
例如：
{&
浏览 10提问于2009-11-06得票数 2
回答已采纳
2回答
全对最大流
、、
给定有向加权图，如何求出所有顶点对之间的最大流(或最小边切)。
天真的方法是简单地为每对调用一个像Dinic这样的最大流算法，其复杂性是O((V^2)*E)。
因此，对于所有对，它都是O((V^4)*E)。
是否可以通过一些优化来降低O((V^3)*E)或O(V^3)的复杂性？
浏览 4提问于2012-12-21得票数 8
1回答
正碳烷烃同分异构体计数
、、、
n -碳烷烃是由n个节点组成的无根树，其中每个节点的次数最多为4。例如，表示n的一些低值的枚举列表。
我正在寻找一种算法来计算这种n -碳脂肪族烷烃的数量，给定一个n。
我已经在化学堆栈交换中使用了。我也考虑过动态编程，即从较小的组件构建较大的图形，但我无法处理过多计算相同的异构体。
澄清:碳只是一个比喻。我不希望考虑C16和C17的不稳定性，也不关心立体异构体
浏览 3提问于2016-04-25得票数 5
2回答
我现在已经编写了各种图搜索(A*，DFS，BFS等)。算法重复了很多次。每次，唯一真正的区别是我正在搜索的实际搜索状态，以及如何从现有状态生成新状态。
我现在面临着另一个搜索繁重的项目，希望避免再次编写和调试通用搜索算法。如果我可以定义一个搜索状态类，包括生成连续状态的信息，启发式成本等，并将其插入到某种现有的搜索框架中，就可以为我完成所有繁重的任务，那就太好了。我知道算法并不是特别难编码，但总是有足够的技巧让它变得令人讨厌。
真的存在这样的东西吗？我什么也找不到。
浏览 0提问于2010-12-02得票数 4
回答已采纳
2回答
最小生成树的一个性质证明
、、、
我需要你的帮助，证明如下：G=(V,E)是一个无向连通图，边上有非负权重。设T是G的MST，T'是G的生成树(不是最小树)，因此它支持Weight(T') > Weight(T)。证明了T'中最光滑边的权重不小于T中最重边的权重。
我不知道该如何处理，如果我们让e(u,v) - heaviest edge on T和e'(u',v') - heaviest edge on T'，然后如果我们看看(u,u')定义的剪裁，我们可以使用Kruskal算法来证明e'不是被选择在T或其他方面。
谢谢,
浏览 3提问于2017-01-18得票数 3
回答已采纳
假设您有一组可以并行完成的任务。每个作业都有一个时间要求(第一个作业的时间要求是t_i )。还有一些依赖项，其中第一条是说您必须在作业u_i之前执行作业v_i，您必须尽量减少所需的总时间。
通过将这些关系转换成一个有向无圈图，然后使用它来确定并行处理哪些关系，这很容易做到。
如果我不清楚，这里有一个例子。假设你有5个有时间要求的工作-- 2，9，3，12，5，而你必须在5之前做3件，5之前做4件，1之前做3件，2之前做1件。那么你能做的最好是17件。这是你的爸爸：
+---> 1 (2) ---> 2(9)
|
3 (3)
|
+----> 5 (5)
^
浏览 4提问于2014-05-07得票数 0
回答已采纳
2回答
给定n <= 200000节点和m <= 200000边的加权无向图。边权重(整数)最高可达1e9。存在q <= 200000查询。每个查询提供两个节点u v和一个整数界限p (<= 1e9)。如果在u和v之间有一条路径，路径中的每个边权重都是<= p，那么答案是yes no。
请注意，路径不必是最短的。路径上的最大权重是<= p。天真的方法当然是行不通的。如何快速回答查询(以O(n，lg，n)或类似的方式)？
浏览 4提问于2017-04-02得票数 1
我正在努力提高我对树木再生的概念理解。你会说-- For循环与数组的关系就像递归与树的关系一样--这是一个很好的类比吗？
如果要搜索数组中的任何内容，可以使用循环。如果要搜索树中的任何内容，可以使用递归。在数组中，当我们遍历越来越多的元素时，我们用变量来跟踪结果。在树中，我们使用返回语句+参数+变量来跟踪结果。
浏览 1提问于2022-03-31得票数 0
1回答
现在，我知道凝聚是自下而上的方法，而分裂是自上而下的方法。但是，我不知道他们在具体的过程中有什么不同。例如，它们是否都使用邻近矩阵来计算样本之间的任何成对距离？此外，如果设置所有相同的参数，像相同的连接准则，相同的cluster...do目标数，它们最终得到的结果是完全相同的？
浏览 1提问于2021-02-21得票数 1
回答已采纳
我有200个数据点，每个点都是代表位置的3个数字的列表。我想从这个3D空间中采样N=100点，但有一个约束，即每两个点之间的最小距离必须大于0.15。下面的脚本是我采样点的方式，但它一直在运行，永远不会停止。此外，如果我设置了一个大于某个值的N，代码将无法找到所有N个点，因为我随机采样每个点，它会到达一个点，在这个点上，不能对不太靠近当前点的点进行采样，但实际上，如果点分布非常“密集”(但仍然满足大于0.15的最小距离)，N可能会比这个值大得多。有没有更有效的方法来做到这一点？ import numpy as np
import random
import time
def get_ran
浏览 77提问于2020-09-16得票数 0
2回答
您将使用二进制堆而不是二进制搜索树的场景有哪些？
我对每个结构都有一个基本的了解。如果可能的话，我希望你能对此发表意见。
浏览 2提问于2018-09-17得票数 0
1回答
正如维基百科所说：
最小生成林是其连通部分的最小生成树的结合。
为了找到最小生成树，我们可以使用例如、或。
我们可以用什么算法来寻找最小生成森林？
浏览 2提问于2017-05-16得票数 2
回答已采纳
3回答
我目前正在优化电网规划，而MST没有很好地解决这个问题，因为如果到主电网的连接是一个辐射点，所有的电力都必须流经一条边，并将经过很长的“电气距离”到达每个耗电量点。
我正在研究的问题可能是最小化MW*distance或有功功率矩，但这会产生一个非线性问题。
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的距离)。
通过这种方式，我只是购买更长更细的电缆，这是一种更便宜的解决方案，较短，较厚的电缆。
浏览 1提问于2013-06-27得票数 6
1回答
我试图编写一个Python算法，它将为二叉树中的整数路径找到最大和。我认为最简单的方法是递归函数，但这似乎不像我想的那样工作。我怎样才能修改这个函数，使它找到绝对的最大路径？到目前为止，我可以确认这棵树的工作情况很好，因为我为它编写的高度函数是按预期工作的。
class Node:
def __init__(self, data):
self.right = self.left = None
self.data = data
class Solution:
def insert(self, root, data):
if not
浏览 0提问于2019-01-19得票数 1
回答已采纳
2回答
我是最小生成树的新手，并试图找出在任何特定情况下使用哪种MST算法。有没有人能举几个例子，说明哪种MST算法比其他算法更合适
浏览 3提问于2013-01-04得票数 2
回答已采纳
5回答
设G= (V，E)是无向图。若F.中G的每个圈至少有一条边，则称边的F⊆E集为⊆反馈边集。
(a)假设G未加权。设计了一种有效的求最小大小反馈边缘集的算法.
(b)设G是一个具有正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
我的解决方案(需要建议)：
( a) 最小大小反馈边集：，由于图是不加权的，我们可以使用DFS。我们像往常一样从任何顶点开始DFS。当我们遇到一个后边缘，我们把它插入到一组反馈边。当DFS完成时，这个集合将是答案。
( b) 最小权反馈边集：由于图是加权的，所以我们可以使用Kruskal。但是Kruskal通常以最小重量的边缘开始。如果我们可以否定所有的
浏览 6提问于2012-05-29得票数 15
嗨，我正在做下面的算法。这是问题的图片，我对以下问题的答案是: I-f f-g f-g g-d d-a g-c a-h a-b这条路是最小生成树的正确路径吗？如果不是的话，我还需要参加哪个vt考试？
浏览 3提问于2020-05-28得票数 1
2回答
加权图G的最小瓶颈生成树是G的生成树，使得生成树中任意边的最大权最小。MBST不一定是MST (最小生成树)。
请举一个例子，说明这些陈述是有意义的。
浏览 2提问于2013-01-12得票数 35
回答已采纳
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。
我用Prim算法找到了最小生成树。。
我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树吗？
浏览 1提问于2019-03-17得票数 0
回答已采纳
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
1回答
那么我该如何解决这个问题呢？我需要一个程序，它从标准输入读取一个正整数n，并将顶点集{1，2，3...n}上所有不同的有根、有序、带标签的树的表示写入标准输出。
对于输出，我需要使用树t的以下线性文本表示L(t)
If t is empty then L(t) = ().
If t has root n and children, in sibling order, C = (c1; c2; : : : ; ck), then
L(t) = (n, (L(c1), L(c2), : : :, L(ck)))
where, L(ci) denotes the linear textual
浏览 1提问于2013-09-29得票数 0
1回答
霍夫曼最小方差编码
、、、
众所周知，具有最小方差的Huffman码是最好的。我研究了整个波兰语/英语互联网，我发现:要构建具有最小方差的Huffman代码，您需要使用以下方法之一(当然，节点的概率是最重要的)：
选择表示最短树的节点
选择最早创建的节点(考虑启动时创建的leafs )。
问题是，我找不到这些方法正确性的任何证据。有人能证明这些吗？
我很乐意澄清任何事情。
浏览 4提问于2013-02-03得票数 2
3回答
我想问一下，Esau-Williams算法有没有可能有用的地方？我知道它是用来解决CMST问题的，但我找不到任何可能出现CMST问题的地方。
浏览 2提问于2013-05-13得票数 1
2回答
我需要编写一种算法，以求给定无向图的最小命中集F，即包含图的每个圈中的最小边的集合，使F与任意给定圈的交集不为空。我编写了一种算法，它首先使用深度搜索来查找图中所有可能的循环，然后在每个循环中取最小边缘，并将其放入一个集合中(在该集合中，我删除重复的循环)。
然而，我被要求在多项式时间内完成这项任务，但我不太确定我的算法是否完成了。例如，我添加了一个计数器来解决从A开始的以下图，我的DFS方法被调用了34次：
有人能帮我算出我写的算法的运行时间吗？它是功能性的，但它似乎效率很低。谢谢
下面是我的DFS方法的代码。MHS是起类似节点作用的基本数据结构。它们有一个标记和一个链接列表，其中包含
浏览 1提问于2016-02-15得票数 0
回答已采纳
1回答
我有一个我的教授给我的关于用Kruskal算法找到MST的代码。但是，我不明白到底需要什么
int parent[10]
当我们使用这些函数时会发生什么？
find()
和
uni()
下面是他给我们的完整代码。
#include <stdio.h>
int parent[10];
int find(int i)
{
while(parent[i])
{
i=parent[i];
}
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i
浏览 1提问于2019-06-03得票数 0
回答已采纳
1回答
假设我对计算生成树有三种限制：
约束度(例如:生成树中的节点只能连接到其他3个节点)有界直径(例如:所有边的权重之和后，不能超过100)。
2.1。如果可能，显示满足此criteria.Both的所有子树
有什么解决这个问题的好算法不会让我发疯吗？我将不得不使用相当大的输入(1000+节点)来运行它，所以它的复杂性也不会太高。
浏览 0提问于2010-07-27得票数 3
1回答
我一直在尝试理解极大极小算法在tic tac toe游戏的中间状态的工作原理。但我不能这样做。我知道最小最大算法在每一步都会为玩家返回最好的状态。如果这些州是这样的
在游戏的最后阶段，更容易理解的是，为玩家带来优势或最大分数的状态是最佳配置。在这个例子中，我们可以看到在叶子上分数为'1‘的状态是最好的状态。但在中间阶段或游戏开始时会发生什么。
假设我们一开始有3个位置，或者玩家可以通过玩某个位置来达到这些状态。这些位置进一步导致了下一步的电路板配置。来自初始/开始节点的三个分支中的每一个最终将导致在叶节点上用“1”表示的胜利，或者在叶节点上用“-1”表示的失败，或者
浏览 19提问于2017-06-23得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
