问题标签 [kruskals-algorithm]

在我参加的编程课上，我们学习了 Bellman-Ford SSSP 和 Djikstra 的 SSSP，我们了解到 Bellman-Ford 是基于 Kruskal 的最小生成树算法，而 Djikstra 是基于 Prim 的最小生成树算法。

我们被告知要记住 Djikstra 和 Prim 都在本地级别上运行，因为您根据已经选择的边和节点进行比较，这对我来说很有意义。我们还被告知要记住 Bellman-Ford 和 Kruskal 在全局级别上运行，因为您选择最小的边权重，而不管之前选择的节点如何。

对于 Kruskal 的算法，我可以理解为什么我们可以认为这是全局的，因为您实际上只是选择最轻或最小的边缘权重。但是对于 Bellman-Ford 的算法，我只是不明白它是如何被认为是全局的，因为您仍然需要担心之前选择的节点和边。Bellman-Ford 到底是如何基于 Kruskal 算法的，它是如何被认为是“全球”运作的？

根据视频，我编写了 Kruskal 算法。但我有“小”问题——不是找到最低的权重，而是发现我的权重最高。这听起来可能很有趣，但我找不到我犯错的地方。

和主要算法。权重保存在称为“weightmat”的二维矩阵中。Vertex 是顶点的数量，Edges 是带有变量 v1,v2,weight 的结构体。使用这个结构，我创建了边数组。：

我正在尝试按照成本增加的顺序来实现图的所有可能生成树的列表。我正在使用Sorensen 和 Janssens (2005)的算法。该图初始化如下：

在此之后，有必要找到具有一些限制的图的最小生成树，例如 Edge(2)-(4) 不应该在 MST 中，而 Edge(1)-(2) 应该在那里。

对于边缘排除，可以使用 remove_edge_if(..) 从图中删除边缘。

但是我应该如何确保其中一条边始终位于生成树中？我试图在 Kruskal 函数的输出中添加一些 Edge，但它显然不起作用。它产生图的 MST + 添加的边：

是否可以以 Kruskal 算法知道包含什么和不包含什么的方式标记边缘？

以下代码应该从邻接矩阵中找到最小生成树：

它适用于 6 个顶点和以下矩阵：

但是对于 13 个顶点和以下矩阵：

发生此错误：

错误发生在第 17 行：while (parent[i])

VS汽车：

I saw a question in codechef where the objective is to select edges from a graph such that selected edges do not form a cycle and also product of weights of all the selected edges is maximum.In the editorial it is given that prim's and kruskal's algorithm works here.Infact it is given that it works for maximizing any symmetric monotonic function of edges. So what exactly is symmetric monotonic function and where else can we use this algorithms.

世界上有N顶点和M边。有三种类型的边：类型“AB”、“BC”和“CA”。

有 A、B 和 C 三个人。每个人都可以使用一条边当且仅当它的类型名称包含该人的姓名。（例如，A 可以使用 AB 类型和 CA 类型的边）

我想选择一些边，这样对于所有人来说，图形都是连接的。因此，如果我们制作一个由 AB 类型和 CA 类型的边组成的图，则该图应该是连通的。（这也应该适用于 AB/BC、BC/CA 型）

我应该如何解决这个问题？有两个版本

1. 如果我想最小化所选边的数量怎么办？
2. 如果我想最小化所选边的总成本怎么办？

这是我尝试过的。

主要是，如果它连接 X 和 Y 的两个图，则添加类型为“XY”的边非常好。所以，首先添加所有非常好的边，然后添加一些连接至少一个图的边为一个人。

• 如果我无限地打乱边缘的顺序，这可能是一个很好的解决方案，但我不确定这一点，它不能解决第二个问题。

• 我有一些贪婪的策略：首先为 A 制作一个连接图，A 的数量（或成本）最小，然后是 B，然后是 C。打乱人的顺序（因此算法将应用 6 次）

我有一种强烈的感觉，这个问题是 NP-hard，但不能将问题变成众所周知的 NP-hard 问题。

我正在尝试尽可能高效地实施 Kruskal。

对于运行时效率，使用堆或排序算法对边缘进行排序有区别吗？

还有哪些其他技术可以使 Kruskal 算法更有效地工作？

基本上，除了检查顶点 u 和 v 是否不在同一个组件中之外，我还试图通过添加一个条件来修改 Kruskal 的算法。我隐约了解 union-find 数据结构的工作原理，所以我想检查一下我是否真的得到了正确的想法。

鉴于我有一个无向图 G = (V, E) 和一个包含 V 中的一些顶点的集合 A（顶点 A ⊂ V 的子集），我想捕获 V 中每个顶点 u 的实例（循环） ，你也在这个集合A中找到。我正在考虑使用：

这会因为设置参数不同（因此标签不同）而不起作用吗？我只是想确认...

为了澄清，我需要知道一条边 (u, v) 是否包含集合 A 中的一个顶点。我试图使用 Union-Find 来实现这一点（因为 find() 需要 O(1) 时间），而不是遍历集合 A 来比较每个元素......谁能告诉我这是否可能？还是我应该只使用数组遍历方法？

谢谢你。

我必须在 Java中实现Kruskal 算法。

我有一部分是按重量排序边缘，但是当我不得不考虑保存每棵树的集合的结构时，我有点迷茫。

我认为有一个集合向量，其中每个集合代表一棵树。但是如果我必须合并两棵树，我不知道该怎么办。从向量中删除两个元素并添加一个新的组合元素？

有没有一种结构可以使它更容易？

我需要的是：

• 迭代主要集的所有集
• 将元素添加到其中一个集合，或
• 创建一个新集并将其添加到主要集
• 合并其中的两个集合（当然，删除它们的单数版本）

我是 matlab 编码的新手，我想知道如何绘制访问最小生成树中所有点的游览（是的，TSP/TSM）。我得到了一组 20x2 矩阵的点，我能够找出这些点的 MST，我需要帮助弄清楚如何计划以最小的可能距离游览这些点？

我的 MST 的 adj 矩阵是，

从 kruskal 算法中获得，用于绘制完整图的 MST。

我的，从 kruskal 函数获得的相邻加权矩阵是，

任何指导将不胜感激。