最小生成樹(shù)and最短路徑-全文預(yù)覽
【正文】 每執(zhí)行一次（3）都需要對(duì)著兩個(gè)數(shù)組進(jìn)行更新for (int ks = 0 。++i ){if( !used[i] amp。 ++kn ){lowcost[kn] = data[0][kn]。優(yōu)化（3）（3） 選擇A中所有的點(diǎn)中能到達(dá)B的最小權(quán)值邊，將這條邊的另一個(gè)點(diǎn)加入到A中并從B中剔除；如何尋找最小權(quán)值邊？如果直觀地去做，從A中各點(diǎn)遍歷，那么每加入一個(gè)點(diǎn)到A所費(fèi)的時(shí)間也是驚人的，所以也引入兩個(gè)數(shù)組來(lái)作優(yōu)化。對(duì)于這種簡(jiǎn)單的區(qū)分，大可不必抽象出對(duì)象出來(lái)。鄰接矩陣如果說(shuō)克魯斯卡爾算法使用自定義的邊集數(shù)組存儲(chǔ)圖是直觀的，那么普林算法采用自定義的點(diǎn)集數(shù)組也是合適的？如果以某一點(diǎn)作為單獨(dú)的數(shù)據(jù)結(jié)構(gòu)，那么這一數(shù)據(jù)結(jié)構(gòu)應(yīng)當(dāng)包含有與這個(gè)點(diǎn)有關(guān)的邊的所有信息——權(quán)值和對(duì)應(yīng)點(diǎn)。如此下去直到全部頂點(diǎn)都加入到集合中，即得最小生成樹(shù)。時(shí)間復(fù)雜度若e表示圖的邊數(shù)，那么，排序過(guò)程將有O(eloge)，生成過(guò)程則是O(e)，故總的來(lái)說(shuō)，時(shí)間復(fù)雜度為O(eloge)。}現(xiàn)在剩余最后的問(wèn)題——回路的避免。bool cmp(edge a , edge b){ int value 。由算法的核心思想上看，我們需要存儲(chǔ)的數(shù)據(jù)為邊，而邊的要素包括三點(diǎn)：連接的兩個(gè)結(jié)點(diǎn)、邊的權(quán)值。簡(jiǎn)單圖示：21 121 1 3 2 MST 2 54343 4 4 克魯斯卡爾（Kruskal）算法克魯斯卡爾算法從邊的角度來(lái)解決問(wèn)題，即在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構(gòu)成回路，則放棄，選取次小邊。由于之前學(xué)《離散數(shù)學(xué)》時(shí)只要求在思想上理解，并沒(méi)要求程序?qū)崿F(xiàn)，所以學(xué)起來(lái)也挺吃力的。這無(wú)疑是釋放了一個(gè)很大的信號(hào)——這些內(nèi)容很重要。即是在原圖上刪除邊，直到剩余n1條邊，保證n個(gè)結(jié)點(diǎn)連通且邊的權(quán)值加起來(lái)
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1