問(wèn)題9 連通的代價(jià)

?圖的連通問(wèn)題是一個(gè)圖的基本問(wèn)題，如何用最小的代價(jià)把圖中所有節(jié)點(diǎn)連通起來(lái)，稱為最小生成樹(shù)問(wèn)題。最小生成樹(shù)問(wèn)題的應(yīng)用很廣。

?

本章在介紹問(wèn)題求解時(shí)，按照算法基本思想—算法描述—算法運(yùn)行示例—算法分析這4個(gè)步驟展開(kāi)介紹?！咀髡吒惺埽@個(gè)4個(gè)步驟是學(xué)習(xí)各種算法的標(biāo)準(zhǔn)步驟，對(duì)學(xué)習(xí)者各方面能力的訓(xùn)練都有幫助，還可以加上，代碼實(shí)現(xiàn)，就更完整】

?

本書詳細(xì)介紹的求解最小生成樹(shù)問(wèn)題的算法，不是一般數(shù)據(jù)結(jié)構(gòu)、算法書中常見(jiàn)的Kruskal算法、Prim算法、破圈法算法。而且沒(méi)有給出算法的出處。這里就不詳細(xì)介紹了，推薦自讀。

?

【作者感受】

求解最小生成樹(shù)問(wèn)題的有效算法值得學(xué)習(xí)，因?yàn)樽钚∩蓸?shù)問(wèn)題應(yīng)用很廣。

圖的生成樹(shù)和最小生成樹(shù)有很多（圖的）特色性質(zhì)，有興趣的讀者可以在圖論中學(xué)習(xí)。

針對(duì)圖的最小生成樹(shù)問(wèn)題，可以采用貪心算法設(shè)計(jì)策略，如何設(shè)計(jì)具體的貪心策略，就是不同的算法。不同的算法可能展現(xiàn)出不同的優(yōu)勢(shì)，更好地適應(yīng)不同的輸入數(shù)據(jù)（圖）；同時(shí)，學(xué)習(xí)不同的算法，分析不同算法的性能（效率和適用性），可以加深對(duì)最小生成樹(shù)問(wèn)題的理解，訓(xùn)練讀者的算法思維。

要實(shí)現(xiàn)最小生成樹(shù)算法的實(shí)際運(yùn)行時(shí)間，需要一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的支持（空間換時(shí)間）。

證明最小生成樹(shù)算法的正確性，需要用到圖論的一些知識(shí)，還會(huì)用到歸納法或反證法，需要一定的數(shù)學(xué)基礎(chǔ)。

?

學(xué)習(xí)本章，對(duì)算法邏輯、程序和數(shù)據(jù)結(jié)構(gòu)、數(shù)學(xué)知識(shí)都涉獵，有一點(diǎn)難度，但是難度還好。

所以，最小生成樹(shù)算法是數(shù)據(jù)結(jié)構(gòu)、算法教材中必有的內(nèi)容。