python最小生成树kruskal与prim算法详解

kruskal算法基本思路：先对边按权重从小到大排序，先选取权重最小的一条边，如果该边的两个节点均为不同的分量，则加入到最小生成树，否则计算下一条边，直到遍历完所有的边。 prim算法基本思路：所有节点分成两个group，一个为已经选取的selected_node（为list类型），一个为candidate_node，首先任取一个节点加入到selected_node，然后遍历头节点在selected_node，尾节点在candidate_node的边，选取符合这个条件的边里面权重最小的边，加入到最小生成树，选出的边的尾节点加入到selected_node，并从candidate_node删除。