标签: minimum-spanning-tree

我正在从geeksforgeeks 文章中研究 Kruskal 的 MST 。给出的步骤是：

\n

1. 按权重非降序对所有边进行排序。

\n

2. 选择最小的边。检查是否与目前形成的生成树形成环。如果没有形成循环，则包括该边。否则，丢弃它。

\n

3. 重复步骤(2)，直到生成树中有(V-1)条边。

\n

我真的不觉得有必要使用不相交集。为了检查循环，我们可以将顶点存储在访问的数组中，并在选择边时将它们标记为 true。循环程序，如果我们发现一条边的两个顶点都在访问的数组中，我们就会忽略该边。

换句话说，我们可以\xe2\x80\x99t而不是存储不相交集的森林，而只存储一个位数组来指示哪些顶点在先前的步骤中已链接到另一条边？

当我看到这个问题的时候我就想到了这个问题。为简单起见，我们可以将讨论限制在无向、加权、连通图上。很明显，如果我们从图中选择任意节点作为源，Dijkstra 不能保证生成 MST。然而，是否可以保证在一个无向、带权、连通图中一定存在一个节点，如果我们选择它作为源并应用 Dijkstra 算法，该节点将为该图生成 MST？也许你可以给出证明或者反例。谢谢！

这是一个消费税:

考虑从加权连通图G中找到边的最小权重连接子集T的问题.T的权重是T中所有边权重的总和.给计算最小权重连通子集T的有效算法.

这是我得到的:

1. 我必须假设权重由正面和负面混合.只有两种重量的混合才能对这种消费有意义.

2. 我将首先对边缘进行排序,因此负边缘将首先出现.

3. 我会考虑使用Kruskal的算法,但应该进行一些修改

4. 因为我欢迎负边缘,我会尝试添加尽可能多的负边缘.

5. 另外,可以添加一些正边缘以便在不是所有负边缘都连接的情况下它们可能需要一些正边缘作为桥接.

好的,上面是我的想法.但是当我试图弄脏手时,我就陷入了困境.

如何始终记录可能的最小重量？

例如,

{0,1}的权重为-20

{2,3}的重量为-10

如果{1,3}的权重为11,那么我当然不希望{1,3}

或者如果{1,3}的重量为9,那么我想要

通过什么样的数据结构,我可以始终保持最小权重和该权重的顶点？

值得注意的是,这个消费的子集寻求的目标edges.

考虑从加权连通图G 中找到边缘的最小权重连接子集T的问题

这意味着仍然需要包含所有顶点.

它也不仅仅是一个MST.考虑如果顶点有两条边,一条是-1,另一条是-2.在普通的MST算法中,只会采用-2的边缘.但在这个消费税中,需要采取-1和-2来进一步降低总体重量.

我查看了以下prim的算法(为了创建最小生成树),我不确定下面代码中的输入值是什么,我认为G当然是发送的图形(邻接矩阵或列表图)我认为值s是起点应该在哪里？此外,如果它是开始,那么您将以何种方式将起始值发送到以下算法？:

from heapq import heappop, heappush

def prim(self, G, s): 
    P, Q = {}, [(0, None, s)] 
    while Q: 
        _, p, u = heappop(Q) 
        if u in P: continue 
        P[u] = p 
        for v, w in G[u].items(): 
            heappush(Q, (w, u, v)) 
    return P 

任何帮助将不胜感激,谢谢!

这是查找最小生成树的正确算法.

将Graph划分为2个相同连接的部分.找到它的最小生成树.使用连接它们的最小边缘连接它们.我试图得到这个算法的反例,但不能.

我现在正在学习最小生成树的主题，我了解了大部分内容，但我仍然有一些不明白的地方。我正在处理无向加权图。

首先，我知道找到 MST 的成本为 O(E*log V)。现在，当我们处理平面图时，我想将其优化为线性时间 - O(V+E)。

其次，我看到了单位平方中 n 个点的例子，并且我成功地证明了权重为 O(sqrt n) 的 MST 是存在的。问题是我找不到找到这个 MST 的算法。

谢谢大家，或者

我在解决有关最小生成树的问题时遇到了一些麻烦。因此，图中的每个节点都是一个城市，并且可能具有连接两个节点的权重边，这就是在两个城市之间修建道路的成本。问题基本上是告诉人们修路的最低成本，并使所有城市都以某种方式连接。我可以通过使用Prim或kruskal算法轻松解决此最大问题的子问题。

现在最棘手的部分是：每个城市（节点）都可以有一个机场，而每个机场都有一次成本（如果您决定建造）。如果两个城市都有机场，则可以使用机场在两个城市之间旅行。现在，我必须计算建造道路和机场的最低成本，以使所有城市都连接起来，但是我很难用网络的其余部分来表示与机场的连接。有人可以帮我吗？也许我对使用MST是完全错误的？

我想出的唯一解决方案是：对于每个有机场的城市，我都会将该城市与另一个有机场的城市连接起来。另外，如果建造两个机场的成本较低，那么建造道路的成本也应考虑在内。我运行kruskal是为了获得最便宜的边缘，但是如果kruskal选择“机场”边缘，我会将其添加到生成树中，然后将这两个机场的成本设为0（如果它们以前没有建造过）。我相信，通过在运行kruskal时进行动态权重更改，我正在破坏获得最低成本的想法。

我想用多个最小生成树分割一个无向图。有一些特殊的（根）节点，我想从中开始构建最小生成树，并且我知道节点之间的每个权重。

有没有什么算法可以解决这个问题？如果没有严格的方法，任何近似的方法对我来说都可以。

我附上两个输出示例。如果你帮助我，我会很高兴。谢谢你。