minimum-spanning-tree

1热度

1回答

我想知道从这个图中的Prim算法的顶点顺序：我的回答是{a,c,b,e,f,g,d}，但也有人说{a,c,b,e,d,f,g}或{a,c,d,e,b,f,g}。哪个答案正确？

0热度

1回答

我们都知道存在诸如kruskal's和prim的MST算法的算法来查找连通图的MST（最小生成树）。我知道的另一种方法是从图中的每个循环中删除具有最大值的边缘，直到没有更多循环。结果图将是MST。我不确定的问题是，如果连接图具有不同的权重，那么图中每个周期的最小边将包含在图的每个MST中？我们能够证明/反驳这个吗？

0热度

1回答

使用邻接表来表示最小生成树

我一直在试图解决类的问题。问题是：给定一个无向图摹，发现摹内的最小生成树。为了通过这个问题，我的函数必须采取，并返回，一邻接表。但是，我不确定如何去将输入和输出表示为邻接列表。 from collections import defaultdict class Graph: def __init__(self,vertices): self.V= vertices

0热度

1回答

如何找到路径的最大边将所有对MST

的顶点作为我们假设我们有一个已知的最小生成树。我们的任务是找出每对顶点之间存在路径上的最大优势。举个例子，我们有以下的最小生成树： 1---10---2 \ 5\ \ 4---4---3 顶点1和2之间，我们与成本10 顶点1和3之间的边缘，我们具有成本5. 顶点3和4之间的边缘，我们有与成本的边缘4. 对于每个路径的最大边缘：路径1-

0热度

1回答

是对的：所有边权重都是正数，那么连接所有顶点并且总重量最小的任何边权都必须是最小生成树？

这个问题是从演练23.1-7演变而来的算法介绍。原来的问题是： 23.1-7 认为，如果一个图的所有边缘权重是肯定的，那么边缘的任意子集，连接所有的顶点和具有最小的总重量必须为树。举一个例子来说明，如果我们允许一些权重是非正的，那么同样的结论就不会遵循。但我认为如果图的所有边权重都是正数，那么连接所有顶点并且具有最小总权重的边的任何子集都必须是最小生成树。是我的必然吗？如果没有，请给我一个反

2热度

1回答

使特定节点的程度最小化的最小生成树

我们如何找到使节点度数最小的最小生成树v（在所有最小生成树中）？会修改Kruskal算法，使得如果有几个边具有相同的重量，我们选择不接触的那个v解决问题？

1热度

1回答

从字典创建一个稀疏矩阵

我正在做一个学校项目，我给了一个无向图G，并且我认为在G内找到了最小生成树。我想我会使用Scipy (https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html)中的minimum_spanning_tree。但要做到这一点，我必须为它提供一个

1热度

1回答

具有顶点权重和边权重的最小Spanninjg树

我正在解决有关最小生成树的问题。因此，图中的每个节点都是一个城市，并且可能具有连接两个节点的权重边，这是在两个城市之间建设公路的成本。问题主要在于告诉我们建设道路的最低成本，并让所有的城市都有一定的联系。我可以通过使用Prim或kruskal算法轻松解决这个问题，解决我最大的问题。棘手的部分是现在：每个城市（节点）可以有一个机场，每个机场都有一次性成本（如果你决定建造它）。如果两个城市都有机场，

1热度

1回答

总是有一些MST是最短路径树吗？

在我的计算机科学课程。我们的教授给了我们这个期末考试的问题，我有麻烦：玛丽莎和乔尔会在客场之旅，他们希望确保他们在每个城市停止（想街道作为图的边缘，城市作为顶点）。他们想要到达每个城市，他们将从家乡纽约Vertexville的城市开始。他们希望尽可能提高燃料效率，不希望两次看到相同的景色，因此他们要求在可能的公路行程路线中穿过的高速公路/道路是一个称为最短路径树的概念（换言之，在他们可能的路线中

0热度

1回答

java - 如何找到MST中最大的加权边缘？

根据标题，问题非常简单。我有一个现有的MST，不带有加权边缘，有V个顶点。给定一个起始节点和结束节点，是否有一个有效的算法在O(V)时间运行，返回MST中最大的权重？谢谢！