网络x：所有生成树及其关联的总权重
给定一个简单的无向网格网络，如下所示： import networkx as nx from pylab import * import matplotlib.pyplot as plt %pylab inline ncols=3 N=3 G=nx.grid_2d_graph(N,N) labels = dict( ((i,j), i + (N-1-j) * N ) for i, j i
..
minimum-spanning-tree相关内容
找到所有最小生成树
可能的重复: 所有最小生成树实现 如何以有效的方式在无向图中找到所有最小生成树? 解决方案 对于学术答案的道歉...但 Knuth 的 TAOCP，第 4 卷，第 4 卷正是关于生成所有生成树(第 26 页).当他谈到生成(生成)树时，有一些思考，但是您在 TAOCP 中的最佳选择.
..
Prim 和 Dijkstra 算法之间的区别?
Dijkstra 和 Prim 算法之间的确切区别是什么?我知道 Prim 会提供 MST，但 Dijkstra 生成的树也将是 MST.那么具体的区别是什么? 解决方案 Prim 的算法构造了一个最小生成树 为图，它是连接图中所有节点的树，并且在连接所有节点的所有树中总成本最小.然而，MST 中任意两个节点之间的路径长度可能不是原始图中这两个节点之间的最短路径.MST 很有用，例如，如果
..
使用Kruskal算法的最小生成树
我如何使用Kruskal算法计算im R(3.0.0-Linux x32)最小生成树? 我使用以下igraph(0.6.5)库创建一个加权全图: set.seed(1234567890)g
..
唯一的最小生成树充分必要的条件
给出图G，这是充分必要的条件，因此该图具有唯一的最小生成树?此外，如何证明这些条件? 到目前为止，我发现这些条件是: 1)对于将V(G)分为两个子集的每个分区，每个子集中具有一个端点的最小权重边是唯一的. 2)在G的任何循环中，最大重量边都是唯一的. 但是我不确定这是否正确.即使万一是正确的，我也无法证明其正确性. 解决方案 实际上，唯一的MST有必要的充分条件.在
..
不带三角剖分的欧式最小生成树
我一直在浏览有关使用Delaunay三角剖分技术找到EMST(Euclidean MST)的文章，但同时也读到可以通过扫掠线算法找到EMST的地方.因为这样做会更容易实现，所以我想实现它而不是使用现有的库. 任何人都可以引导我/将我定向到具有该算法说明的(可能是免费的)论文/资源的链接吗? 解决方案 来自此和此应该可以帮助您入门.他们都使用扫掠线算法来获取MST.
..
在巨大的完整图中找到MST的算法
让我们假设一个完整的图表包含25000个以上的节点。每个节点本质上都是平面上的一个点。 它有6.25亿条边。每个边的长度应存储为浮点数。 我需要一种算法来查找其MST（在普通PC上）。 如果我采用Kruskal算法，则需要首先对所有边进行排序，但我什至无法承受将所有边同时存储在内存中。 如果我选择Prim的算法，很难同时评估在堆中存储多少个边，但是其中大多数可能会非常算法开始后
..
确定给定的加权图是否具有唯一的MST
我正在寻找一种算法(或其他方法)来确定给定的加权图在O(ElogV)中是否具有唯一的MST(最小生成树)? 我对权重一无所知(例如weight(e1)！= weight(e2))，如果该图仅具有一个唯一的MST，则算法仅返回True；否则，则返回False. 我首先使用Kruskal的算法，然后检查find-set(u)== find-set(v)，以便在MST中有一个圆圈，但是这种方
..
如何在Haskell中编写MST算法(Prim或Kruskal)?
我可以同时编写Prim算法和Kruskal算法，以在C ++或Java中找到最小的生成树，但是我想知道如何在Oskm中使用O(mlogm)或O(mlogn)来实现它们(纯函数式的程序更好) .非常感谢. 解决方案 如svenningsson所建议的，纸张.)Kruskal的问题在于，它要求您有一个O(log n)联盟查找算法.在此处中描述了具有纯功能接口的联合查找数据结构.在内部使用可变状
..
Jgraph:一般遍历森林穿越
早上好/下午/晚上. 因此，我们的数据结构课程为我们分配了使用以下算法在Java中分割灰度图像的任务: 输入:具有P个像素和数字R的灰度图像. 输出:分割为R个区域的图像 1.将图像映射到原始加权图. 2.查找图形的MST. 3.在R – 1最昂贵的边缘上切割MST. 4.将平均树顶点权重分配给森林中每棵树的每个顶点 5.将分区映射到分割图像上 问题是，他们只是把我们
..
最小生成树的预遍历
有什么方法可以打印MST给出的输出的预遍历（使用Kruskal或Prim的算法）。我很困惑，因为输出可能始终是二叉树。那么，在这里如何进行遍历？普通的DFS可以完成任务吗？ 解决方案 处理此类问题时的主要问题是单词 tree 中的算法问题。主要定义有两个（实际上可能稍有不同）： 树是无环连接（无向）图。 一棵树基本上是一组节点，每个节点都有一个父节点（一个节点除外，称为 root
..
查找跨越给定最小生成树的最小权重完整图
让 T =（V，E）是 | V | 顶点和 | E |的树。 = | V-1 | 边，成本已知。我们想要构建一个跨过 T 的最小权重完全图 G =（V，E'）作为其唯一的最小生成树。 / p> 示例：考虑以下树 T 。 红色中的边具有给定的成本。 由于其唯一的MST而跨越 T 的最小权重完整图 G 以下内容： 我试图找到一种生成此图的（多项式时间）算法。我主要是在寻找技巧，而不是
..
检查边缘是否包含在线性时间中的某些MST中（非明显值）
我正在研究一种算法，以检查所有可能的mst之一中是否包括给定的边。 对于此问题，我们正在考虑使用非唯一值并且我们的边缘e连接顶点A& B。 到目前为止，我有：如果可以从A到B的路径由权重小于或等于边e的权重的边组成， -我们可以说边缘e不是任何MST的一部分。 我在这里是否缺少任何内容/关于更好算法的想法？ 编辑： 关于涉及循环属性的解决方案有何想法-因此，我们认为所
..
通过修改边更新最小生成树
带有MST 的图（正重边）如果将某些边e修改为新值，那么更新MST而不完全重新生成MST的最佳方法是什么。我认为这可以在线性时间内完成。而且，似乎我需要基于以下两种算法：1）e是否已经是MST的一部分，2）新边缘e是否大于或小于原始边缘 解决方案 有4种情况： Edge is在MST中，并且您降低了edge的值： 当前的MST仍然是MST Edge不在MST会降低边的值
..
什么时候应该使用Kruskal而不是Prim（反之亦然）？
我想知道何时应该使用 Prim的算法以及何时使用 Kruskal的可以找到最小的生成树？它们都有简单的逻辑，同样的最坏情况，唯一的不同是实现可能涉及一些不同的数据结构。那么决定因素是什么？ 解决方案 当您的图具有很多边时，请使用Prim算法。 对于具有 V 个顶点 E 个边的图形，Kruskal算法在 O（E log V）中运行如果使用O（E + V log V）的摊销时间内运行。
..
Networkx:为给定的节点集创建完整的图
我有一个列表作为c4_leaves = [56,78,90,112].我正在尝试使用c4_leaves中的这些元素作为节点来创建完整的图形.这是我尝试过的； V_ex = c4_leaves G_ex = nx.Graph() G_ex.add_nodes_from(V_ex) G_ex = nx.complete_graph(4) for u,
..
使用networkx的有向图的生成树
我在networkx中有向图G，我想获得它的最小生成树. 我这样做: T = nx.algorithms.minimum_spanning_tree( G.to_undirected() ) 这是无向的，我想恢复指示，但我不知道该怎么做. 我试过了: G[T.edges()] 最后一行看起来很蟒蛇，但这不是networkx的工作方式，显然... 有人知道怎么做吗? 换
..
找到最小的生成树
能否请您告诉我为什么此MATLAB代码错误?我不明白为什么.提前非常感谢您. function [mst, cost] = prim(A) [n,n] = size(A); A, n, pause, if norm(A-A','fro') ~= 0 , disp(' Error: Adjacenc
..
同一张图的两个最小生成树可以具有不同的边权重吗?
图可以具有许多不同的最小生成树(MST)，但是不同的MST是否可以具有不同的边缘权重集?例如，如果某个MST使用边缘权重{2,3,4,5}，那么每个其他MST是否都必须具有边缘权重{2,3,4,5}，还是其他MST可以使用其他权重集合吗? 给我一个想法的特性是，只有边缘权重不同时，图形才具有唯一的MST. 解决方案 集合必须具有相同的权重.这是一个简单的证明:假设他们没有.让我们将T
..
如何使用最小生成树方法将边连接到图像中的节点
我在手写图像中进行图形匹配的项目，我想用图表表示给定的单词图像，使用下面的算法 算法： 输入：二进制图像B，网格宽度w，网格高度h 输出：图g =（V，E），节点V和边E 1：函数网格（B，w，h） 2：对于i←1到列数C =宽度B / w做 3：对于j←1到行数R = B / h的高度为 4：V =V∪{（xm，ym）| （xm，ym）是段sij的质量中心} 5：对于每
..