什么是生成树

问题描述

精选答案

对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。

常用的生成树算法有DFS生成树、BFS生成树、PRIM 最小生成树和Kruskal最小生成树算法。通俗的来说呢，就是先假设结论错误，即最小生成树的最大边比瓶颈生成树的最大边大，然后删掉最小生成树的最大边，这时候最小生成树会被分成两个部分（两颗树）。那么，在瓶颈生成树中肯定存在连接这两个部分并且比最小生成树最大边小的边（因为毕竟瓶颈生成树人家也是生成树，任意两个部分是肯定有边相连的），那么用这条边替换掉最小生成树的最大边，就会与最小生成树的定义矛盾。

其他回答

造价工程师说

生成树是指对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。

在图论的数学领域中，如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。

生成树是连通图的包含图中的所有顶点的极小连通子图。

图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。