我一直在阅读跨树的概念&其类型。这是我所理解的。
生成树： 是Graph G的一个子集，它有最少的边缘连接所有的顶点。
最小生成树。 这是一棵边缘权重之和最小的生成树 It is a spanning tree where the summation of the edge weights is minimum.
现在，这是否意味着，在检索一个MST时。
如果我们在G中遇到一条路径，它有更多的边(与其他路径相比)，但边权重之和最小(与所有其他可能的路径相比)，我们不会认为它是MST吗?
MST的概念是否只有在G有多棵Spanning树的情况下才会出现，否则Spanning树=MST？
谢谢你的帮助!
- 如果我们在G中遇到一条路径，它有更多的边(与其他路径相比)，但边权重之和最小(与所有其他可能的路径相比)，我们不会把它视为MST吗？
我想你说的 "路径 "是指写 "树 "吧？(A "路径"是一个完全不同的概念：它只有两个端点，没有分支结构）。)
A 树 是一个没有循环的连接图，所以每棵树与 n 顶点正好有 n-1条边。所以如果一个图有 n 顶点，那么该图的每一棵生成树都必须有准确的 n-1条边。所以，如果你有一个子图有 更多 比 n-1条边，那么它就不是一棵树，所以它不是一棵生成树，所以--正如你猜测的那样--它不是一棵最小生成树。
但是请注意，如果一个子图连接了所有的顶点，那么这个子图将必然包含至少一棵生成树；除非有负重量的边，否则这些生成树的重量将小于或等于子图的重量。所以，虽然你的例子不是最小生成树，但它很可能包含一棵最小生成树。
- 只有当我们对G有多个Spanning树时，MST的概念才会出现，否则Spanning树=MST？
如果一个图只有一棵Spanning树，那么这棵Spanning树就是最小Spanning树，是的。但是请注意，只有当图本身出现这种情况时 是 一棵树（在这种情况下，它是自己的最小跨度树）；否则它肯定会有多棵跨度树。
当然，即使它有多棵跨度树，也有可能它们的权重都是一样的。反正在这种情况下，它们都会是最小跨度的树。