最小生成树 例子

最小生成树是一种在图论中寻找一棵包含图中所有顶点，且所有边的权值之和最小的树。例如，假设我们有一个包含5个顶点的无向图，每条边的权值分别为1、2、3、4和5。我们可以使用Kruskal算法来找到这个图的最小生成树。首先，我们将所有的边按照权值从小到大排序，得到的顺序为1、2、3、4、5。然后，我们从权值为1的边开始，尝试将其添加到最小生成树中。如果添加这条边会导致形成一个环（即包含重复的顶点），则我们放弃这条边。否则，我们将这条边添加到最小生成树中，并更新剩余边的列表。重复这个过程，直到所有的边都被尝试过。最终，我们得到的最小生成树包含了5个顶点，总权值为6（1+2+3）。