minimum-spanning-tree

1热度

2回答

我想解决最小生成树问题的一个较难的版本。还有N顶点。还有2M边编号为1,2，..，2M。该图连接，无向和加权。我想选择一些边缘来使图形保持连接并使总成本尽可能小。有一个限制：编号为2k的边缘和编号为2k-1的边缘是并列为，因此应该选择两者或者不应该选择两者。所以，如果我想选择边缘3，我也必须选择边缘4。那么，连接图形的最低总成本是多少？我的想法：我们叫两个边2k和2k+1一个边缘设置。如

1热度

1回答

包含/排除某些边的提升最小生成树

我试图按照成本增加的顺序实现图的所有可能生成树的列表。我正在使用Sorensen and Janssens (2005)的算法。 - （4）不应该在MST和边缘（ typedef property<edge_weight_t, int> EdgeWeightProperty; typedef adjacency_list<vecS, vecS, undirectedS, no_property,

0热度

1回答

在C++中设计Prim实现的数据结构

我想在C++中实现Prim的MST算法。我有一个设计问题我实现了一个min-heap，它需要一个整数，我们可以提取min，减少key和insert-key。现在，据我所知在Prim的我需要维护每个顶点的权重，邻居信息。一些想法我有有： 1]定义的结构 struct node { int vertex; int weight; int neighbor; };

2热度

1回答

如果已添加项目的值发生更改，如何管理堆（最小堆）

我是一名java开发人员（但来自非CS/IT教育背景）。我对算法产生了兴趣，目前我正在尝试实施Prim的计算MST的算法。我已经告诉过，为了让你知道背景，但我的问题与MST无关。我已经实现了我自己的MinHeap，而不是使用Java.util.PriorityQueue（虽然即使当我更改我的代码并使用它时，我也遇到了与前面提到的相同的问题）。我向堆中添加项目，但决定比较的项目的值即使在堆中添加

0热度

2回答

设计一个图，其中最短路径树比最小生成树长

设计一个图的示例，其中shortest path tree比最小生成树长。在最坏的情况下，最短路径树比最小生成树多长时间？

-1热度

1回答

使用Delaunay Triangulation加速Python MST计算

我有一个代码可以让许多点的最小生成树（大约25000个数据集在每个集合中包含40-10000个点），这显然需要一段时间。我正在使用scipy.sparse.csgraph中的MST算法。我被告知MST是Delaunay Triangulation的一个子集，所以有人建议我通过先找到DT并从中找到MST来加速我的代码。有谁知道这会造成多少差异？另外，如果这使得它更快，为什么它不是算法的一部分？如

0热度

1回答

Prim的算法实现不止一次添加顶点

我想在Java中实现Prim算法。我面临的问题是同一个顶点不止一次被添加，因此我的MST的重量会出错。我已经使用了以下的数据结构：标记：长度的数组= | V |，标记为[I] = 48意味着尚未MST，和49是指顶点i是MST。堆：一个长度= | V |的二维数组，其中第一行将给出顶点，第二行将给出相应的wts。 adj_list：图的邻接表表示。 wt_list：由adj_list表示的边

0热度

2回答

在sparce图上执行Kruskal算法的最佳数据结构？

如果对空间没有限制，那么假定图形将被打包，选择什么样的预处理kruskals算法是最好的数据结构。我想使用单链表实现

1热度

1回答

如何在3d空间中使用Prims算法

我想知道如何在三维空间中使用Prim算法。把它放到上下文中：我想计算所有可能的和最短/最有效的方法来在墙上铺设电缆，并考虑3d空间中的一些不可用点/约束。任何想法如何建模（算法以及技术上）？我知道常用的最短路径和最小/最大生成树算法，但直到现在才在2d空间中学习/使用它们。

1热度

2回答

Java网络/树模拟会在一定数量的节点之后进入无限循环

我希望有人能够帮助解决我遇到的问题。首先，我试图删除尽可能多的代码，因为这不会导致问题。我的问题是这样的：当我运行程序时，一切都运行完美，直到我创建了一个包含约130个节点的图。一旦它击中130多个节点，程序将永远在无限循环中运行。我试着用15个节点上的135个节点运行程序，以获得所需的图形密度。为了给出一些上下文，我正在研究模拟，为此我创建了随机图并使用BFS构建生成树。我的问题出现在创