克鲁斯卡尔算法的基本思想是以边为主导地位,始终选择当前可用(所选的边不能构成回路)的最小权植边。
1、给所有的边按照从小到大的顺序排序
2、从小到大依次考察每一条边(u,v)
<1>设一个有n个顶点的连通网络为G(V,E),最初先构造一个只有n个顶点,没有边的非连通图T={V,空},图中每个顶点自成一格连通分量。
<2>在E中选择一条具有最小权植的边时,若该边的两个顶点落在不同的连通分量上,则将此边加入到T中;否则,即这条边的两个顶点落到同一连通分量 上,则将此边舍去(此后永不选用这条边),重新选择一条权植最小的边。
<3>如此重复下去,直到所有顶点在同一连通分量上为止