Python实现Kruskal 和Prim算法求解无向连通图的最小生成树问题

问题描述：

从边赋权图上选择一部分边得到一个子图，子图与原图具有共同的顶点，子图的边是原图的边的子集，且子图具有最小的开销（边的权值之和最小），符合这样要求的子图称作最小生成树，这类问题称作最小生成树问题。

求解最小生成树问题的主流算法有克鲁斯卡尔（Kruskal）算法和普利姆（Prim）算法。

克鲁斯卡尔算法的基本思想是：按权值从小到大的顺序把边增加到子图中直到子图变为连通图，如果某条边加入后会产生圈则不加入该边。

普利姆算法的基本思想是：从任意一个顶点开始逐个顶点进行判断并不断地扩张连通分支的规模，直到所有顶点都连通起来。这两种算法都属于贪心算法。

参考代码：

运行结果：