最小生成树算法Prim Kruskal

最小生成树算法是图论中的重要问题，旨在找到一个包含图中所有顶点的树，并且使得树的边权和最小。Prim算法和Kruskal算法是解决此问题的两种经典算法。Prim算法从一个顶点开始，逐步扩展生成树，每次选择与当前生成树相连的最小权重边。Kruskal算法则通过对图中所有边按权重排序，然后依次选择不形成环的最小权重边，直到生成树包含所有顶点。两者在应用中各有优势，Prim算法适用于稠密图，而Kruskal算法适用于稀疏图。