sollin算法及證明
(2012-02-23 08:59:44) 1、算法概述 用于生成連通無向圖的最小代價生成樹。
2、算法步驟
步驟一：令圖中每個頂點表示一棵樹，原圖構成一個森林T；
步驟二：為T中每棵樹選擇一個最小代價邊，使得加入后仍是一棵樹，兩棵樹可以同一條邊；
步驟三：重復步驟二，直到T中只有一棵樹為止。
3、算法證明
要證明sollin算法得到的是一棵最小代價生成樹，我們分兩步來證明：
（1）sollin算法一定能得到一個生成樹；
（2）該生成樹具有最小代價。
證明如下：
（1）根據算法規則，每次新引入的邊都能保證森林中的樹仍是樹，既不會有環路出現。如果最后得到的不是一個生成樹，那就只有一種可能，即，得到的是多棵樹。但由于原圖是連通的，不可能出現存在兩棵或兩棵以上的樹相互不相連的情況。因此，該算法最后得到的必然是一顆樹。
（2）我們采用循環不變式來證明。循環不變式如下：
森林中的每棵樹都是最小代價生成樹。
初始化：每棵樹只有一個節點，所以是最小代價生成樹。
保持：每次添加新邊，其兩個端點必然位于兩棵樹中（否則形成環路），因此也就必然會將兩棵樹合并為一棵。假設合并的樹不是最小代價樹，就表示該樹還有其它一些代價更小的邊，通過加入一條邊，刪除一條邊的形式，可以得到一個更小代價的樹。首先，添加的邊兩個端點不可能同時能屬于被合并的兩棵樹中的一棵，那樣的話，就表示那棵樹不是最小代價樹，這與前提矛盾。因此，兩個端點只可能分別屬于兩棵樹。這個同樣也不可能發生，具體證明可以參考關于Prim的證明，畫一個環形證明。
本站僅提供存儲服務，所有內容均由用戶發布，如發現有害或侵權內容，請
點擊舉報。
