腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
我们
可以
使用
Union-Find
数据结构
来
检测
有
向
图中
的
圈
吗
?
、
、
、
、
我知道
可以
使用
DFS和BFS
来
检测
有
向
图中
的
圈
。我想知道
我们
是否
可以
用以下方法
检测
有
向
图中
的
圈
联合查找 还是不想? 如果是,那是怎么做
的
?和 如果
我们
不能,那为什么呢?
浏览 23
提问于2020-04-12
得票数 13
回答已采纳
1
回答
验证无
向
图是否
有
圈
、
、
但我还是不能理解,这些问题太老了,无法回答……另请参阅但我就是不能理解让它工作
的
过程。 到目前为止,我所做
的
全部工作就是初始化并提供图形。找到了从顶点A到顶点B
的
最短路径。
浏览 0
提问于2015-07-02
得票数 0
2
回答
为什么Prim或Kruskal
的
算法不能用于
有
向
图?
、
、
、
Prim和Kruskal
的
算法用于寻找连通和无
向
图
的
最小生成树。为什么不能在有
向
图上
使用
它们呢?
浏览 1
提问于2014-03-26
得票数 23
回答已采纳
2
回答
使用
JGrapht在有
向
边权重
图中
寻找负
圈
、
、
可以
使用
JGrapht在有
向
边权重
图中
找到负
圈
吗
?我浏览了Javadoc,发现我
可以
使用
CycleDetector
来
检测
周期,但不是专门用来
检测
负周期。CycleDetector
可以
找到周期,但如果不以某种方式探索它们,您就无法判断它们是否是负
的
。谢谢!
浏览 28
提问于2016-08-04
得票数 1
1
回答
有
向
图上
的
Floyd
圈
检测
算法
、
如何
使用
Floyd
的
圈
检测
算法
来
计算
有
向
图中
的
圈
的
长度?我遇到
的
大多数链接都解释了Flyod在链表上
的
循环算法,但是如何将相同
的
算法用于
有
向
图?
浏览 2
提问于2016-08-11
得票数 2
1
回答
在着色
图中
寻找具有单个不同着色边
的
圈
、
给定一个边上有红/蓝着色
的
一般无
向
图,我希望能够
检测
到
图中
恰好包含一条蓝边
的
所有
圈
。有没有一个已知
的
算法
来
解决这个问题?我知道如何
使用
DFS方法在一般
图中
检测
循环,并且
可以
通过回溯和计算找到循环后
的
蓝边数量
来
检测
单蓝边循环,但据我所知,这种解决方案将导致边二次时间复杂度。还有更好
的
吗
浏览 14
提问于2021-04-25
得票数 3
1
回答
为什么要
使用
DFS
来
查找无
向
图中
的
圈
,
使用
拓扑排序
来
查找
有
向
图中
的
圈
?
、
、
、
对于无
向
图,如果
我们
需要找到一个
圈
,
我们
使用
深度优先搜索,如所述,这是一种众所周知
的
方法,也是最优
的
。 但对于
有
向
图,建议
使用
拓扑排序。我
的
问题是,为什么
我们
不能
使用
我们
用于无
向
图
的
相同技术,
来
检查
有
向
图中
的
圈</
浏览 3
提问于2013-05-28
得票数 6
回答已采纳
1
回答
创建图形c++
的
逻辑
、
我正在做一个项目,在这个项目中,我得到了一个权重为A或B
的
边列表。我最终需要确定是否
可以
创建一个具有'x‘个A边数
的
生成树。现在,我正在尝试列出在创建最小生成树时
使用
的
所有边,并通过列出我
使用
过
的
顶点来做到这一点。如果
使用
了其中两个顶点,则会丢弃该边。我遇到
的
问题是,一旦我到达我
的
图
的
末尾,我经常会得到两半没有连接
的
图,因为连接这两半
的
边已经被
使
浏览 2
提问于2016-11-25
得票数 0
1
回答
有
向
图中
最长
圈
的
逼近
、
、
、
、
在有
向
图中
寻找最长
圈
(循环i是指没有节点重复
的
循环)是一个NP难问题,否则
我们
可以
判断该图是否为Hamiltonian图。我
的
问题是:对于这个问题
有
任何α-逼近多项式算法
吗
?
浏览 2
提问于2020-02-06
得票数 1
回答已采纳
1
回答
此算法是否正确
检测
有
向
图中
的
循环?
、
我
有
一个在有
向
图中
找到
圈
的
方法。 给定一个
有
向
图G= (V,E),假设G中有一个顶点w,使得存在一条从w到
图中
所有其他顶点
的
路径。考虑以下在
图中
查找循环
的
方法。
使用
顶点w作为源,在G上运行BFS。如果
我们
遇到另一个顶点两次,
我们
声称
我们
找到了一个循环。如果每个顶点只相遇一次,
我们
就断言G中不存在
圈</e
浏览 0
提问于2014-05-15
得票数 0
1
回答
C++中带负循环
的
Floyd-Warshall
、
、
、
、
我正在
使用
Floyd-Warshalls算法进行图搜索,不知道如何改变它
来
防止负循环。a:b;}for(int i = 0; i < n; i++)
浏览 3
提问于2013-05-15
得票数 1
回答已采纳
2
回答
使用
BFS
检测
周期
、
、
、
我知道这是一个常见
的
问题。但在许多地方,我读到
使用
BFS
的
循环
检测
对于
有
向
图是不可能
的
。一个例子是这个链接 我认为
我们
可以
使用
BFS实现有
向
图
的
拓扑排序。如果存在拓扑序,则
我们
可以
说图是无
圈
的
,否则它是循环
的
。这不可能
吗
?
浏览 0
提问于2017-11-18
得票数 1
11
回答
寻找无
向
图中
的
所有
圈
、
我需要一个在无
向
图中
找到所有简单循环
的
有效算法。我知道成本可能是指数级
的
,问题是NP-完全
的
,但我将在一个小
图中
使用
它(最多20-30个顶点),并且
圈
的
数量很少。经过长时间
的
研究(主要是在这里),我仍然没有一个可行
的
方法。以下是我
的
搜索摘要: ->非常好
的
描述,但没有解决方案 ->仅在有
向
浏览 4
提问于2012-09-11
得票数 72
5
回答
如何检查边是否在某个周期内?
、
我
有
一个hw问题,它要求一个算法
来
检测
在任何包含任何给定边'E‘
的
无
向
图中
是否存在任何
圈
。该算法
的
运行时间为O(N)线性时间。
有
什么提示
吗
?
浏览 0
提问于2011-10-12
得票数 12
1
回答
动态
有
向
无圈图上有效计算可达权和
的
数据结构
、
、
、
我
有
一个
有
向
无圈图,其中每个顶点都有一个“权重”属性。来自初始顶点
的
可达顶点是所有可通过沿着一个或多个边到达
的
顶点
的
集合,从初始顶点开始。可达权和是从初始顶点到
的
顶点上
的
所有权重之和。此外,我
可以
在
图中
任意添加有
向
边和顶点,但是图总是保持无
圈
的
。 是否
有
任何
数据结构
,我
可以
用它
来
扩充图,从而有
浏览 3
提问于2022-01-03
得票数 1
1
回答
在无
向
图中
是否
有
有效
的
算法
来
求最长
圈
的
长度?
、
、
我想知道
有
什么有效
的
算法
来
求
图中
最长
圈
的
长度
吗
?算法不需要知道循环中
的
顶点是什么,只需要知道长度。
浏览 0
提问于2019-04-11
得票数 0
回答已采纳
2
回答
BFS
检测
不应该在其中
的
周期
我已经实现了一个BFS算法
来
检测
图中
的
循环,这是以下代码: if(rootstring name; vector <node *> adj;这是我构建
的
图grp->addEdge("A","C"
浏览 0
提问于2012-02-28
得票数 0
1
回答
图论-当一个节点
的
所有边都包含在一个循环中时
、
、
、
、
给定有
向
或无
向
图,
有
许多算法
可以
找到
圈
。然而,我正在寻找一种特定类型
的
循环。一个
圈
,
图中
的
一个节点0.n
有
"k“向外
的
边,它
的
所有k个边都包含在这个循环中。也就是说,
我们
节点
的
所有边缘只连接到构成循环
的
其他节点。
我们
有
一个
圈
(这次是在一个无
向</e
浏览 1
提问于2018-03-23
得票数 0
1
回答
判断一条边是否属于某个循环
的
有效算法
、
、
、
我正在尝试构造一个有效
的
算法,得到无
向
图和边e(u,v),并决定这条边是否属于
图中
的
某个
圈
,而不是所有的
圈
!我
的
方法是从
图中
取出边( u,v),然后运行BFS
来
查看v是否仍然
可以
从u到达。如果是,那么原始图就有一个包含e
的
圈
,否则就没有。但是我不太确定如何调整算法,以确定边是否属于图
的
所有
圈
。
浏览 11
提问于2017-12-30
得票数 2
回答已采纳
1
回答
如何通过替换循环
来
最小化图
的
顶点?
、
如何通过删除回路
来
最小化
有
向
图
的
顶点数量?有没有
可以
在这里改编
的
算法? 已经
有
一个关于删除
图中
的
圈
的
问题,但我特别询问通过删除
图中
的
圈
来
最小化顶点
的
数量。
浏览 20
提问于2021-08-08
得票数 0
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
图书推荐:算法
有向无环图检测
3分钟带你系统的了解Python集合与基本的集合运算
无向图
10种常用的图算法直观可视化解释
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
活动推荐
运营活动
广告
关闭
领券