最小生成树

最小生成树是图论中的一个概念，指在加权连通图中，所有顶点连接在一起的权值最小的树。它可以用来解决一些实际问题，如网络设计、电路布线等。最小生成树有许多算法，其中Kruskal算法和Prim算法是最常用的两种。Kruskal算法的基本思想是按照权值从小到大的顺序选择边，如果这条边不会形成环路，则将其加入到最小生成树中；Prim算法的基本思想是从任意一个顶点开始，每次选择距离该顶点最近的一个未访问过的顶点，并将其加入到最小生成树中。这两种算法的时间复杂度都是O(ElogE)，其中E表示图中边的数量。