避圈法

避圈法英文名称：kruskal学科：运筹学 图论 树适应题型：最小支撑树问题主要思想：开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选择一条权最小的。（每一步中，如果有两条或两条以上的边都是权值最小的边，则从中任选一条）。算法的具体步骤：第一步：令i=1，Ei=Φ.( Φ表示空集)

第二步：选一条边ei ∈ EEi-1,使（V，Ei-1∪{e}）不含圈的所有边e（ei ∈ EEi-1）中权最小的边。令Ei=Ei-1∪{e}，如果这样的边不存在，则T=（V，Ei-1）是最小树。

第三步：把i换成i+1，转入第二步。证明略

[1]