离散数学 最小生成树 定义12.3设无向连通带权图G=<V,E,W,T是G的一棵生成 树，T的各边权之和称为T的权，记作WT.G的所有生成树 中权最小的生成树称为G的最小生成树： 避圈法（Kruskal) 输入：连通图G=<V,E,W> 输出：G的最小生成树T l.将G中非环边按权从小到大排列：W(e1)≤We2)..≤Wem) 2.令Tk-{e1},ik-2. 3.若e,与T中的边不构成回路，则令T←几U{e 4.若T<n-1,则令ik-i计1，转3. 1010 最小生成树 定义12.3 设无向连通带权图G=<V,E,W>，T是G的一棵生成 树，T的各边权之和称为T的权，记作W(T)．G的所有生成树 中权最小的生成树称为G的最小生成树. 避圈法（Kruskal） 输入: 连通图G=<V,E,W> 输出: G的最小生成树T 1. 将G中非环边按权从小到大排列: W(e1 )W(e2 ) …W(em). 2. 令T{e1 }, i2. 3. 若ei与T中的边不构成回路, 则令TT{ei }. 4. 若|T|<n-1, 则令ii+1, 转3