                        課程
                    
                        /后端開(kāi)發(fā)
                        
                            /C++
                        
                        /數(shù)據(jù)結(jié)構(gòu)探險(xiǎn)之圖篇

最小邊的點(diǎn)集合問(wèn)題

在算法第二步的找到最小邊連接的點(diǎn)，并找出點(diǎn)所在的點(diǎn)集合，對(duì)點(diǎn)做出相應(yīng)的處理，這樣的目的是什么

慕慕9573698

2020-02-10

源自：數(shù)據(jù)結(jié)構(gòu)探險(xiǎn)之圖篇 4-6

關(guān)注問(wèn)題我要回答

960

操作

收起

1 回答

董瘦瘦
2020-02-26

這是克魯斯卡爾算法的原理啊

在鄰接矩陣?yán)锶〕鏊羞吅笳页鲎钚∵?/p>
最小邊對(duì)應(yīng)的點(diǎn)不在集合中則添加進(jìn)去
一個(gè)在的話則把另一個(gè)添加到該點(diǎn)集合中
兩個(gè)都在同一個(gè)點(diǎn)集合中，只能拋棄這條邊，為什么呢？因?yàn)闀?huì)形成回環(huán)。例如：有一個(gè)點(diǎn)集合為{A,B,C}，要找的邊為AC，對(duì)應(yīng)兩個(gè)點(diǎn)都在，再選AC這條邊的話A-B,B-C,A-C就形成回環(huán)，所以在程序里continue跳過(guò)
兩個(gè)點(diǎn)在不同的點(diǎn)集合中，說(shuō)明這兩個(gè)點(diǎn)集合代表的邊可以通過(guò)當(dāng)前這條邊連接起來(lái)，對(duì)應(yīng)程序里的處理就是拼接兩個(gè)vector