最小邊的點集合問題
在算法第二步的找到最小邊連接的點，并找出點所在的點集合，對點做出相應(yīng)的處理，這樣的目的是什么
慕慕9573698
2020-02-10
1 回答
舉報
0/150
提交
取消
2020-02-26
這是克魯斯卡爾算法的原理啊
在鄰接矩陣里取出所有邊后找出最小邊
最小邊對應(yīng)的點不在集合中則添加進去
一個在的話則把另一個添加到該點集合中
兩個都在同一個點集合中，只能拋棄這條邊，為什么呢？因為會形成回環(huán)。例如：有一個點集合為{A,B,C}，要找的邊為AC，對應(yīng)兩個點都在，再選AC這條邊的話A-B,B-C,A-C就形成回環(huán)，所以在程序里continue跳過
兩個點在不同的點集合中，說明這兩個點集合代表的邊可以通過當前這條邊連接起來，對應(yīng)程序里的處理就是拼接兩個vector