Kruskal的最小生成树算法贪婪算法在C++中

生成树是连接所有顶点的有向无向图子图。图中可以存在许多生成树。每个图上的最小生成树(MST)的权重相同或小于所有其他生成树。权重被分配给生成树的边,总和是分配给每个边的权重。由于 V 是图中的顶点数,因此最小生成树的边数为 (V - 1),其中 V 是边数。

使用 Kruskal 算法查找最小生成树

Following are the edges in the constructed MST 22 -- 23 == 24 20 -- 23 == 25 20 -- 21 == 30 Minimum Cost Spanning tree : 79登录后复制