避圈法

英文名称：

kruskal

学科：

运筹学 图论 树

适应题型：

最小支撑树问题

主要思想：

开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选择一条权最小的。（每一步中，如果有两条或两条以上的边都是权值最小的边，则从中任选一条）。

算法的具体步骤：

第一步：令i=1，Ei=Φ.( Φ表示空集)

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

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

证明

略