這裏僅介紹最短路問題和最小生成樹問題，可用破圈法求解最小生成樹問題，破圈算法具體如下：
（1） 在給定的賦權的連通圖（若不是連通圖，則不存在生成樹）上任找一個圈；
（2） 在所找的圈中去掉一條權數最大的邊（如果有兩條或兩條以上的邊都是權數最大的邊，則任意去掉其中一條）；
（3） 如果所餘下的圖已不含圈，則算法結束，餘下的圖即為最小生成樹.否則返回步驟（1）.
下麵通過一個例子來說明破圈法求解最小生成樹問題的具體過程.
例9某大學準備對所屬的7個二級學院辦公室進行計算機聯網，這個網絡的可能連通的途徑如圖52圖G所示.圖中v1,…,v7表示7個二級學院的辦公室，圖中的邊為可能聯網的途徑，邊上的數值為這條路線所需的網線長度（單位：百米）.請設計一個網絡能連通這7個辦公室，並且使總的網線長度最短.
圖52
解：此問題實際上是求圖中G的最小生成樹.我們采用破圈法，具體求解過程如下：
（1） 在圖G中任找一個圈（v1,v6,v7,v1），此圈的邊[v1,v6]的權數16=10為最大，去掉邊[v1,v6]，得圖52中的圖G1；
（2） 在圖G1中任找一個圈（v3,v4,v5,v7,v3），此圈的邊[v4,v5]的權數45=8為最大，去掉邊[v4,v5]，得圖52中的圖G2；
（3） 在圖G2中任找一個圈（v2,v3,v5,v7,v2），此圈的邊[v5,v7]的權數57=5為最大，去掉邊[v5,v7]，得圖52中的圖G3；
（4） 在圖G3中任找一個圈（v3,v5,v6,v7,v3），此圈的邊[v3,v7],[v5,v6]的權數37=56=5為最大，去掉邊[v5,v6]（或去掉邊[v3,v7]），得圖52中的圖G4；
（5） 在圖G4中隻有一個圈（v2,v3,v7,v2），此圈的邊[v3,v7]的權數37=4為最大，去掉邊[v3,v7]，得圖52中的圖G5；
（6） 在圖G5中已無圈，破圈法結束.可知圖G5即為圖G的最小生成樹，總權數等於19.因此該大學可按圖52中的圖G5設計計算機網絡，且所需網線長度最短為19百米.