检查 v 是否是 MST 中的叶子
Checking if v is a leaf in MST
我有这个问题：
给定无向图G = (V,E), V ∋ v 和非负权重W 求是否存在一棵最小生成树(MST) 其中v 是一个叶子，如果存在，return它。
我考虑过使用prim算法找到MST并检查v是否是其中的叶子。如果 v 不是叶子，我会找到第二个 MST 并检查它。问题是时间复杂度会太高。我确信还有另一种方法可以解决这个问题，但我不知道如何解决。你能给我一些关于如何处理这个问题的线索吗？
"generate all MSTs and check if v is a leaf in any of them" 的问题是图中 MST 的数量 can be enormous：它可能与 n ** (n-2) 一样多，其中n是节点数。
更好的方法是观察给定图的所有 MST 具有相同的总权重。所以更有效的算法可以像这样工作：
- 应用标准算法找到
G 的 MST。令 total_weight 为其总重量。
- 应用标准算法找到
G - v 的 MST，即没有节点 v 的图。让mst_without_v成为这个MST，让weight_without_v成为它的总权重。
- 如果
v 有一条权重为 total_weight - weight_without_v 的边，则将这条边添加到 mst_without_v 和 return 中。否则，return null.
如果算法 return 是一个图，那么它是 G 的 MST，因为它跨越 (G - v) + v = G，它是一棵树（因为它是由一棵树与一个添加了叶子），并且它具有正确的总重量。
如果算法 returns null，则 G 的 MST 不存在，其中 v 是叶子。否则，从这样的 MST 中删除 v 会得到总权重错误的 G - v 的 MST。
我认为即使kaya3建议的算法是正确的，如果你正在学习算法，也很难为它写一个正式的证明，所以我会建议一个更优雅的解决方案，它很容易证明。另外，我建议对 kaya3 算法进行编辑，使证明更容易一些：
算法 1:
- 运行 Prim 算法 from v 优先考虑所有未连接到 v 的边。（例如，可以通过添加一个非常连接到 v 的边的数量很少）。
- 如果 v 是算法发现的 MST 中的叶子 return 为真。否则，return 错误。
我会给你一个提示来证明它是真的：因为你从 v 开始 Prim 那么它肯定会选择从 v 出来的最亮的边缘，然后它会继续选择其他边缘只要这些边的权重小于或等于从 v 出来的边，就不会连接到 v。如果它选择了从 v 出来的边，那么没有它就无法完成 MST，或者它的重量更小比任何其他边缘的权重。
我有这个问题：
给定无向图G = (V,E), V ∋ v 和非负权重W 求是否存在一棵最小生成树(MST) 其中v 是一个叶子，如果存在，return它。
我考虑过使用prim算法找到MST并检查v是否是其中的叶子。如果 v 不是叶子，我会找到第二个 MST 并检查它。问题是时间复杂度会太高。我确信还有另一种方法可以解决这个问题，但我不知道如何解决。你能给我一些关于如何处理这个问题的线索吗？
"generate all MSTs and check if v is a leaf in any of them" 的问题是图中 MST 的数量 can be enormous：它可能与 n ** (n-2) 一样多，其中n是节点数。
更好的方法是观察给定图的所有 MST 具有相同的总权重。所以更有效的算法可以像这样工作：
- 应用标准算法找到
G的 MST。令total_weight为其总重量。 - 应用标准算法找到
G - v的 MST，即没有节点v的图。让mst_without_v成为这个MST，让weight_without_v成为它的总权重。 - 如果
v有一条权重为total_weight - weight_without_v的边，则将这条边添加到mst_without_v和 return 中。否则，returnnull.
如果算法 return 是一个图，那么它是 G 的 MST，因为它跨越 (G - v) + v = G，它是一棵树（因为它是由一棵树与一个添加了叶子），并且它具有正确的总重量。
如果算法 returns null，则 G 的 MST 不存在，其中 v 是叶子。否则，从这样的 MST 中删除 v 会得到总权重错误的 G - v 的 MST。
我认为即使kaya3建议的算法是正确的，如果你正在学习算法，也很难为它写一个正式的证明，所以我会建议一个更优雅的解决方案，它很容易证明。另外，我建议对 kaya3 算法进行编辑，使证明更容易一些：
算法 1:
- 运行 Prim 算法 from v 优先考虑所有未连接到 v 的边。（例如，可以通过添加一个非常连接到 v 的边的数量很少）。
- 如果 v 是算法发现的 MST 中的叶子 return 为真。否则，return 错误。
我会给你一个提示来证明它是真的：因为你从 v 开始 Prim 那么它肯定会选择从 v 出来的最亮的边缘，然后它会继续选择其他边缘只要这些边的权重小于或等于从 v 出来的边，就不会连接到 v。如果它选择了从 v 出来的边，那么没有它就无法完成 MST，或者它的重量更小比任何其他边缘的权重。