minimum-spanning-tree

0热度

1回答

这里看到的PriorityVertex类型是什么？我也在写一个getMinSpanningTree方法。 Prim's Algorithm

0热度

1回答

我在使用Prim的这个实现跟踪找到的最短路径的总权重时遇到了一些麻烦。该路径似乎是正确的，但我无法弄清楚权重的总和在添加到存储路径的数组中（因为它只写入所用的存储路径）。我试着总结pCrawl-> weight作为每个顶点被添加到MST，但似乎是图上所有权重的总和。与值键[]相同。我的问题是每次向MST添加一条路径时总结的内容，以反映添加了所有最短路径时MST的总权重。下面是我使用的代码：用

3热度

1回答

遍历Prim的MST算法的邻接矩阵

我有一个遍历Java加权邻接矩阵的问题。我想要做的是使用Prim的算法从矩阵中获得最小生成树的权重。我到目前为止的代码如下： public int findPrim(int[][] matrix) { ArrayList <Integer> checkThese = new ArrayList < >(); checkThese.add(0); //Starting ver

0热度

1回答

从最小生成树的二值图像创建网络无向加权图

我试图在阈值图像的裂缝中的像素之间创建最小生成树。当我去除噪点时，像素并不总是接触，所以我试图用图形连接它们。 Python 2.7我已经设置了一个图像阈值，所以低于阈值的所有东西都显示为白色，其他都是黑色的。我一次对一个65x65的窗口进行阈值设置，并将任何少于10个像素的窗口设置为白色。 import networkx as nx import matplotlib.pyplot as pl

1热度

2回答

MST的cheriton-tarjan算法的复杂性

几天前我在这里看到一篇关于Cheriton-Tarjan算法的文章，我认为这是对Boruvka算法的改进。我想我知道它是如何工作的，但我不明白为什么这个算法的复杂性是O（mloglogn）。有人可以向我解释吗？日Thnx。

0热度

1回答

检查图形是否使用BFS连接并打印MST

我在邻接列表中存储了一个包含节点1,2,3,4 ...的图形。我写了这段代码来做广度优先搜索（BFS）。 BFS的工作原理非常完美，但我不知道程序是查找图形是连接还是断开连接，然后打印图形的最小生成树（如果连接的话）？我存储在邻接表图的一个例子：对BFS 1 3 4 2 4 3 1 4 4 2 1 3 ，代码： int visit[999] = { 0 }; Q.enqueue(0

2热度

1回答

这个算法与prim算法类似，在第9-10行中做了什么？

我明白这个问题有点类似于在这个论坛上提出的另一个问题，但我的问题是一个具体问题，而另一个问题没有提供答案。我将引用的算法如下。我知道这个算法循环遍历图中的每个顶点并赋值为无穷大。它也赋予集合V中的“s”为0.我猜“s”是父节点？然后它创建一个集合“A”来存储访问节点。虽然该集合不包含集合“V”中的所有顶点，但它将选择一个节点，其中最小值尚未在“A”中。然后它遍历所有的顶点adj。到这个节点。它比

9热度

5回答

更快的次优MST算法？

我正在为此苦苦挣扎。我们可以使用Kruskal算法或MST的Prim算法得到MST。而对于 “次优” MST，我可以：第一个GET MST使用上面提及的任何算法。对于来自MST的最佳边缘的每个V-1： a。首先删除或标记边缘 b。继续计算MST没有边缘 c。比较和记录下来的是“次优” MST与先前的迭代最后，我们有“次优” MST 但这运行在O（VE），其中V是NUM顶点和E是边数。

1热度

1回答

我需要使用什么数据结构来构建Java中的最小生成树？

我有一个类Node类似于Java的类Point与x和y坐标，我画到JPanel。我试图在欧几里德图上为一组这样的节点创建一个最小生成树，然后我将其绘制到面板上。但是我无法真正弄清楚首先需要创建树的数据结构。我试过使用LinkedLists和ArrayLists来实现Prim的算法，但它们似乎使事情变得过于复杂。我应该为此考虑哪些数据结构？

-1热度

1回答

打印出基于等级

对于一个家庭作业二维数组，我们被分配到使生成树对于每个图形，按区域分开他们，后来在升序显示他们的生成树。我有一个函数，它执行广度优先搜索来定义图形中的连通组件，然后将区域馈送给为每个区域执行生成树的函数。我想根据“道路”数量或其具有的非零元素来显示我的最终生成树二维数组。所有2d阵列都是邻接矩阵。我宣布我的类声明的二维数组的数组作为 int** spantreelist[10]; 我的树是