腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(493)
视频
沙龙
2
回答
以
最小
代价
断开
无
向
赋
权
图中
的
两个
节点
algorithm
、
graph-theory
、
np
、
max-flow
假设我们已经给出了一个
无
向
加权图以及一个源
节点
和目的
节点
,我们需要通过删除边来
断开
源
节点
和目的
节点
的
连接,删除边
的
成本就是边
的
权重。我们需要
最小
化
断开
两个
节点
的
成本。 例如 ? 在这里,
断开
0
节点
和6
节点
的
连接需要5分钟
的
成本
浏览 21
提问于2021-07-18
得票数 2
1
回答
使
无
向
图
断开
的
最小
成本
algorithm
、
graph
使
无
向
加权(正
权
)图
断开
的
最小
成本是多少?我有以下想法。 1.找出
图中
所有的桥。那么
最小
重量
的
桥边缘就是ans。2.如果没有桥,这意味着所有
节点
都在一个循环中(我不确定)。然后,我根据它们
的
权重对边缘进行排序,
两个
最小
浏览 1
提问于2012-10-03
得票数 0
1
回答
寻找
无
向
图中
两个
节点
之间
断开
连接
的
最小
权重
java
、
algorithm
我想要得到
无
向
图中
两个
特定
节点
之间
断开
连接
的
最小
权重。
图中
的
每个
节点
和边都有自己
的
权重。 这
两个
节点
可以通过许多不同
的
方式删除一些权重来
断开
连接。因此,我想要得到
断开
连接
的
删除权重
的
最小
值。在下面的例子中,我想要得到Lidcombe和Red
浏览 11
提问于2019-11-12
得票数 0
回答已采纳
1
回答
如何找到权重不超过k
的
反馈集
algorithm
、
graph
、
graph-algorithm
、
depth-first-search
任意
无
向
加权图
的
反馈集是边
的
子集,在去除子集中
的
边后,剩下
的
图是
无
圈
的
。谢谢!
浏览 5
提问于2020-03-17
得票数 0
回答已采纳
4
回答
完全
断开
二部图
的
连接
algorithm
、
graph
、
graph-theory
、
graph-algorithm
、
bipartite
我有一个不连通
的
二部
无
向
图。我想完全
断开
图表
的
连接。我唯一能执行
的
操作是删除一个
节点
。移除
节点
将自动删除其边。任务是
最小
化要删除
的
节点
数量。
图中
的
每个
节点
最多有4条边。通过完全
断开
一个图,我
的
意思是不应该通过链接连接
两个
节点
。基本上是一个空
的
边集。
浏览 1
提问于2012-08-07
得票数 4
回答已采纳
1
回答
赋
权
有
向
图
的
邻接矩阵
algorithm
、
data-structures
、
graph-theory
、
shortest-path
A)设A是具有n个顶点
的
赋
权
有
向
图G
的
邻接矩阵,其中A[i,j]是边i到j
的
权重。如果没有这样
的
边缘A[i ,i]=0。矩阵A^K= A*A*A*...A。如果我们使用+而不是*,并且使用min而不是+,则时隙A^k [i,j]不能用至多k边来描述路径i到j
的
权重。我想找出这个问题表现出什么东西?B)设A是具有n点
的
赋
权
有
向
图(
无
圈多边) G
的
邻
浏览 3
提问于2014-10-18
得票数 0
2
回答
寻找图算法:如何使图快乐?
algorithm
、
graph
、
bioinformatics
背景:在
图中
,如果有奇数负边,则称简单圈为冲突圈;若负边数为偶数(或零),则称为协调圈。例如,在下图
的
左边,图有
两个
相互冲突
的
循环(S1-S2-S3-S1和S2-S3-S4-S2),其他循环是一致
的
。如果一个图没有冲突
的<
浏览 6
提问于2014-09-18
得票数 1
1
回答
照片上
的
Gomory-Hu树不工作了?
python
、
graph
、
igraph
IGRAPH UNW- 3 2 --+ edges (vertex names):这是没有意义
的
,因此,
最小
切割树t应该是一个中心为"3“
的
恒星。显然不是这样
的
..。
浏览 0
提问于2014-08-13
得票数 1
回答已采纳
1
回答
在
图中
找出给定顶点不连通
的
最小
割
graph
、
graph-theory
一段时间前,我读到了一个通用
的
最小
切割算法,它将一个图作为输入,并删除一个min。使
两个
断开
的
组件保持不变
的
边数。 我现在正在处理一个具有10k+
节点
和500k+边
的
无
向
图(
两个
顶点之间没有多条边)。为了给
节点
之间
的
交互赋值,我考虑计算
两个
给定顶点
的
最小
割
断开
(或流相关
的
度量
浏览 1
提问于2012-02-21
得票数 8
回答已采纳
1
回答
如何将弹性添加到
最小
生成树?
algorithm
、
networking
、
tree
、
graph-theory
我有一个完整
的
,加权
的
,
无
向
图。边
权
值是
两个
节点
之间连接
的
代价
,因此
最小
生成树是总
代价
最低
的
边
的
子集,使得图保持连通。MST必须在任何时候都是连接
的
,但不幸
的
是,这些连接并不是很可靠,所以我想在这个图形/网络中添加冗余。 是否有可能计算一个边
的
子集,使总边成本
最小
化,边连通度超过一定
浏览 0
提问于2019-06-27
得票数 1
1
回答
部分所有对最短路径
algorithm
、
graph
给定一个包含许多
节点
的
无
向
赋
权
图,如何计算所有对最短路径
的
一个子集?Dijkstra或Floyd-Warshall都可能会计算额外
的
节点
,这对于我
浏览 0
提问于2017-06-13
得票数 5
1
回答
包含每个
节点
的
无
向
加权图
的
最短圈
algorithm
、
graph
、
graph-theory
问题:在包含每个
节点
的
无
向
加权
图中
寻找最短圈。所有的重量都是正数。一个
节点
可以被访问不止一次,它将问题与哈密顿循环(TSP)区分开来。一种天真的尝试可能是使用
最小
生成树(MST)和回溯来到达起始
节点
。这导致长度为2*MST,但不是
最小
周期。示例:考虑一个具有顶点1、2、3、4和边
代价
为c12=c13=c14=1和c23=c24=c34=100
的
完整图。TSP距离=2 0 2 (1 -> 2 -
浏览 4
提问于2022-08-12
得票数 1
回答已采纳
2
回答
无
向
图和有
向
图
的
最小
生成树算法有什么区别?
algorithm
、
graph
、
tree
、
graph-algorithm
无
向
图MST算法(Prim或Kruskal)是有
向
MST算法(Edmond/Chiu)
的
一般形式吗?为什么很难找到定向情况下
的
MST源代码?我们可以使用
无
向
解来获得有
向
图中
的
MST吗?
浏览 6
提问于2015-01-16
得票数 8
回答已采纳
4
回答
使用
最小
生成树算法
algorithm
、
minimum-spanning-tree
假设我有一个加权
无
向
图G= (V,E).每个顶点都有一个元素列表。 我们从一个顶点根开始,开始寻找具有x值
的
元素
的
所有出现情况。我们希望
以
最小
的
距离(就边
权
而言)来发现所有具有x值
的
元素
的
出现。在我看来,MST将包含所有的顶点(因此也包括满足我们条件
的
所有顶点)。因此,寻找从根到所有其他顶点
的
最短路径(当然,这将在MST上完成)就可以完成发现所有发生
的
所有事件<e
浏览 4
提问于2011-11-17
得票数 2
回答已采纳
2
回答
销毁双向
图中
的
加权边
algorithm
、
graph-theory
、
dynamic-programming
在我最近
的
采访中,我被问到了以下问题:有一个没有圈
的
双向图G。每条边都有一定
的
权重。还有一组
节点
K,它们应该彼此
断开
(通过移除一些边)。K集中任意
两个
节点
之间只有一条路径。目标是
最小
化被移除边
的
总权重,并将所有
节点
(来自集合K)彼此
断开
。 我
的
方法是为K集合中
的
每个
节点
运行BFS,并确定K中所有
节点
对之间
的
所有
浏览 3
提问于2012-11-07
得票数 2
1
回答
对于这个图问题,有没有好
的
算法?
algorithm
、
graph
有一个在边上有权
的
无
向
图(
权
是非负整数,它们
的
和不大,大多数是0)。我需要以
最小
化不同子图之间边
的
权重和
的
方式将其划分为若干个子图(假设20个
节点
的
图到每个5个
节点
的
4个子图)。这听起来有点像
最小
割集问题,但还不够接近。 在另一种方案中-有一堆存储桶,所有的项目恰好属于
两个
存储桶,我需要将存储桶划分为存储桶组,
以
最小</
浏览 1
提问于2010-07-16
得票数 4
回答已采纳
1
回答
Dijkstra与MST
的
关系
algorithm
、
shortest-path
、
minimum-spanning-tree
当我看到时,这个问题突然浮现在我
的
脑海中。为了简单起见,我们可以将讨论限制在
无
向
、加权、连通图上。显然,如果从
图中
选择任意
节点
作为源,Dijkstra不能保证生成MST。然而,它是否保证在一个
无
向
、加权、连通
图中
必须存在一个
节点
,如果我们选择它作为源并应用Dijkstra
的
算法,它将为该图生成一个MST?也许你可以给出一个证据或者一个反例。谢谢!
浏览 1
提问于2020-12-16
得票数 2
回答已采纳
1
回答
找到一条从A到B
的
最短路径最大
的
边
algorithm
、
graph
、
shortest-path
给出具有边
权
的
无
向
图G,给出一组候选边(长度?)和顶点A和B,求出从A到B
的
最短路径最大
的
边。 候选边是虚线。从A到B
的
最短路径是A -> C -> D -> G -> B(成本7)。但是对于边(D,B),最短路径是A -> C -> D -> B(
代价
6),因此算法应该返回(D,B)。我想出了一个蛮力
的
解决方案O((x=1,2)^2 log 将边添
浏览 4
提问于2014-10-06
得票数 3
2
回答
根据给定
的
准则寻找
图中
两个
节点
之间
的
路径--优化任务
algorithm
、
optimization
、
graph-theory
、
pseudocode
、
graph-traversal
我有循环
的
,
无
向
的
加权图G=(V,E)。我需要根据以下规则在
两个
给定
节点
之间找到简单
的
路径(没有循环): 选择此路径,该路径在已找到路径
的
选定
最小
值中具有最大
最小
值。一个重要
的
假设是:
图中
的
节点
数很小:不到15个。解决这个问题
浏览 5
提问于2013-08-27
得票数 1
回答已采纳
2
回答
TSP变种,可能
的
算法?
algorithm
、
graph
、
traveling-salesman
、
approximation
、
np-hard
经典
的
旅行商问题(TSP)定义之一是:在我
的
例子中,我不需要哈密顿路径,我需要
两个
已知顶点之间
的
路径。因此,公式将是: 给定一个加权完全无
向
图,其中三角形不等式成立,
两个
称为源和目的地
的
特殊顶点返回一条
最小
加权路径,该路径恰好访问所有
节点
一次,从源开始,结束于目的地。我记得哈密顿路径是
浏览 4
提问于2013-03-08
得票数 0
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
69.图像分割之二-OpenCV从零开始到图像识别
最小生成树-克鲁斯卡尔算法-Kruskal算法
2024-02-24:用go语言,给你一个 n 个点的带权无向连通图,节点编号为 0 到 n-1, 同时还有一个数组 edges
传统神经网络
文心一言 VS 讯飞星火 VS chatgpt (259)-- 算法导论19.3 2题
热门
标签
更多标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
活动推荐
运营活动
广告
关闭
领券