Prime算法O(NM)

贪心的思想

流程: 1.设定起始点,放入A集合,将起始点连接的边放入可选的边的集合中去。 2.循环n-1次, 1.找出可选的边集合中另一个端点在b集合中且边权最小的一条,将它加入最小生成树

堆优化O(n log m)

把边按边权放入小根堆,再pop

Kruskal

1.用变量记录下目前已经选择的边的数目 2.从大到小判断边是否可行,如果可行,就取出,直到取出n-1条边