算法導(dǎo)論--最小生成樹
最小生成樹：在連通網(wǎng)的所有生成樹中入挣，所有邊的代價和最小的生成樹，稱為最小生成樹硝拧。
1.Kruskal算法
此算法可以稱為“加邊法”径筏，初始最小生成樹邊數(shù)為0葛假，每迭代一次就選擇一條滿足條件的最小代價邊，加入到最小生成樹的邊集合里匠璧。
- 把圖中的所有邊按代價從小到大排序桐款；
- 把圖中的n個頂點(diǎn)看成獨(dú)立的n棵樹組成的森林；
- 按權(quán)值從小到大選擇邊夷恍，所選的邊連接的兩個頂點(diǎn)ui,viui,vi,應(yīng)屬于兩顆不同的樹魔眨，則成為最小生成樹的一條邊，并將這兩顆樹合并作為一顆樹酿雪。
-
重復(fù)(3),直到所有頂點(diǎn)都在一顆樹內(nèi)或者有n-1條邊為止遏暴。
image.png
Prim算法
此算法可以稱為“加點(diǎn)法”，每次迭代選擇代價最小的邊對應(yīng)的點(diǎn)指黎，加入到最小生成樹中朋凉。算法從某一個頂點(diǎn)s開始，逐漸長大覆蓋整個連通網(wǎng)的所有頂點(diǎn)醋安。
1.圖的所有頂點(diǎn)集合為VV杂彭；初始令集合u={s},v=V?uu={s},v=V?u;
2.在兩個集合u,vu,v能夠組成的邊中，選擇一條代價最小的邊(u0,v0)(u0,v0)吓揪，加入到最小生成樹中亲怠，并把v0v0并入到集合u中。
3.重復(fù)上述步驟柠辞，直到最小生成樹有n-1條邊或者n個頂點(diǎn)為止团秽。
哈夫曼樹
哈夫曼樹又稱最優(yōu)二叉樹。它是 n 個帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中叭首，帶權(quán)路徑長度 WPL 最小的二叉樹习勤。
假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點(diǎn)焙格。 n個權(quán)值分別設(shè)為 w1图毕、w2、…间螟、wn吴旋，則哈夫曼樹的構(gòu)造規(guī)則為：
(1) 將w1、w2厢破、…荣瑟，wn看成是有n 棵樹的森林(每棵樹僅有一個結(jié)點(diǎn))；
(2) 在森林中選出兩個根結(jié)點(diǎn)的權(quán)值最小的樹合并摩泪，作為一棵新樹的左笆焰、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左见坑、右子樹根結(jié)點(diǎn)權(quán)值之和嚷掠；
(3)從森林中刪除選取的兩棵樹捏检，并將新樹加入森林；
(4)重復(fù)(2)不皆、(3)步贯城，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹霹娄。
注意：為了使得到的哈夫曼樹的結(jié)構(gòu)盡量唯一能犯，通常規(guī)定生成的哈夫曼樹中每個結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)。
哈夫曼編碼
在電報通信中犬耻，電文是以二進(jìn)制的0踩晶、1序列傳送的，每個字符對應(yīng)一個二進(jìn)制編碼枕磁，為了縮短電文的總長度渡蜻，采用不等長編碼方式，構(gòu)造哈夫曼樹计济，
將每個字符的出現(xiàn)頻率作為字符結(jié)點(diǎn)的權(quán)值賦予葉子結(jié)點(diǎn)茸苇，每個分支結(jié)點(diǎn)的左右分支分別用0和1編碼，從樹根結(jié)點(diǎn)到每個葉子結(jié)點(diǎn)的路徑上
所經(jīng)分支的0沦寂、1編碼序列等于該葉子結(jié)點(diǎn)的二進(jìn)制編碼税弃。如上文所示的哈夫曼編碼如下：
最短路徑問題---Dijkstra算法
最短路徑問題介紹
問題解釋：
從圖中的某個頂點(diǎn)出發(fā)到達(dá)另外一個頂點(diǎn)的所經(jīng)過的邊的權(quán)重和最小的一條路徑，稱為最短路徑凑队。
初始狀態(tài)：S是已計算出最短路徑的頂點(diǎn)集合，U是未計算除最短路徑的頂點(diǎn)的集合幔翰！
第1步：將頂點(diǎn)D加入到S中漩氨。
此時，S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}遗增。 注:C(3)表示C到起點(diǎn)D的距離是3叫惊。
第2步：將頂點(diǎn)C加入到S中。
上一步操作之后做修，U中頂點(diǎn)C到起點(diǎn)D的距離最短霍狰；因此，將C加入到S中饰及，同時更新U中頂點(diǎn)的距離蔗坯。以頂點(diǎn)F為例，之前F到D的距離為∞燎含；但是將C加入到S之后宾濒，F(xiàn)到D的距離為9=(F,C)+(C,D)。
此時屏箍，S={D(0),C(3)}, U={A(∞),B(23),E(4),F(9),G(∞)}绘梦。
第3步：將頂點(diǎn)E加入到S中橘忱。
上一步操作之后，U中頂點(diǎn)E到起點(diǎn)D的距離最短卸奉；因此钝诚，將E加入到S中，同時更新U中頂點(diǎn)的距離榄棵。還是以頂點(diǎn)F為例凝颇，之前F到D的距離為9；但是將E加入到S之后秉继，F(xiàn)到D的距離為6=(F,E)+(E,D)祈噪。
此時，S={D(0),C(3),E(4)}, U={A(∞),B(23),F(6),G(12)}尚辑。
第4步：將頂點(diǎn)F加入到S中辑鲤。
此時，S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}杠茬。
第5步：將頂點(diǎn)G加入到S中月褥。
此時，S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}瓢喉。
第6步：將頂點(diǎn)B加入到S中宁赤。
此時，S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}栓票。
第7步：將頂點(diǎn)A加入到S中决左。
此時，S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}走贪。
此時佛猛，起點(diǎn)D到各個頂點(diǎn)的最短距離就計算出來了：A(22) B(13) C(3) D(0) E(4) F(6) G(12)。
