避圈法的基本思想是先把邊按權由小到大排列起來，依次挑選權儘可能小的邊構造生成樹，即首先選取權最小邊，再從其餘邊中選取不能與已選邊構成圈的權最小的邊作為添加邊，依次類推，直到不存在合適的邊為止．全部挑選的邊與節點一起形成的圖就是最小樹。
基本介紹
- 中文名：避圈法
- 外文名：kruskal
- 學科：運籌學 圖論 樹
- 適應題型：最小支撐樹問題
基本思想,算法步驟,案例,
基本思想
避圈法的基本思想是先把邊按權由小到大排列起來，依次挑選權儘可能小的邊構造生成樹，即首先選取權最小邊，再從其餘邊中選取不能與已選邊構成圈的權最小的邊作為添加邊，依次類推，直到不存在合適的邊為止．全部挑選的邊與節點一起形成的圖就是最小樹。
算法步驟
避圈法算法步驟如下：
1、將連通網路G的邊按權由小到大排序，並加以編號，記為e1,e2,…,em；
2、若(V,E1)構成連通圖，則(V,E1)便是最小樹，否則轉下一步；
3、從E\E1中選取一邊ei，使得(V,E1)U{ei}不含圈，而且ei為符合該條件的權最小（序號最小）的邊，將所得到的E1U{ei}仍記為E1，轉第2步。
案例
某大學準備將所屬7個學院的計算機聯網，網路可能聯通的途徑如圖所示，邊旁的數字為相應線路的鋪設費用（單位：萬元），試設計一個能連通各學院並且總費用最少的網路。
圖1解：把線路的鋪設費用作為邊的權。圖就是一個網路，其最小樹既保證各學院信息暢通又能使總費用最少。
用避圈法求解的過程如下：在權為2的5條邊中，若選{v1,v6}和{v1,v2}，就不能選{v2,v6}，因為這三條邊構成圈，所以只能選取其中4條，其順序用帶圈的數字表示。同理，在權為3的3條邊中，若選了{v4,v6}，則{v2,v7}就不能要。最後選取{v2,v3}，共有6條邊入選，最小樹已經得到，如圖所示，最小總費用z*=2+2+2+2+3+3=14(萬元)。
圖2