求最小生成树有许多方法,这里介绍避圈法(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
发布评论