求最小生成树有许多方法，这里介绍避圈法(KruskaIKruskaIKruskaI算法)
设图GGG有nnn个结点，以下算法产生最小生成树。
(1) 选择最小权边e1e_1e1，如果有多条这样的边，选序号最小的边，置边数i←1i\leftarrow1i←1;
(2) i=n−1i=n- 1i=n−1结束，否则转(3) ;
(3) 设定已选定e1,e2,...,eie_1,e_2,... ,e_ie1,e2,...,ei， 在GGG中选取不同于e1,e2，..,eie_1,e_2，.. ,e_ie1,e2，..,ei;的边ei+1e_{i+1}ei+1使e1,e2，..,ei;e_1,e_2，.. ,e_i;e1,e2，..,ei;无回路且ei+1e_{i+1}ei+1是满足此条件的最小边，如果有多条这样的边，选序号最小的边。
(4) i←i+1i←i+ 1i←i+1,转(2).
更多推荐
最小,方法,Kruskal
发布评论