生成树和最小生成树的区别
Difference between Spanning tree & Minimum spanning tree
我一直在阅读生成树的概念及其类型。这是我的理解：
生成树：图G的一个子集，连接所有顶点的边数最少
最小生成树：边权值之和最小的生成树
现在，这是否意味着，在检索 MST 时，
如果我们遇到 G 中的一条路径，它有更多的边（与其他路径相比）但边权重总和的权重最小（与所有其他可能的路径相比），我们不会将其视为 MST？
MST 的概念是否只有在 G 有多个生成树时才会起作用？ else 生成树=MST?
感谢您的帮助！！
- if we come across a path in G which has more edges (as compared to some other path) but least weight on the summation of edge weights(as compared to all other paths possible), we won't be considering it as an MST?
我假设 "path"，你是想写 "tree"？ （“path”是一个完全不同的概念：它只有两个端点，没有分支结构。）
一个tree是一个没有圈的连通图，所以每棵有n个顶点的树正好有n−1边缘。因此，如果一个图有 n 个顶点，那么该图的每个生成树都必须恰好有 n−1 个边。所以如果你有一个子图的边 more 比 n−1 边，那么它不是树，所以它不是生成树，所以 - 作为你已经猜到了——它不是最小生成树。
但是要注意，如果一个子图连接了所有的顶点，那么这个子图必然至少包含一棵生成树；并且除非存在负权重边，否则这些生成树的权重将小于或等于子图的权重。因此，尽管您的示例不是最小生成树，但它很可能包含最小生成树。
- Does the concept of MST comes into play only if we have multiple Spanning trees for G? else Spanning tree=MST?
如果一个图只有一棵生成树，那么那棵生成树就是最小生成树，是的。但请注意，只有当图本身 是 一棵树（在这种情况下它是它自己的最小生成树）时才会发生这种情况；否则肯定会有多个生成树。
当然，即使它有多个生成树，也有可能它们都具有相同的权重无论如何，在这种情况下它们都是最小生成树。
我一直在阅读生成树的概念及其类型。这是我的理解：
生成树：图G的一个子集，连接所有顶点的边数最少
最小生成树：边权值之和最小的生成树
现在，这是否意味着，在检索 MST 时，
如果我们遇到 G 中的一条路径，它有更多的边（与其他路径相比）但边权重总和的权重最小（与所有其他可能的路径相比），我们不会将其视为 MST？
MST 的概念是否只有在 G 有多个生成树时才会起作用？ else 生成树=MST?
感谢您的帮助！！
- if we come across a path in G which has more edges (as compared to some other path) but least weight on the summation of edge weights(as compared to all other paths possible), we won't be considering it as an MST?
我假设 "path"，你是想写 "tree"？ （“path”是一个完全不同的概念：它只有两个端点，没有分支结构。）
一个tree是一个没有圈的连通图，所以每棵有n个顶点的树正好有n−1边缘。因此，如果一个图有 n 个顶点，那么该图的每个生成树都必须恰好有 n−1 个边。所以如果你有一个子图的边 more 比 n−1 边，那么它不是树，所以它不是生成树，所以 - 作为你已经猜到了——它不是最小生成树。
但是要注意，如果一个子图连接了所有的顶点，那么这个子图必然至少包含一棵生成树；并且除非存在负权重边，否则这些生成树的权重将小于或等于子图的权重。因此，尽管您的示例不是最小生成树，但它很可能包含最小生成树。
- Does the concept of MST comes into play only if we have multiple Spanning trees for G? else Spanning tree=MST?
如果一个图只有一棵生成树，那么那棵生成树就是最小生成树，是的。但请注意，只有当图本身 是 一棵树（在这种情况下它是它自己的最小生成树）时才会发生这种情况；否则肯定会有多个生成树。
当然，即使它有多个生成树，也有可能它们都具有相同的权重无论如何，在这种情况下它们都是最小生成树。