-
3 votesanswersviews
坚持解决最小生成树问题
我已经减少了我在图中找到最小生成树的问题 . 但我希望还有一个约束条件,即每个顶点的总度数不应超过某个常数因子 . 我如何模拟我的问题? MST是错误的道路吗?你知道任何能帮助我的算法吗? 还有一个问题:我的图表有重复的边缘权重,那么有没有办法计算唯一的MST数量?有算法可以做到这一点吗? 谢谢 . 编辑:按度数,我的意思是连接顶点的边的总数 . 重复边缘重量是指两个边缘具有相同的重量 . -
0 votesanswersviews
查找边长为{1,2,3}的图的最小生成树的算法[重复]
这个问题在这里已有答案: A fast algorithm for minimum spanning trees when edge lengths are constrained? 2个答案 我最近一直在研究Prims / Kruskals算法,以便在图中找到最小生成树,我对以下问题感兴趣: Let G be an undirected graph on n vertices with m ... -
2 votesanswersviews
叶片约束MST问题的简化为哈密顿路径问题
众所周知,计算具有最小可能叶数的生成树是NP完全的 . 但我无法弄清楚这个问题的多项式时间减少到哈密顿路径问题 . 我的指数减少: if(hamiltonian path exists for whole graph) min leaves = 1; return; else for each vertex of the graph if(hamilton... -
0 votesanswersviews
Prim和Kruskal的算法复杂性
给定具有权重的无向连通图 . w:E - > {1,2,3,4,5,6,7} - 意味着只有7个重量可能 . 我需要在O(n m)中使用Prim算法和在O(m * a(m,n))中使用Kruskal算法找到生成树 . 我不知道该怎么做,真的需要一些关于权重如何帮助我的指导 . -
0 votesanswersviews
在c中设计Prim实现的数据结构
我正在尝试在C中实现Prim的MST算法 . 我有一个设计问题 我实现了一个带有整数的min-heap,我们可以提取-min,减少key和insert-key . 现在正如我在Prim中所理解的那样,我需要保持每个顶点的权重,邻居信息 . 我的一些想法是: 1]定义结构 struct node { int vertex; int weight; int neighbor; ... -
2 votesanswersviews
查找树的父节点以创建尽可能短的树高
我有一个无向图表示为欧几里德权重的邻接矩阵 . 我用它来表示更大的完整图形的最小生成树 . 我想要找到的是图中的单个节点,当用作根节点时,创建尽可能短的树高 . 我想出的是使用每个节点作为根执行深度优先遍历,并跟踪所见的最短高度 . 有没有更快的方法来实现这一目标? -
0 votesanswersviews
在Minimax路径寻找解决方案中找到路径和最大权重边缘?
我目前正在编程分配:给定一个大的加权未连接图(1 <V <2000,0 <E <100 000) . 找到沿“最小加权路径”从“源”到“目标”的最大加权边 . 到目前为止我所拥有的是将图存储在AdjacencyList中(IntegerPair的Vector of Vector,其中第一个整数是邻居,第二个是边的权重) . 我还使用Prim算法获得了最小生成树: priva... -
1 votesanswersviews
计算无向图的最小生成树
考虑具有n个顶点和m个边的无向图 . 假设边缘有两种类型:m1个红色边缘和m2个绿色边缘 . 因此m = m1 m2 . 红色边缘具有权重1,绿色边缘具有权重2.设计和分析有效算法以计算这种图形的最小生成树 -
0 votesanswersviews
MST相关算法
给定具有权重函数 w:E->R 的无向和连通图 G(V,E) ,边 e(u,v) 属于E.哪种算法以线性运行时复杂度运行,可以确保是否存在包含边e的最小生成树? -
1 votesanswersviews
最小生成树变化算法
在接受采访时我被问到以下问题,我无法找到有效的解决方案 . 这是问题所在: 我们想 Build 一个网络,我们给了n个节点和m个边 . 边缘是双向的,我们知道边缘的成本 . 边缘的所有成本都保存在数组C中,因此C [i,j]表示边缘i-j的成本 . 如果节点i,j未连接,则C [i,j]是无限的 . 现在我们也知道节点的确切K能够无线地与具有该属性的其他节点通信(用于无线传输) . 要将无线技术... -
12 votesanswersviews
最小生成树和最短路径树是否始终共享至少一条边?
我正在研究图论,我对最小生成树和最短路径树之间的联系有疑问 . 设 G 是一个无向连通图,其中所有边都加权 with different costs . 设 T 为 G 的MST,让 T 为某个节点 s 的最短路径树 . 是否 T 和 T 保证分享至少一个优势? 我相信这并非总是如此,但我找不到反例 . 有没有人有关于如何找到反例的建议? -
0 votesanswersviews
使用邻接列表表示最小生成树
我一直试图解决课堂问题 . 问题是: 给定无向图G,找到G内的最小生成树 . 为了传递这个问题,我的函数必须接收并返回一个邻接列表 . 但是,我不确定如何将输入和输出表示为邻接列表 . from collections import defaultdict class Graph: def __init__(self,vertices): self.V= verti... -
0 votesanswersviews
最小生成树和最短路径
我遇到了一个问题: 给定具有整数权重(正和负)的连通有向图,开发一种算法,找到两个顶点之间的最短路径 . 我认为我可以使用最小的生成树算法,如kruskal,然后使用dijkstra的算法来表明,因为在MST中,每个顶点只有一个进入边缘,dijkstra的算法甚至可以用于负权重 . 这听起来像copasteic吗? 附:我无法证明MST包含每个顶点的有向图的最短路径 .