腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
在
删除
边
之后
,
有没有
一种
有效
的
方法
可以
在
生成
树
图中
找到
组件
的
大小
?
algorithm
、
graph-theory
、
graph-algorithm
、
coding-efficiency
、
spanning-tree
我
的
任务是
在
包含N节点
的
生成
树
图中
高效地处理Q查询。 每个查询都引用我需要处理
的
一条
边
,并且我应该输出
图中
删除
该
边
后剩余
的
两个
组件
的
大小
。我现在
的
想法是从由该
边
连接
的
两个节点启动DFS,确保DFS永远不会遍历该
边
本身。这样,对于O(Q * N)
的</
浏览 34
提问于2020-09-13
得票数 2
3
回答
图有两棵/三棵不同
的
最小
生成
树
?
algorithm
、
graph
、
graph-algorithm
、
minimum-spanning-tree
我正在尝试寻找
一种
有效
的
方法
来检测给定
的
图G是否有两个不同
的
最小
生成
树
。我还试图
找到
一种
方法
来检查它是否有3种不同
的
最小
生成
树
。我考虑过
的
最简单
的
解决方案是运行Kruskal
的
算法一次,然后
找到
最小
生成
树
的
总权重。然后,从
浏览 1
提问于2013-05-16
得票数 6
1
回答
如何
找到
权重不超过k
的
反馈集
algorithm
、
graph
、
graph-algorithm
、
depth-first-search
任意无向加权图
的
反馈集是
边
的
子集,
在
去除子集中
的
边
后,剩下
的
图是无圈
的
。谢谢!
浏览 5
提问于2020-03-17
得票数 0
回答已采纳
1
回答
两个具有公共
边
的
图上
的
最小
生成
树
algorithm
、
graph
、
tree
、
minimum-spanning-tree
、
undirected-graph
给出了两个具有加权
边
的
完备图,
在
两个学习
的
MST在给定
的
边
子集上有公共
边
的
约束下,分别在这两个图上
找到
了两个最小
生成
树
(MST)。请注意,这两个图有相同
的
顶点数,但
边
的
权重是不同
的
。例如,如果这两个图是具有顶点{1,…,d}
的
完全
边
加权图.我们要求两个学习
的
MST
在<
浏览 3
提问于2015-03-25
得票数 2
2
回答
加权无向
图中
的
成对总成本
algorithm
、
graph
、
graph-theory
假设我们有一个加权无向图,其中,对于任意两个顶点,都有一条唯一
的
路径连接它们。这里有n顶点和n - 1
边
,每条路
的
代价都是c_i。现在,如果每条连接两个给定顶点
的
路径都有一定
的
成本,这取决于它经过
的
道路,那么我们如何
有效
地计算所有城市之间
的
总成本呢?例如,每条道路
的
费用
可以
是它经过
的
第一条道路和最后一条道路
的
费用之和,也
可以
是它经过
的
每条道路<e
浏览 0
提问于2017-01-14
得票数 2
回答已采纳
2
回答
必要时移除边缘并分割连接
组件
(C++,Boost)
c++
、
algorithm
、
boost
、
graph
我有一个很大
的
图(顶点
的
数目
可以
在
5万到10万之间,邻接矩阵不需要稀疏)。
图中
的
边
可以
删除
/添加,并且在这些更改
之后
,我想更新
生成
的
连接
组件
结构。我以
一种
简单
的
方式实现了这一点,我
在
C++中使用BFS搜索自己(跟踪连接
组件
if
的
unordered_map
的<
浏览 0
提问于2014-07-25
得票数 4
回答已采纳
1
回答
寻找跨越给定最小
生成
树
的
最小权完全图
algorithm
、
graph
、
minimum-spanning-tree
设T= (V,E)是一棵具有已知代价
的
|V|顶点和|E| = |V-1|
边
树
。构造了一个最小权完全图G= (V,E'),它
的
最小
生成
树
为T。 跨T作为其唯一MST
的
最小权重完整图G如下: 我试图
找到
一个
浏览 2
提问于2015-01-05
得票数 3
回答已采纳
4
回答
如何确定
删除
给定
的
循环是否会断开图
的
连接
algorithm
、
graph
我已经看到了
在
图中
检测循环
的
方法
,但我仍然没有
找到
一种
检测“桥式”循环
的
方法
。因此,假设我们
在
一个连通(和无向)
图中
找到
了一个循环。我们如何确定移除此循环是否会断开图形
的
连接?通过移除循环,我
的
意思是移除循环中
的
边
(因此顶点不受影响)。
一种
方法
是清楚地计算
删除
之前和
浏览 2
提问于2015-10-09
得票数 8
1
回答
图中
求最小
生成
树
(MST)?
algorithm
、
graph
、
tree
、
minimum-spanning-tree
、
kruskals-algorithm
给出了一个边上有权
的
无向图G和2 different最小
生成
树
: T,T‘对于T‘中没有T’
的
每一个
边
e,T‘中有一个
边
e',它不在T中,所以如果在T中用e'代替e (我们称之为T_new),那么它仍然是G
的
最小
生成
树
。我认为我离
找到
正确
的
算法太近了,但我坚持了一点:由于T是一棵
树</
浏览 9
提问于2021-05-09
得票数 1
3
回答
寻找特定v有k度
的
生成
树
algorithm
、
depth-first-search
我知道我们应该使用DFS,但我不明白
之后
我们要做什么。
浏览 2
提问于2017-02-01
得票数 1
回答已采纳
1
回答
生成
树
的
定义
python
、
networkx
、
graph-theory
、
spanning-tree
我想检查我对
生成
树
(对于无向图和连通图)
的
理解是否正确。
浏览 0
提问于2019-04-03
得票数 0
回答已采纳
1
回答
从MST中
删除
节点:与Kruskal重新连接
algorithm
、
graph
、
graph-algorithm
、
kruskals-algorithm
我有一个MST,需要
删除
一个节点。我知道
在
O(log^4(n))中有一个算法,但是由于MST包含不到50个节点和2500条
边
,并且我已经对边进行了排序,所以我想给出一个更基本
的
解决方案:我为每个连接
的
组件
创建并集,并在它们上运行Kruskal我
的
推理是,这应该是可行
的
,因为我们有一个MST,并在
删除
节点后通过最便宜
的
方式重新连接它。然而,我没有
找到
任何
可以
证实这是
有效</e
浏览 8
提问于2020-05-16
得票数 0
回答已采纳
1
回答
使无向图有向
python
、
graph
、
directed-acyclic-graphs
我有一个无向图,完全图,并希望将它转换成一个有向无圈图,
在
每个节点之间有一个(单向)路径。为了开始,我想添加随机
边
和停止一旦所有节点连接。需要研究
的
是一个算法(使用Python,但任何语言都
可以
)。B \ / v,但在这种情况下,所有无向
边
都会变成有向
边
与
生成
树
浏览 5
提问于2014-10-08
得票数 1
1
回答
如何去除无权有向
图中
的
圈,使
边
数最大化?
algorithm
、
graph
、
graph-theory
、
directed-graph
、
cyclic-graph
设G是包含圈
的
无权有向图。我正在寻找
一种
算法,它查找/创建所有的无圈图G',它由G中
的
所有顶点和G
的
一个
边
的
子集组成,小到足以使G‘无圈。这意味着: G‘不满足于1和2,因此G’比G‘和G'’具有更多
的
边
,G'‘是无圈
的
。 背景:原始图G模拟元素之间
的
成对排序。由于
图中
的
循环,这不能作为对所有元素
的
排序来利用。因此,
浏览 0
提问于2011-06-08
得票数 15
回答已采纳
1
回答
判定
图中
是否存在k-圈
的
有效
近似算法
algorithm
、
graph
、
graph-theory
、
adjacency-matrix
我有一个非常大
的
稀疏图G (大约一亿个节点,大约五千万条
边
),我想
找到
一种
有效
的
算法(希望是O(1)或节点+
边
的
数量为亚线性
的
),以某种概率预测这个
图中
存在长度为k
的
循环。
在
实际使用中,相对于G
的
大小
,k将非常小(
在
30到90之间)。还
可以
保证k将始终为偶数。G也是一个随机图,所以我不希望有任何一致
的<
浏览 8
提问于2019-03-10
得票数 0
1
回答
如果
删除
边缘,更新最小
生成
树
algorithm
、
graph
、
tree
、
runtime
、
big-o
我对以下问题有困难:从G中
删除
一个
边
以
生成
一个新
的
图,这样新
的
图仍然是连通
的
。给出了
一种
使用T
在
O(|E|)时间内为新图寻找最小
生成
树
的
算法。
浏览 1
提问于2015-06-17
得票数 1
回答已采纳
1
回答
图中
圈中
边
的
最大权重
algorithm
、
graph
、
minimum-spanning-tree
如果不属于MST
的
图中
的
边
的
权重减少了,我试图修改最小
生成
树
。我
在
堆栈溢出上看到,首先将边缘连接到MST,现在MST中正好有一个循环,而在循环特性中,
可以
从MST中
删除
权重最大
的
边
?如何在那个周期中
找到
最大重量
边
?
浏览 1
提问于2015-01-02
得票数 2
回答已采纳
3
回答
证明不存在包含最大加权
边
的
最小
生成
树
algorithm
、
graph
、
minimum-spanning-tree
假设有一个图G,它
的
所有边都有对应于不同整数
的
权重。所以没有两条
边
具有相同
的
权重。设E是G
的
所有边,emax是E中具有最大权重
的
边
。图G
的
另一个性质是每条
边
e都属于图G中
的
某个圈。我必须证明G
的
最小
生成
树
不包含
边
emax。 我
可以
理解为什么这是真的,因为所有的
边
都是不同
的
,并且每条
边<
浏览 2
提问于2013-11-28
得票数 6
回答已采纳
5
回答
如何在无向
图中
寻找反馈
边
集
algorithm
、
graph
、
kruskals-algorithm
若F.中G
的
每个圈至少有一条
边
,则称
边
的
F⊆E集为⊆反馈
边
集。(b)设G是一个具有正
边
权
的
加权无向图。设计了
一种
有效
的
求最小权反馈边缘集
的
算法. ( a) 最小
大小
反馈
边
浏览 6
提问于2012-05-29
得票数 15
2
回答
如何证明MST上始终存在极小极大路径
algorithm
、
data-structures
、
graph-algorithm
、
minimum-spanning-tree
无向
图中
的
是两个顶点v,w之间
的
一条路径,它最小化了路径上边
的
最大权重。设T是给定图G=(V,E)
的
最小
生成
树
.如何证明,对于V中
的
任意一对顶点v,w,
在
v与w之间总是存在一条完全
在
T上
的
极小极大路径。 我试图假设T上没有完全
的
极小极大路径,但我不知道如何得到一个矛盾。
浏览 0
提问于2017-03-25
得票数 3
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
我敢说,这图绝对跟你想象中的不太一样!
最小生成树-克鲁斯卡尔算法-Kruskal算法
多变量数据可视化之属性云刷
10种常用的图算法直观可视化解释
大规模并行图计算:从理论到实践
热门
标签
更多标签
活动推荐
运营活动
广告
关闭
领券