怎麼用普里姆演算法或克魯斯卡爾演算法求下面無向帶權圖的最小生成樹?

山雞村小貓2019-04-10 14:22:57

我說說克魯斯卡爾吧，普利姆就留給別人啦。

按照邊權從小到大排序，構建節點集一樣的空圖，然後逐個加回圖中去，跳過出現環路的邊，直到完全聯通。

邊權為2：加入BC EG

邊權為3：加入EH

邊權為4：加入AD CF

邊權為5：加入BD FG

這就已經是聯通圖了，所以以上加進去的邊就是原圖的最小生成樹。具體是怎麼追蹤連通性的，去看並查集。

這個例子沒有出現環路，沒有用到克魯斯卡爾演算法的查環分支。