具有 1 个加权边的最短路径生成树与 MST
Shortest path spanning tree with 1 weighted edges vs MST
我目前正在研究图及其算法，我注意到一个我不知道如何准确证明的问题：
如果我们有一个连通的无向图 G=(V,E)，并且每个 边的权重都为 1，是否可以说每棵生成树都从根的最短路径构建，是最小生成树吗？
我 运行 http://visualgo.net/sssp.html 中的一些示例，对我来说似乎这个问题的答案是正确的，但有人可以告诉我如何证明这一点？
我想到的另一个问题是，另一个方向也是正确的吗？
TLDR：不一定
考虑具有单位权重的三角形图 - 它具有三个顶点 x,y,z，以及所有三个边 {x,y},{x ,z},{y,z} 有单位权重。
任意两个顶点之间的最短路径为直达路径。同意吗？
但是，要满足图中 MST 的条件，您必须将连接 3 个顶点的 2 条边放在一起。例如说 {x,y}, {y,z}。这并不表示任何一对顶点之间的最短路径。
因此，你的命题是错误的:)
每棵树恰好有 n - 1 条边。由于所有权重都等于 1，因此 G 的每个生成树的总权重为 n - 1。对于最小生成树也是如此。所以答案是肯定的。
我目前正在研究图及其算法，我注意到一个我不知道如何准确证明的问题：
如果我们有一个连通的无向图 G=(V,E)，并且每个 边的权重都为 1，是否可以说每棵生成树都从根的最短路径构建，是最小生成树吗？
我 运行 http://visualgo.net/sssp.html 中的一些示例，对我来说似乎这个问题的答案是正确的，但有人可以告诉我如何证明这一点？ 我想到的另一个问题是，另一个方向也是正确的吗？
TLDR：不一定
考虑具有单位权重的三角形图 - 它具有三个顶点 x,y,z，以及所有三个边 {x,y},{x ,z},{y,z} 有单位权重。
任意两个顶点之间的最短路径为直达路径。同意吗？
但是，要满足图中 MST 的条件，您必须将连接 3 个顶点的 2 条边放在一起。例如说 {x,y}, {y,z}。这并不表示任何一对顶点之间的最短路径。
因此，你的命题是错误的:)
每棵树恰好有 n - 1 条边。由于所有权重都等于 1，因此 G 的每个生成树的总权重为 n - 1。对于最小生成树也是如此。所以答案是肯定的。