问题标签 [minimum-spanning-tree]

正如我的问题所说，我想知道为什么我们在Prim 算法中使用优先队列？它如何使我们免于使用幼稚的方式（是的，我听说过，但不知道为什么）。

如果有人可以逐步解释邻接列表，我将非常高兴。我正在使用 Cormen 的书。

伪代码：

我正在考虑使用 std::vector 然后 std::make_heap(); 作为存储边的优先级队列。

与问题“边缘 - 权重关联”和 Tamás 的回答相关，我编写了以下代码来获取从原始向量权重中提取的 mst 树的弧权重。我将在迁移到 igraph 0.6 时使用此代码。

有些人在代码中看到了一些错误或改进，两者都像 igraph 使用一样。

谢谢，吉列尔莫。编码：

我的作业有以下问题：

给出一个 O(n+m) 算法来确定边 e 是否会成为图的 MST 的一部分

（我们可以在这项任务中获得其他人的帮助，所以这不是作弊。）

我认为我可以做一个 BFS 并找出这条边是否是两层之间的一条边，如果是的话，这条边是否是这些层中最小的。但是当这条边不是 BFS 树的树边时我能说什么呢？

参考 Ada 中的 Kruskal 算法，我不知道从哪里开始。

在实际编写程序之前，我试图仔细考虑所有内容，但是对于我应该使用哪些数据结构以及如何表示所有内容，我非常迷茫。

我最初的想法是在邻接列表中表示完整的树，但是阅读 Wikipedia 中的算法状态create a forest F (a set of trees), where each vertex in the graph is a separate tree，我不确定如何在不快速变得混乱的情况下实现这一点。

它说要做的下一件事是create a set S containing all the edges in the graph，但我再次不确定最好的方法是什么。我正在考虑一系列记录，带有to,from和weight，但我迷失在forest.

最后，我试图弄清楚我如何知道一条边是否连接两棵树，但我再次不确定做这一切的最佳方法是什么。

我想知道是否有一种算法可以计算有向图中的最小生成树（最佳分支），给定所有这些根顶点之间的一组根顶点，但不仅仅是一个根顶点和图中的所有其他顶点.

给定一组根顶点 [1,4,6] 和一个图 G，如下图所示：

...算法应该在同一张图片上返回类似绿色子图的东西。

我想得到这样一个 MST，它连接提供给算法的所有根顶点。我倾向于认为可能算法的结果是图 G 的子图，其中包含 G 的所有根顶点和一些其他顶点。

笔记：

1. 我知道有向图没有 MST，但有Chu-Liu/Edmonds 算法。
2. 我猜这种算法的结果（如果实际上可能的话）将返回一个最佳分支，其中包括图的一些顶点以及所有根顶点。

我想修改 Prim 的算法，以便它找到最大生成树如何做到这一点

我正在阅读有关 Cormen 等最小生成树的信息。以下是通用的最小生成树。

假设我们有一个连通的无向图 G = (V, E)，权重函数为 w:E->R，我们希望找到 G 的最小生成树。这里我们使用贪心方法。这种贪心策略由以下“通用”算法捕获，该算法一次生成一条边的最小生成树。该算法管理一组边 A，保持以下循环不变。

在每次迭代之前，A 是某个最小生成树的子集。

问题

1. 在不变量中，“A”是某个最小生成树的子集，作者是什么意思？这个陈述中的“一些”是什么？我教过只有一个 MST。

2. 在上面的伪代码中，作者所说的“A 不是生成树”是什么意思？即，while 循环如何以及何时退出？

3. 在“一些”最小生成树的伪代码中，我的理解只有一个。我对吗？

任何人都可以用小例子解释一下吗？

谢谢！

假设我有一个加权无向图 G = (V,E)。每个顶点都有一个元素列表。

我们从顶点根开始，开始寻找所有出现的具有值x的元素。我们希望通过最少的距离（就边权重而言）来发现所有出现的具有值x的元素。

按照我的想法，MST 将包含所有顶点（以及因此满足我们条件的所有顶点）。因此，揭示所有事件的算法可以通过找到从根到所有其他顶点的最短路径来完成（当然这将在 MST 上完成）。

编辑：正如路易斯指出的那样，如果任意选择根，MST 将不会在所有情况下都起作用。但是，为了清楚起见，根是输入的一部分，因此可能只有一个 MST（假设边缘具有不同的权重）。这个生成树实际上将具有从根开始到图中所有其他顶点的所有最小成本路径。

在一个示例问题中，我得到了一个加权图 G = (V, E) 的 MST T。问题是，如果要将一个新顶点 v 及其所有边添加到图中，那么计算这个新 G* = (VU v, E*)。

到目前为止，我唯一的想法是：

两个问题：

1. 如何处理可能已断开连接的顶点
2. 这绝对不是 O(|V|log|V|)

我怎样才能做到这一点？

我正在阅读有关最小生成树算法的信息。提到了cut。无向图 G = (V, E) 的一个割 (S, VS) 是 V 的一个分区。如果一条边的权重是穿过该割的任何边中的最小值，则该边是穿过该割的轻边。

Kruskal 和 Prims 算法中如何使用上述定义？

我不明白 Kruskals 和 Prim 的算法中如何使用 cut

谢谢