问题标签 [minimum-spanning-tree]

我有一个 2d 对称矩阵“myMSTdata[][]”，它表示加权边最小生成树 MST（如果没有直接边则为零），我需要在边上以最大权重切割该 MST，以便我有两个子树分区（第 1 部分，第 2 部分）。有什么简单或便宜的方法吗？或者有没有我可以用来这样做的图书馆？

我使用 Kruskal 算法生成了一个最小生成树，我想知道如何存储路径

这是我的最小生成树

我使用 Kruskal 算法生成了这个最小生成树，我很难在两个节点之间生成路径。有人可以帮我处理伪代码吗？我尝试使用邻接列表和邻接矩阵

所以我需要一些帮助来找到一个最小生成树。假设我有邻接列表形式的图表：

第一个字母表示您正在查看哪个节点，数字表示与任何其他节点的连接数。例如，A 有两个连接 - B 和 I 各有一个。之后，字母后面的数字只是表示边的权重。B 的权重为 12，我的权重为 25。所以我最初计划将整个事物表示为一个名为 的字符串数组Graph[8]。每行将是阵列中的不同插槽。我很难弄清楚如何使用 Prims 或 Kruskalls 算法来实现这一点。

我知道 MST 是 delauny 三角剖分的一个子集，但它如何帮助找到最小生成树？当我对 MST 使用 delauny 三角剖分的边缘时，这意味着什么？这与在找到 MST 之前不对一组点进行三角测量有何不同？

因此，似乎确定一条边是否在最小生成树中可以归结为该边是否是某个循环中最重的边的问题。我知道如何使用 DFS 检测边缘是否处于循环中，但如何确定它是否是该循环中最重的边缘？是通过找到循环并选择其中最重的边缘吗？

我想制作一个动态最小生成树。我在 n 个顶点上有一个现有的 MS 树，我从这个新顶点向所有现有顶点添加了一个顶点和边。如何有效地更新新图表的 MST？O(n) 将是最佳的。我还可以使删除顶点操作有效吗？

带有 MST 的图（正权重边）如果某些边 e 被修改为新值，那么在不完全重新制作 MST 的情况下更新 MST 的最佳方法是什么。我认为这可以在线性时间内完成。此外，我似乎需要一种不同的算法，基于 1）e 是否已经是 MST 的一部分，以及 2）新边缘 e 是否大于或小于原始边缘

如果给定一个连通图 G，则将该图拆分为 Ga 和 Gb。如果你找到 Ga 和 Gb 的最小生成树（分别称为 Xa 和 Xb），用最小加权边连接 Xa 到 Xb 是否仍然形成生成树？那棵生成树是最小生成树吗？

到目前为止，这是我的逻辑。我相信几乎按照定义，将 Xa 连接到 Xb 至少会形成一棵生成树。（如果有一个反例会有所帮助）但是，我认为它不会总是形成最小生成树，因为根据图形的结构，您可能能够从 Xa 或 Xb 中删除一条边，然后添加连接它们的边缘，仍然有一棵树。在具有相同权重的多条边在不同顶点处连接 Xa 和 Xb 的情况下，可能会出现这种情况。

到目前为止我的逻辑正确吗？

我正在尝试确定最佳搜索案例以与我编写的搜索算法进行比较。

我有一组标记为“必需”的节点和一个标记为“开始”的节点，其余的标记为“可选”。鉴于我的第一个扩展是“开始”节点，我想找到我需要扩展以发现所有必需节点的最佳节点数。

• 我相信我正在寻找的是最小生成树，但会修剪所有不以“必需”节点结尾的分支。这是斯坦纳树问题吗？
• 如果我的图表未加权，Steiner 树和最小生成树的大小是否相同？
• 如果我能对树的大小说些什么呢？即类似（最小生成树大小的大小=平均最短路径*＃所需节点......我认为这不是真的，但能够根据连通性或其他东西计算平均值会很好）。

几点注意事项：

1. 这不是旅行销售问题，因为我不需要在每个所需节点之间存在路径，我只想发现每个所需节点。
2. 我的图表是无向且未加权的（或就此而言同样加权）
3. 我的图表平均有大约 100 个必需节点，可能还有数千个可选节点