我的第一本算法書

?圖例

?藍(lán)色：應(yīng)用

?紅色：重點(diǎn)

?紫色：時(shí)間復(fù)雜度

?

?綠色：代碼

?加粗：名詞解釋/重點(diǎn)

?序章算法的基本知識

?算法和程序有些相似，區(qū)別在于程序是以計(jì)算機(jī)能夠理解的編程語言編寫而成的，可以在計(jì)算機(jī)上

運(yùn)行；而算法是以人類能夠理解的方式描述的，用于編寫程序之前.

?運(yùn)行時(shí)間的計(jì)算方法

?一般來說我們最為重視的是算法的運(yùn)行時(shí)間，即從輸入數(shù)據(jù)到輸出結(jié)果這個(gè)過程所花費(fèi)的時(shí)間。

?使用"步數(shù)”來描述運(yùn)行時(shí)間。"1步"就是計(jì)算的基本單位。通過測試"計(jì)算從開始到結(jié)束

總共執(zhí)行了多少步"來求得算法的運(yùn)行時(shí)間。

?0這個(gè)符號的意思是"忽略重要項(xiàng)以外的內(nèi)容"，讀音同Order。

?選擇排序的時(shí)間復(fù)雜度為0（11人2）、快速排序的時(shí)間復(fù)雜度為O（nlogn）。

?第1章數(shù)據(jù)結(jié)構(gòu)

?1-1數(shù)據(jù)結(jié)構(gòu)

?決定了數(shù)據(jù)的順序和位置關(guān)系

?將數(shù)據(jù)存儲于內(nèi)存時(shí)，根據(jù)使用目的選擇合適的數(shù)據(jù)結(jié)構(gòu)，可以提高內(nèi)存的利用率。

?數(shù)據(jù)在內(nèi)存中是呈線性排列的，但是我們也可以使用指針等道具，構(gòu)造出類似"樹形"的復(fù)雜

結(jié)構(gòu)

?1-2鏈表（線性排列）

?在鏈表中，數(shù)據(jù)的添加和刪除都較為方便，就是訪問比較耗費(fèi)時(shí)間。

?在鏈表中，數(shù)據(jù)一般都是分散存儲于內(nèi)存中的，無須存儲在連續(xù)空間內(nèi)。

?因?yàn)閿?shù)據(jù)都是分散存儲的，所以如果想要訪問數(shù)據(jù)，只能從第1個(gè)數(shù)據(jù)開始，順著指針的指向

——往下訪問（順序訪問）。

?雖然刪除的數(shù)據(jù)本身還存儲在內(nèi)存中，但是不管從哪里都無法訪問這個(gè)數(shù)據(jù)，所以也就沒有特

意去刪除它的必要了。今后需要用到被刪數(shù)據(jù)所在的存儲空間時(shí)，只要用新數(shù)據(jù)覆蓋掉就可以

了。

?鏈表操作的時(shí)間復(fù)雜度

?杳找（線性查找）

0（n）

?添加/刪除數(shù)據(jù)

0（1）

?循環(huán)鏈表，也叫'‘環(huán)形鏈表"

?沒有頭和尾的概念

?想要保存數(shù)量固定的最新數(shù)據(jù)時(shí)通常會(huì)使用這種鏈表。

?雙向鏈表

?存在兩個(gè)缺點(diǎn)

?指針數(shù)的增加會(huì)導(dǎo)致存儲空間需求增加；

?添加和刪除數(shù)據(jù)時(shí)需要改變更多指針的指向.

?1-3數(shù)組（線性排列）

?在數(shù)組中，訪問數(shù)據(jù)十分簡單，而添加和刪除數(shù)據(jù)比較耗工夫。

?數(shù)據(jù)按順序存儲在內(nèi)存的連續(xù)空間內(nèi)。因此每個(gè)數(shù)據(jù)的內(nèi)存地址（在內(nèi)存上的位置）都可以通

過數(shù)組下標(biāo)算出，可以借此直接訪問目標(biāo)數(shù)據(jù)（隨機(jī)訪問）。

?數(shù)組操作的時(shí)間復(fù)雜度

?查找（線性查找）

。⑴

?添加/刪除數(shù)據(jù)

0（n）

?1-4棧Stack（線性排列）

?在棧中，添加和刪除數(shù)據(jù)的操作只能在一端進(jìn)行，訪問數(shù)據(jù)也只能訪問到頂端的數(shù)據(jù)。想要訪

問中間的數(shù)據(jù)時(shí)，就必須通過出棧操作將目標(biāo)數(shù)據(jù)移到棧頂才行。

?最后添加的數(shù)據(jù)最先被取出，即"后進(jìn)先出”的結(jié)構(gòu)，稱為LastInFirstOut,簡稱LIFOo

?棧只能訪問最新添加的數(shù)據(jù)。在只需要訪問最新數(shù)據(jù)時(shí)，使用它比較方便。

?括號配對

?深度優(yōu)先搜索算法，通常會(huì)選擇最新的數(shù)據(jù)作為候補(bǔ)頂點(diǎn)。在候補(bǔ)頂點(diǎn)的管理上可以使用

棧。

?1-5隊(duì)列Queue（線性排列）

?隊(duì)列中添加和刪除數(shù)據(jù)的操作分別是在兩端進(jìn)行的。

?隊(duì)列也不能直接訪問位于中間的數(shù)據(jù)，必須通過出隊(duì)操作將目標(biāo)數(shù)據(jù)變成首位后才能訪問。

?最先進(jìn)去的數(shù)據(jù)最先被取來，即"先進(jìn)先出"的結(jié)構(gòu)，我們稱為FirstlnFirstOut,簡稱FIFO。

?"先來的數(shù)據(jù)先處理"是一種很常見的思路，所以隊(duì)列的應(yīng)用范圍非常廣泛。

?廣度優(yōu)先搜索算法，通常就會(huì)從搜索候補(bǔ)中選擇最早的數(shù)據(jù)作為下一個(gè)頂點(diǎn)。在候補(bǔ)頂點(diǎn)

的管理上就可以使用隊(duì)列。

?1-6哈希表

?哈希表存儲的是由鍵（key）和值（value）組成的數(shù)據(jù)。

?在哈希表中，準(zhǔn)備好數(shù)組，可以利用哈希函數(shù)快速訪問到數(shù)組中的目標(biāo)數(shù)據(jù)。如果發(fā)生哈希沖

突，就使用鏈表進(jìn)行存儲。

?給數(shù)組設(shè)定合適的空間非常重要。

?如果數(shù)組的空間太小，容易發(fā)生沖突，線性查找的使用頻率也會(huì)更高；

?如果數(shù)組的空間太大，會(huì)出現(xiàn)很多空位，造成內(nèi)存的浪費(fèi)。

?幾種解決沖突的方法

?鏈地址法

在存儲數(shù)據(jù)的過程中，如果發(fā)生沖突，可以利用鏈表在已有數(shù)據(jù)的后面插入新數(shù)據(jù)來解決

沖突。

?開放地址法

當(dāng)沖突發(fā)生時(shí)，立刻計(jì)算出一個(gè)候補(bǔ)地址（數(shù)組上的位置）并將數(shù)據(jù)存進(jìn)去。如果仍然有

沖突，便繼續(xù)計(jì)算下一個(gè)候補(bǔ)地址，直到有空地址為止。

?計(jì)算候補(bǔ)地址

?多次使用哈希函數(shù)

?線性探測法

?在把哈希表應(yīng)用于密碼等安全方面時(shí)需要留意的條件：無法根據(jù)哈希值推算出原值

?哈希表在數(shù)據(jù)存儲上的靈活性和數(shù)據(jù)查詢上的高效性

?關(guān)聯(lián)數(shù)組

一種具有特殊索引方式的數(shù)組。不僅可以通過整數(shù)來索引它，還可以使用字符串或者其他

類型的值（除了NULL）來索引它。它包含標(biāo)量數(shù)據(jù)，可用索引值來單獨(dú)選擇這些數(shù)據(jù)，

和數(shù)組不同的是，關(guān)聯(lián)數(shù)組的索引值不是非負(fù)的整數(shù)而是任意的標(biāo)量。這些標(biāo)量稱為Keys,

可以在以后用于檢索數(shù)組中的數(shù)值。關(guān)聯(lián)數(shù)組的元素沒有特定的順序，可以把它們想象為

一組卡片。每張卡片上半部分是索引而下半部分是數(shù)值。

?1-7堆（圖的樹形結(jié)構(gòu)）

?堆是一種圖的樹形結(jié)構(gòu)，被用于實(shí)現(xiàn)“優(yōu)先隊(duì)列"（priorityqueues）

?優(yōu)先隊(duì)列是一種數(shù)據(jù)結(jié)構(gòu)，可以自由添加數(shù)據(jù)，但取出數(shù)據(jù)時(shí)要從最小值開始按III頁序取出。

?和隊(duì)列的不同，隊(duì)列是先進(jìn)先出；堆雖然也是最頂部的先出，但是由于它插入數(shù)據(jù)的時(shí)候

有排序過，所以是最小的先出。

?堆中的每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)。樹的形狀取決于數(shù)據(jù)的個(gè)數(shù)。

?結(jié)點(diǎn)的排列順序?yàn)閺纳系较?，同一行里則為從左到右。@opalli:填滿一行再填下一行

?在堆中存儲數(shù)據(jù)時(shí)必須遵守這樣一條規(guī)則：子結(jié)點(diǎn)必定大于父結(jié)點(diǎn)。@opalli:只在縱向有大

小順序，橫向節(jié)點(diǎn)間沒有大小關(guān)系。

?最小值被存儲在頂端的根結(jié)點(diǎn)中。

?往堆中添加數(shù)據(jù)時(shí)，

?T殳會(huì)把新數(shù)據(jù)放在最下面一行靠左的位置。當(dāng)最下面一行里沒有多余空間時(shí)，就再往

下另起一行，把數(shù)據(jù)加在這一行的最左端。

?如果父結(jié)點(diǎn)大于子結(jié)點(diǎn)，交換父子結(jié)點(diǎn)的位置。

?從堆中取出數(shù)據(jù)時(shí)，

?取出的是最上面的數(shù)據(jù)。這樣就能始終保持最上面的數(shù)據(jù)最小。

?最上面的數(shù)據(jù)被取出，堆的結(jié)構(gòu)也需要重新調(diào)整。

?將最后的數(shù)據(jù)移動(dòng)到最頂端。@opalli:為了保持堆是平衡的，塞滿一行再塞下一

行的屬性。同時(shí)注意最后的數(shù)據(jù)是最后一行最右邊的數(shù)據(jù)，而不是（倒數(shù)第二行）

最右邊的數(shù)據(jù)！如果用數(shù)組來存儲堆，那就是最后一個(gè)數(shù)據(jù)。

?如果子結(jié)點(diǎn)的數(shù)字小于父結(jié)點(diǎn)的，就將父結(jié)點(diǎn)與其左右兩個(gè)子結(jié)點(diǎn)中較小的一個(gè)進(jìn)

行交換。@opalli:和較小的那個(gè)交換，和較大的交換，則換上去的那個(gè)是比另一

個(gè)大的！

?堆操作的時(shí)間復(fù)雜度

?取出最小值

。⑴

?重構(gòu)樹（刪除）（樹的高度為Iog2n）

O（logn）

?添加數(shù)據(jù)（與樹的高度成正比）

O（logn）

?如果需要頻繁地從管理的數(shù)據(jù)中取出最小值，那么使用堆來操作會(huì)非常方便。

?狄克斯特拉算法，每一步都需要從候補(bǔ)頂點(diǎn)中選擇距離起點(diǎn)最近的那個(gè)頂點(diǎn)。在頂點(diǎn)的選

擇上就可以用堆。

?1-8二叉查找樹/二叉搜索樹/二叉排序樹(圖的樹形結(jié)構(gòu))

?二叉查找樹的兩個(gè)性質(zhì)@opalli:縱橫方向皆有大小關(guān)系

二叉查找樹的最小結(jié)點(diǎn)要從頂端開始，往其左下的末端尋找；二叉查找樹的最大結(jié)點(diǎn)要從頂端

開始，往其右下的末端尋找。

?每個(gè)結(jié)點(diǎn)的值均大于其左子樹上任意一個(gè)結(jié)點(diǎn)的值。

?每個(gè)結(jié)點(diǎn)的值均小于其右子樹上任意一個(gè)結(jié)點(diǎn)的值。

?往二叉杳找樹中刪除數(shù)據(jù)

?如果需要?jiǎng)h除的結(jié)點(diǎn)沒有子結(jié)點(diǎn)，直接刪掉該結(jié)點(diǎn)即可。

?如果需要?jiǎng)h除的結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)，那么先刪掉目標(biāo)結(jié)點(diǎn)，然后把子結(jié)點(diǎn)移到被刪除結(jié)

點(diǎn)的位置上即可。

?如果需要?jiǎng)h除的結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，那么先刪掉目標(biāo)結(jié)點(diǎn)，然后在被刪除結(jié)點(diǎn)的左子樹中

尋找最大結(jié)點(diǎn)，最后將最大結(jié)點(diǎn)移到被刪除結(jié)點(diǎn)的位置上。如果需要移動(dòng)的結(jié)點(diǎn)也還有子

結(jié)點(diǎn)，就遞歸執(zhí)行前面的操作。@opalli:需要移動(dòng)的節(jié)點(diǎn)是左子樹中最大的結(jié)點(diǎn)，所以它

只可能有左子樹，將它移上去以后，直接用左子樹的結(jié)點(diǎn)來填充即可。

?刪除的時(shí)候，將"左子樹中的最大結(jié)點(diǎn)"移動(dòng)到了刪除結(jié)點(diǎn)的位置上，但是根據(jù)二叉查找

樹的性質(zhì)可知，移動(dòng)"右子樹中的最小結(jié)點(diǎn)”也沒有問題。

?二叉查找樹是二分查找算法思想的樹形結(jié)構(gòu)體現(xiàn)

?二叉查找樹操作的時(shí)間復(fù)雜度

?查找數(shù)據(jù)/尋找適合添加數(shù)據(jù)的位置(取決于樹的高度)

?樹的形狀較為均衡

O(logn)

?樹的形狀朝單側(cè)縱向延伸

0(n)

?@opalli:這里和堆也不一樣，因?yàn)槎训臄?shù)據(jù)是塞滿一行才會(huì)塞下面一行，所以時(shí)間復(fù)

雜度是O(logn),而不會(huì)有不平衡達(dá)到0(n)的情況。

?平衡二叉查找樹AVLTree

?平衡二叉樹(AVL樹)在符合二叉查找樹的條件下，還滿足任何節(jié)點(diǎn)的兩個(gè)子樹的高度最

大差為lo

?a,b是AVL樹，c,d不是

，no■>?IIBF3nwiv6aw

TN?t?avalidAVLtrMsnceforwchnod*mthe

treetheh*ghtofth?andnjhtsubtreesdffm

tr??mheightoftrwleftsndrightsubtrew

t>ya<most1(NoticethatforeachNULL60d.Vw

WmoM1.

height<rfthatcfiWssutxr??is-1.)

?1.1.1.1TT&?

?1.1>1?1

(a)(b)

ThrttreeeNOTavakdAVttreesincemeheightTh?tree?NOTavahdAVLVMuncatheh*9M

ofMnodm?ub(reMdonotd<rr?fbyatmost1ofaKnodessubtreesdonddifferbyalnx?t1.

Speo?C8?y.therootsleftindrtgNsubtfees'Bothnode20andnode5violMethisproperty

heightsdifferby2.

//

■<

?O

?1.1?1?1

（d）

?失去平衡的二叉樹可以概括為四種姿態(tài)：LL（左左）、RR（右右）、LR（左右）、RL（右

左）.

Lx^s^入（

-士

IM-，UW-IB4T

?AVL樹通過"旋轉(zhuǎn)操作（rotations）來保持樹的平衡。這種數(shù)據(jù)結(jié)構(gòu)可以修正形狀不均衡

的樹，讓其始終保持均衡形態(tài)，1?煩高查找效率。

?LL的旋轉(zhuǎn)：LL失去平衡的情況下可以通過一次旋轉(zhuǎn)讓AVL樹恢復(fù)平衡。步驟如下：

——插入6r—-1右單旋轉(zhuǎn)__

10匕_[_2

1

□

?將根節(jié)點(diǎn)的左孩子作為新根節(jié)點(diǎn)。

?將新根節(jié)點(diǎn)的右孩不乍為原根節(jié)點(diǎn)的左孩子。

?將原根節(jié)點(diǎn)作為新根節(jié)點(diǎn)的右孩子。

?RR的旋轉(zhuǎn)：RR失去平衡的情況下，旋轉(zhuǎn)方法與LL旋轉(zhuǎn)對稱，步驟如下：

?將根節(jié)點(diǎn)的右孩布乍為新根節(jié)點(diǎn)。

?將新根節(jié)點(diǎn)的左孩子作為原根節(jié)點(diǎn)的右孩子。

?將原根節(jié)點(diǎn)作為新根節(jié)點(diǎn)的左孩子。

?LR的旋轉(zhuǎn)：LR失去平衡的情況下，需要進(jìn)行兩次旋轉(zhuǎn)，步驟如下：

?圍繞根節(jié)點(diǎn)的左孩子進(jìn)行RR旋轉(zhuǎn)。

?圍繞根節(jié)點(diǎn)進(jìn)行LL旋轉(zhuǎn)。

?RL的旋轉(zhuǎn)：RL失去平衡的情況下也需要進(jìn)行兩次旋轉(zhuǎn)，旋轉(zhuǎn)方法與LR旋轉(zhuǎn)對稱，步

驟如下：

?圍繞根節(jié)點(diǎn)的右孩子進(jìn)行LL旋轉(zhuǎn)。

?圍繞根節(jié)點(diǎn)進(jìn)行RR旋轉(zhuǎn)。

?B樹

?把二叉查找樹的子結(jié)點(diǎn)數(shù)擴(kuò)展為m（m為預(yù)先設(shè)定好的常數(shù)）。像這種子結(jié)點(diǎn)數(shù)可以自由

設(shè)定，并且形狀均衡的樹便是B樹。

?其他自平衡BST:紅黑樹(Red-BlackTree)、2-3樹、2-3-4樹、伸展樹(SplayTree)、

B樹

?第2章排序

?2-1什么是排序

排序算法平均時(shí)間復(fù)勘發(fā)最好情K最壞情況.空間要?dú)l(fā)排序方式.穩(wěn)定＜1

胃泡排序。(向O(n)0(向0(1)In-place穩(wěn)定

選掙排序0(向0M2)o(e0(1)In-place不穩(wěn)定

插入排序O2)0(n)。(向0(1)In-place穩(wěn)定

韋爾排壽O(nlogn)0(nlog2n)O(nlog2n)0(1)In-place不穩(wěn)定

歸并排壽0(nlogn)0(nlogn)O(nlogn)O(n)Out-place穩(wěn)定

快速排方0(nlogn)0(nlogn)。(向O(logn)In-place不賽定

培排序0(nlogn)O(nlogn)O(nlogn)0(1)In-place不栽定

計(jì)數(shù)排壽0(n+k)0(n+k)0(n+k)O(h)Out-place穩(wěn)定

精加聲O(n+k)0(n+k)0(n2)O(n+k)Out-place想定

皋敕排方0(nxk)0(nxk)0(nxk)0(n+k)Out—place穩(wěn)定

?2-2冒泡排序

?從序列右邊開始比較相鄰兩個(gè)數(shù)字的大小，再根據(jù)結(jié)果交換兩個(gè)數(shù)字的位置，重復(fù)同樣的操作

直到序列中最小的數(shù)字移動(dòng)到最左邊。然后重復(fù)之前的操作，將第二小的數(shù)字移動(dòng)到左二……繼

續(xù)重復(fù)知道所有數(shù)字都排完序。

.冒泡排序的時(shí)間復(fù)雜度

0(nA2)

?比較

0(nA2)(和數(shù)據(jù)排列順序無關(guān)，恒定。)

?交換

(和輸入數(shù)據(jù)的排列順序有關(guān)。)如輸入數(shù)據(jù)正好以從小到大的順序排列，便不需要任何

交換操作；輸入數(shù)據(jù)以從大到小的II質(zhì)序排列，每次比較都要交換。

?2-3選擇排序

?從待排序的數(shù)據(jù)中尋找最小值，將其與序列最左邊的數(shù)字進(jìn)行交換。重復(fù)同樣的操作直到所有

數(shù)字都?xì)w位為止。

?冒泡排序的時(shí)間復(fù)雜度

0(nA2)

?比較

0(nA2)

?交換

每輪中交換數(shù)字的次數(shù)最多為1次。

?2-4插入排序

?插入排序是一種從序列左端開始依次對數(shù)據(jù)進(jìn)行排序的算法。在排序過程中，左側(cè)的數(shù)據(jù)陸續(xù)

歸位，而右側(cè)留下的就是還未被排序的數(shù)據(jù)。插入排序的思路就是從右側(cè)的未排序區(qū)域內(nèi)取出

一個(gè)數(shù)據(jù),然后將它插入到已排序區(qū)域內(nèi)合適的位置上。

?插入排序的時(shí)間復(fù)雜度

0(nA2)

?輸入數(shù)據(jù)按從大到小的順序排列時(shí)就是最糟糕的情況。

?2-5堆排序

?堆排序的特點(diǎn)是利用了數(shù)據(jù)結(jié)構(gòu)中的堆。首先，在堆中存儲所有的數(shù)據(jù)，并按降序來構(gòu)建堆。

從降序排列的堆中取出數(shù)據(jù)時(shí)會(huì)從最大的數(shù)據(jù)開始取，所以將取出的數(shù)據(jù)反序輸出，排序就完

成了。

?@opalli:既然要反序輸出，為神馬不T始就用升序堆呢？

?堆排序的時(shí)間復(fù)雜度

O(nlogn)

?將數(shù)據(jù)存進(jìn)堆里

O(nlogn)(插入1個(gè)數(shù)據(jù)所需要的時(shí)間為O(logn)。)

?重構(gòu)排序整體來看堆排序的時(shí)間復(fù)雜度為

O(nlogn)(每輪取出最大的數(shù)據(jù)并重構(gòu)堆所需時(shí)間為O(logn)o)

?堆排序的運(yùn)行時(shí)間比冒泡排序、選擇排序、插入排序的時(shí)間0(n^2)都要短，但由于要使

用堆這個(gè)相對復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，所以實(shí)現(xiàn)起來也較為困難。

?T殳來說，需要排序的數(shù)據(jù)都存儲在數(shù)組中。實(shí)際上，這也相當(dāng)于將堆嵌入到包含了序

列的數(shù)組中，然后在數(shù)組中通過交換數(shù)據(jù)來進(jìn)行排序?？梢哉f是強(qiáng)行在數(shù)組中使用了堆

結(jié)構(gòu)。

?@opalli:數(shù)據(jù)結(jié)構(gòu)，歸根到底只有兩種，鏈表和數(shù)組，其余的結(jié)構(gòu)都是基于這兩種最

基本的來構(gòu)建和存儲的.

?樹

?用數(shù)組實(shí)現(xiàn)就是「堆」，因?yàn)椤付选故且粋€(gè)完全二叉樹，用數(shù)組存儲不需要節(jié)點(diǎn)指

針，操作也比較簡單；

?假如A、B.C…節(jié)點(diǎn)對應(yīng)數(shù)組的索引位置0、1、2,那么如果一個(gè)節(jié)點(diǎn)的索引

位置如果是i,那么它的左子節(jié)點(diǎn)的索引位置為2*i+l,右子節(jié)點(diǎn)的索引位置

為2*i+2,父節(jié)點(diǎn)的索弓I位置為ceil[(i-1)/2],ceil表示向下取整。

@opalli:只有堆可以這樣計(jì)算，因?yàn)槎训臄?shù)據(jù)是插滿的。

?用鏈表實(shí)現(xiàn)就是很常見的那種「樹」，因?yàn)椴灰欢ㄊ峭耆鏄?，所以不適合用數(shù)

組存儲。

?在這種鏈表「樹」結(jié)構(gòu)之上，又衍生出各種巧妙的設(shè)計(jì)，比如二叉搜索樹、

AVL樹、紅黑樹、區(qū)間樹、B樹等等，以應(yīng)對不同的問題。

?在一棵樹中，邊的數(shù)量比節(jié)點(diǎn)的數(shù)量少1.如果一棵樹有N個(gè)節(jié)點(diǎn)，則這棵樹有

N-1條邊。LeetCode【684】冗余連接題中的圖在樹的基礎(chǔ)上多了一條附加的邊,

因此邊的數(shù)量也是N。樹是一個(gè)連通且無環(huán)的無向圖，在樹中多了一條附加的邊之

后就會(huì)出現(xiàn)環(huán)。

?2-6歸并排序

?歸并排序算法會(huì)把序列分成長度相同的兩個(gè)子序列，當(dāng)無法繼續(xù)往下分時(shí)(也就是每個(gè)子序列

中只有一個(gè)數(shù)據(jù)時(shí))，就對子序列進(jìn)行歸并。歸并指的是把兩個(gè)排好序的子序列合并成一個(gè)有

序序列。

.歸并排序的時(shí)間復(fù)雜度

O(nlogn)

?分割

不算在運(yùn)行時(shí)間內(nèi)（可以當(dāng)作序列本來就是分割好的）。

?歸并

O（nlogn）（每行花費(fèi)和兩個(gè)子序列的長度相應(yīng)的運(yùn)行時(shí)間，有Iog2n行。）

?2-7快速排序

?快速排序算法首先會(huì)在序列中隨機(jī)選擇一個(gè)基準(zhǔn)值（pivot）,然后將除了基準(zhǔn)值以外的數(shù)分為

"比基準(zhǔn)值小的數(shù)"和"比基準(zhǔn)值大的數(shù)"這兩個(gè)類別，再將其排列成以下形式。

?[比基準(zhǔn)值小的數(shù)]基準(zhǔn)值[比基準(zhǔn)值大的數(shù)]

?接著，對兩個(gè)"[]"中的數(shù)據(jù)進(jìn)行排序之后，整體的排序便完成了。對"[]"里面的數(shù)據(jù)進(jìn)行

排序時(shí)同樣也會(huì)使用快速排序，直到子問題里只剩一個(gè)數(shù)字為止。

?快速排序是一種“分治法"。它將原本的問題分成兩個(gè)子問題（比基準(zhǔn)值小的數(shù)和比基準(zhǔn)值大

的數(shù)），然后再分別解決這兩個(gè)問題。

?分治和遞歸是不是總是結(jié)伴出現(xiàn)呢？

?漢諾塔

?快速排序的時(shí)間復(fù)雜度

?如果每次選擇的基準(zhǔn)值都能使得兩個(gè)子序列的長度為原本的一半

O（nlogn）

?如果每次都選擇最小值作為基準(zhǔn)值

0（nA2）

?如果數(shù)據(jù)中的每個(gè)數(shù)字被選為基準(zhǔn)值的概率都相等，則平均運(yùn)行時(shí)間

O（nlogn）

?實(shí)現(xiàn)參考

hups:〃www.sohu.eom/a/246785807684445

?同冒泡排序一樣，快速排序也屬于交換排序，通過元素之間的比較和交換位置來達(dá)到排序

的目的。

?比冒泡排序快的地方：冒泡的輪數(shù)會(huì)比較多。冒泡排序在每一輪只把一個(gè)元素冒泡到數(shù)列

的一端，而快速排序在每一輪挑選一個(gè)基準(zhǔn)元素，并讓其他比它大的元素移動(dòng)到數(shù)列一邊，

比它小的元素移動(dòng)到數(shù)列的另一邊，從而把數(shù)列拆解成了兩個(gè)部分。

?@算法圖解：

?在大0表示法0（。）中,“實(shí)際上指的是這樣的。

c次h

國定的

時(shí)間量

?C是算法所需的固定時(shí)間量，被稱為常量。

?通常不考慮這個(gè)常量，因?yàn)槿绻麅煞N算法的大0運(yùn)行時(shí)間不同，這種常量將無關(guān)緊要。

?但當(dāng)使用大O表示法表示時(shí)兩個(gè)算法的速度相同，常量的影響可能很大，實(shí)際上會(huì)有速度

的區(qū)別。這就是快速排序比合用E序快的原因所在.@opalli:為撒固定時(shí)間量不一樣？快

排交換次數(shù)少？

?平均情況下(隨機(jī)地選擇一個(gè)數(shù)組元素作為基準(zhǔn)值)快速排序比合并排序快。

?快速排序在最糟情況下,棧長為0(/7),算法的運(yùn)行時(shí)間為0(〃八2);而在最佳情況下，

棧長為O(log/7),整個(gè)算法需要的時(shí)間為0(/7logn)0

?合并排序的運(yùn)行時(shí)間總是O(〃log〃)。

?第3章數(shù)組的查找

.3-1線性查找

?線性查找的時(shí)間復(fù)雜度

0(n)

?3-2二分查找

?二分查找通過比較數(shù)組中間的數(shù)據(jù)與目標(biāo)數(shù)據(jù)的大小，可以得知目標(biāo)數(shù)據(jù)是在數(shù)組的左邊還是

右邊.因此，比較一次就可以把查找范圍縮小一半。重復(fù)執(zhí)行該操作就可以找到目標(biāo)數(shù)據(jù)，或

得出目標(biāo)數(shù)據(jù)不存在的結(jié)論。

?二分查找只能查找已經(jīng)排好序的數(shù)據(jù)。

?二分查找的時(shí)間復(fù)雜度

O(logn)

?二分查找必須建立在數(shù)據(jù)已經(jīng)排好序的基礎(chǔ)上才能使用，因此添加數(shù)據(jù)時(shí)必須加到合適的

位置，這就需要額外耗費(fèi)維護(hù)數(shù)組的時(shí)間。

?第4章圖的搜索

?4-1什么是圖

?計(jì)算機(jī)科學(xué)或離散數(shù)學(xué)中說的"圖"

?頂點(diǎn)/結(jié)點(diǎn)

?邊

?圖

由頂點(diǎn)和連接每對頂點(diǎn)的邊所構(gòu)成的圖形

?圖可以表現(xiàn)各種關(guān)系

?社會(huì)中的各種關(guān)系

?地鐵的路線

?網(wǎng)絡(luò)的連接關(guān)系

?加權(quán)圖

?可以給邊加上一個(gè)值，這個(gè)值叫作邊的"權(quán)重"或者"權(quán)"，加了權(quán)的圖被稱為"加權(quán)

圖"。

?沒有權(quán)的邊只能表示兩個(gè)頂點(diǎn)的連接狀態(tài)，而有權(quán)的邊就可以表示頂點(diǎn)之間的“連接程

度"。

?計(jì)算最短路徑時(shí)，邊的權(quán)重代表的通常都是時(shí)間、距離或者路費(fèi)等，因此基本都是非負(fù)數(shù)。

?在一些情況下頂點(diǎn)也可以有權(quán)重。

?有向圖

?給邊加上箭頭，而這樣的圖就叫作"有向圖"。

?邊上沒有箭頭的圖便是“無向圖"。

?使用有向圖還可以設(shè)置非對稱的權(quán)重。

?無向圖意味著兩個(gè)節(jié)點(diǎn)彼此指向?qū)Ψ剑鋵?shí)就是環(huán)！在無向圖中，每條邊都是一個(gè)環(huán)。

?圖的基本問題——最短路徑問題

?最短路徑問題就是在加權(quán)圖指定了起點(diǎn)和終點(diǎn)的前提下，尋找從起點(diǎn)到終點(diǎn)的路徑中權(quán)重

總和最小的那條路徑。

?解決辦法：圖的最短路徑問題算法（4-4、4-5、4-6）

?算法的應(yīng)用場景

?尋找計(jì)算機(jī)網(wǎng)絡(luò)中通信時(shí)間最短的路徑

?尋找路線圖中耗時(shí)最短的路徑

?尋找路線圖中最省乘車費(fèi)的路徑

?圖的搜索（4-2、4-3）

?圖的搜索指的就是從圖的某一頂點(diǎn)開始，通過邊到達(dá)不同的頂點(diǎn)，最終找到目標(biāo)頂點(diǎn)的過

程。

?根據(jù)搜索的順序不同，圖的搜索算法可分為

?廣度優(yōu)先搜索

?深度優(yōu)先搜索

?@opalli:但是圖的搜索算法和最短路徑問題算法并不完全一樣，圖的搜索有T目標(biāo),

但目標(biāo)不一直是最短路徑？

?BFS相對DFS的最主要的區(qū)別是：BFS找到的路徑一定是最短的，但代價(jià)就是空間復(fù)

雜度比DFS大很多。

?BFS借助隊(duì)列做到一次一步“齊頭并進(jìn)"，即BFS的depth每增加一次，隊(duì)列中

的所有節(jié)點(diǎn)都向前邁一步，保證了第一次到達(dá)終點(diǎn)的時(shí)候，走的步數(shù)是最少的，可

以在不遍歷完整棵樹的條件下找到最短距離的。

?DFS其實(shí)也可以找最短路徑，但是時(shí)間復(fù)雜度相對高很多。DFS實(shí)際上是靠遞歸的

堆棧記錄走過的路徑，要找到最短路徑，得把二叉樹中所有樹杈都探索完才能對比

出最短的路徑有多長。

?形象點(diǎn)說，DFS是線，BFS是面；DFS是單打獨(dú)斗，BFS是集體行動(dòng)。

?BFS可以找到最短距離，但空間復(fù)雜度高；而DFS的空間復(fù)雜度較低。節(jié)點(diǎn)數(shù)為

N的滿二叉樹

:空間復(fù)雜度就是遞歸堆棧，最壞情況下是樹的高度，也就是（）

?DFSOlogNo

?BFS:隊(duì)列中每次都會(huì)儲存著二叉樹一層的節(jié)點(diǎn)，最壞情況下空間復(fù)雜度是樹

的最底層節(jié)點(diǎn)的數(shù)量，也就是N/2，用Big。表示的話也就是0（N）。

?BFS還是有代價(jià)的，一般來說在找最短路徑的時(shí)候使用BFS,其他時(shí)候還是DFS

使用得多一些（遞歸代碼好寫）。

?圖的搜索的應(yīng)用

?遍歷（DFS）

?找出（非加權(quán)圖的）最短路徑（BFS）

?4-2廣度優(yōu)先搜索BFS

?廣度優(yōu)先搜索會(huì)優(yōu)先從離起點(diǎn)近的頂點(diǎn)開始搜索。因此，目標(biāo)頂點(diǎn)離起點(diǎn)越近，搜索結(jié)束得就

越快。

?@opalli:所以廣度優(yōu)先搜索可以用來尋找（非加權(quán)圖的）最短路徑

?候補(bǔ)頂點(diǎn)是用"先入先出"（FIFO）的方式來管理的，因此可以使用"隊(duì)列"這個(gè)數(shù)據(jù)結(jié)構(gòu).

?@opalli:同一層（深度）的頂點(diǎn)，或者說距離起點(diǎn)相同遠(yuǎn)近的頂點(diǎn)，是同時(shí)成為候補(bǔ)頂點(diǎn)的。

?@opalli:搜索某個(gè)頂點(diǎn)，就是判斷其是不是目標(biāo)節(jié)點(diǎn)，不是的話，將其子結(jié)點(diǎn)添加到候補(bǔ)頂

點(diǎn)隊(duì)列中。

?如果圖中有閉環(huán)，其搜索步驟也是一樣的。@opalli:不限于樹狀圖，只要起點(diǎn)確定了，就可

以有遠(yuǎn)近的區(qū)分。

?沒有閉環(huán)的圖叫作"樹"。

?@算法圖解：廣度優(yōu)先搜索的運(yùn)行時(shí)間為O(V+E),其中V為頂點(diǎn)(vertice)數(shù)，E為邊數(shù)。

?4-3深度優(yōu)先搜索DFS

?深度優(yōu)先搜索會(huì)沿著一條路徑不斷往下搜索直到不能再繼續(xù)為止，然后再折返，開始搜索下一

條候補(bǔ)路徑。@opalli:廣度優(yōu)先搜索沒有折返。

?候補(bǔ)頂點(diǎn)是用"后入先出"(LIFO)的方式來管理的，因此可以使用"棧"這個(gè)數(shù)據(jù)結(jié)構(gòu)。

?雖然廣度優(yōu)先搜索和深度優(yōu)先搜索在搜索順序上有很大的差異，但是在操作步驟上卻只有一點(diǎn)

不同，那就是選擇哪一個(gè)候補(bǔ)頂點(diǎn)作為下一個(gè)頂點(diǎn)的基準(zhǔn)不同。

?廣度優(yōu)先搜索選擇的是最早成為候補(bǔ)的頂點(diǎn)，因?yàn)轫旤c(diǎn)離起點(diǎn)越近就越早成為候補(bǔ)，所以

會(huì)從離起點(diǎn)近的地方開始按順序搜索；@opalli:近即深度小。

?而深度優(yōu)先搜索選擇的則是最新成為候補(bǔ)的頂點(diǎn)，所以會(huì)一路往下，沿著新發(fā)現(xiàn)的路徑不

斷深入搜索。

?@opalli:進(jìn)行過”是否目標(biāo)判斷，且子節(jié)點(diǎn)加入了候選”的節(jié)點(diǎn)(對應(yīng)在算法中，就是pop

過的node),被認(rèn)為是搜索過的節(jié)點(diǎn),不會(huì)再入隊(duì)/棧。

?@opalli:BFS&DFS總結(jié)

?廣度優(yōu)先搜索BFS

1/??

2*Returnthelengthoftheshortestpathbetweenrootandtargetnode.

3*/

4intBFS(Noderoot,Nodetarget){

Queue<Node>queue;//storeallnodeswhicharewaitingtobeprocessed

Set<Node>used;//storealltheusednodes

intstep=0;//numberofstepsneeededfromroottocurrentnode

8//initialize

addroottoqueue;

addroottoused;

11//BFS

12while(queueisnotempty){

13step=step+1;

14//iteratethenodeswhicharealreadyinthequeue

intsize=queue.size())

16for(inti=0;i<size;++i){

17Nodecur=thefirstnodeinqueue)

returnstepifcuristarget;

for(Nodenext:theneighborsofcur){

if(nextisnotinused){

addnexttoqueue;

addnexttoused;

23}

24}

removethefirstnodefromqueue)

26)

)

28return-11//thereisnopathfromroottotarget

29)

?深度優(yōu)先搜索DFS

?遞歸

1/?

2*Returntruei￡thereisapathfromcurtotarget.

3*/

4booleanDFS(Nodecur.Nodetarget,Set<Node>visited){

returntruei￡curistarget;

for(next：eachneighboro￡cur){

i￡(nextisnotinvisited){

addnexttovisted;

returntruei￡DFS(next,target,visited)=true：

}

11}

12returnfalse;

13}

?迭代(使用Stack,和BFS的模板幾乎一樣，只是將Queue改成Stack)

1/?

2*Returntruei￡thereisapathfromcurtotarget.

3*/

4booleanDFS(introot,inttarget){

Set<Node>visited;

Staclc<Node>s;

addroottos;

while(sisnotempty){

Nodecur=thetopelementins;

returntruei￡curistarget;

for(Nodenext：theneighborso￡cur){

i￡(nextisnotinvisited){

addnexttos;

addnexttovisited;

15}

)

removecurfroms;

18}

19returnfalse;

20}

?遞歸解決方案的優(yōu)點(diǎn)是它更容易實(shí)現(xiàn)。但存在一個(gè)很大的缺點(diǎn)：如果遞歸的深度太高，

將遭受堆棧溢出。

?回溯

.4-4貝爾曼-福特(Bellman-Ford)算法

?貝爾曼-福特算法是一種在圖中求解最短路徑問題的算法。

?貝爾曼-福特算法的執(zhí)行步驟

?首先設(shè)置各個(gè)頂點(diǎn)的初始權(quán)重：起點(diǎn)為0,其他頂點(diǎn)為無窮大(8)。這個(gè)權(quán)重表示的是從

A到該頂點(diǎn)的最短路徑的暫定距離。隨著計(jì)算往下進(jìn)行，這個(gè)值會(huì)變得越來越小，最終收

斂到正確的數(shù)值。

?計(jì)算這條邊從一端到另一端的權(quán)重

?計(jì)算方法是"頂點(diǎn)原本的權(quán)重+邊的權(quán)重"。

?只要按順序分別計(jì)算兩個(gè)方向的權(quán)重即可，從哪一端開始都沒有問題。選擇按頂點(diǎn)權(quán)重

從小到大的方向開始計(jì)算。

?如果計(jì)算結(jié)果小于頂點(diǎn)的值，就更新這個(gè)值。（從權(quán)重較大的頂點(diǎn)到較小的頂點(diǎn)時(shí)，只

要邊的權(quán)重不為負(fù)，就不會(huì)更新權(quán)重。）

?更新時(shí)需要記錄計(jì)算的是從哪個(gè)頂點(diǎn)到該頂點(diǎn)的路徑。

?對所有的邊都執(zhí)行同樣的操作。在執(zhí)行順序上沒有特定要求。

?更新完所有的邊后，第1輪更新就結(jié)束了。

?接著，重復(fù)對所有邊的更新操作，直到權(quán)重不能被更新為止。

?算法的搜索流程結(jié)束，找到了從起點(diǎn)到其余各個(gè)頂點(diǎn)的最短路徑。

?選出一條邊并計(jì)算頂點(diǎn)的權(quán)重時(shí)，無向圖中的計(jì)算兩個(gè)方向都要計(jì)算；在有向圖中只按照

邊所指向的那個(gè)方向來計(jì)算就可以了。

?即便權(quán)重為負(fù)，貝爾曼-福特算法也可以正常運(yùn)行。

?貝爾曼-福特算法的時(shí)間復(fù)雜度

O（nm）

?將圖的頂點(diǎn)數(shù)設(shè)為n、邊數(shù)設(shè)為m,該算法經(jīng)過n輪更新操作后就會(huì)停止。

?@opalli:為什么？因?yàn)槊枯喼辽俑乱粋€(gè)頂點(diǎn)？最多更新n輪？但是一個(gè)頂點(diǎn)可以被更新

多次吧？

?最后確定下來的最短路徑中,必然會(huì)有點(diǎn)是從起點(diǎn)開始的第一個(gè)頂點(diǎn)，該頂點(diǎn)在第一輪

中就會(huì)被更新成正確的值；而在第二輪結(jié)束后，最短路徑中的第二步的頂點(diǎn)也必然會(huì)被

更新成正確的最小值（也可能是在第一輪中就被更新對了）；……；n輪后可以遍歷所

有的點(diǎn)，路徑必然生成,所以路徑的長度必然小于n,且為最短路徑。

?或者可以說，從起點(diǎn)到每個(gè)頂點(diǎn)都會(huì)有一條最短路徑，這條路徑的長度不會(huì)超過n個(gè)

點(diǎn)，每一步至少能更新成功一個(gè)點(diǎn)。

?如果在一個(gè)閉環(huán)中邊的權(quán)重總和是負(fù)數(shù)，那么只要不斷遍歷這個(gè)閉環(huán)，路徑的權(quán)重就能

不斷減小，根本不存在最短路徑。遇到這種對頂點(diǎn)進(jìn)行n次更新操作后仍能繼續(xù)更新

的情況，就可以直接認(rèn)定它“不存在最短路徑”。

?動(dòng)態(tài)規(guī)劃是貝爾曼-福特算法的一個(gè)分類

?4-5狄克斯特拉（Dijkstra）算法

?狄克斯特拉算法也是求解最短路徑問題的算法，從離起點(diǎn)近的頂點(diǎn)開始，按順序求出起點(diǎn)到各

個(gè)頂點(diǎn)的最短路徑。

?@opalli:如果需要求出起點(diǎn)到各個(gè)頂點(diǎn)的最短路徑，那需要算n輪；如果只需要計(jì)算到目

標(biāo)頂點(diǎn)的最短路徑，則計(jì)算到目標(biāo)頂點(diǎn)后，就可以停止計(jì)算了（會(huì)有頂點(diǎn)沒有算出最短路

徑）；而貝爾曼-福特算法不能中途停止，必須算到不再有更新了（當(dāng)然，最多也就是n

輪）。

?假設(shè)起點(diǎn)到達(dá)目標(biāo)頂點(diǎn)X的最短路徑中，X的深度是d的話，則只求目標(biāo)頂點(diǎn)X的最

短路徑的話：

?狄克斯特拉算法更新到第d輪即可結(jié)束；

?而貝爾曼-福特算法則可能需要到第n輪才會(huì)結(jié)束（即使從第d輪以后，目標(biāo)頂點(diǎn)

X的路徑值不會(huì)再更新了，但是其余頂點(diǎn)還在被更新，所以不確定算法是否可以停

止）

?狄克斯特拉算法的執(zhí)行步驟

?從起點(diǎn)出發(fā)尋找可以從目前所在的頂點(diǎn)直達(dá)且尚未被搜索過的頂點(diǎn)，將它們設(shè)為下一步的

候補(bǔ)頂點(diǎn)。@opalli:是尚未被搜索過（沒有成為過權(quán)重最小的點(diǎn)，其可直達(dá)的點(diǎn)也沒有成

為候補(bǔ)頂點(diǎn)），而不是尚未被經(jīng)過或計(jì)算過或更新過。

?計(jì)算各個(gè)候補(bǔ)頂點(diǎn)的權(quán)重。

?計(jì)算方法是“目前所在頂點(diǎn)的權(quán)重+目前所在頂點(diǎn)到候補(bǔ)頂點(diǎn)的權(quán)重"。

?如果計(jì)算結(jié)果小于候補(bǔ)頂點(diǎn)的值，就更新這個(gè)值。

?從候補(bǔ)頂點(diǎn)中選出權(quán)重最小的頂點(diǎn)，如果兩個(gè)候I卜頂點(diǎn)權(quán)重相等，選擇哪一個(gè)都可以

（@opalli:因?yàn)榱硪粋€(gè)馬上就被搜索了，兩個(gè)頂點(diǎn)的直達(dá)頂點(diǎn)最終會(huì)有一個(gè)被選中）。即

確定了從起點(diǎn)到該頂點(diǎn)的最短路徑,移動(dòng)到該頂點(diǎn)，并將可以從該頂點(diǎn)直達(dá)的頂點(diǎn)設(shè)為新

的候補(bǔ)頂點(diǎn)。

?@opalli:到某頂點(diǎn)的最短路徑是通過逐步從候補(bǔ)頂點(diǎn)中選擇權(quán)重最小的頂點(diǎn)來得到的,

其余所有未被搜索過的頂點(diǎn)的權(quán)重都大于此頂點(diǎn)，所以如果經(jīng)過其他（未被搜索的）頂

點(diǎn)到達(dá)此處，最終其權(quán)重必定會(huì)大于這條路徑。

?狄克斯特拉算法一邊逐一確定起點(diǎn)到各個(gè)頂點(diǎn)的最短路徑，一邊對圖進(jìn)行搜索。

?重復(fù)執(zhí)行同樣的操作直到達(dá)終點(diǎn)為止。@opalli:此時(shí)并不一定已經(jīng)遍歷了所有的結(jié)點(diǎn)。

?比起需要對所有的邊都重復(fù)計(jì)算權(quán)重和更新權(quán)重的貝爾曼-福特算法，狄克斯特拉算法多了一步

選擇頂點(diǎn)的操作，這使得它在求最短路徑上更為高效。

?如果圖中含有負(fù)數(shù)權(quán)重，狄克斯特拉算法可能會(huì)無法得出正確答案。

?@opalli:有負(fù)數(shù)權(quán)重時(shí)，即使某個(gè)頂點(diǎn)成為了當(dāng)時(shí)權(quán)重最小的節(jié)點(diǎn)，經(jīng)過其他（未被搜

索的、權(quán)重更大的）頂點(diǎn)到達(dá)此頂點(diǎn)時(shí)，其權(quán)重仍可能更小。

?閉環(huán)中有負(fù)數(shù)權(quán)重，在狄克斯特拉算法中，即便不存在最短路徑，它也會(huì)算出一個(gè)錯(cuò)誤的

最短路徑出來。

?不存在負(fù)數(shù)權(quán)重時(shí)，更適合使用效率較高的狄克斯特拉算法；而存在負(fù)數(shù)權(quán)重時(shí)，即便較為耗

時(shí)，也應(yīng)該使用可以得到正確答案的貝爾曼-福特算法。

?狄克斯特拉算法的時(shí)間復(fù)雜度

?（將圖的頂點(diǎn)數(shù)設(shè)為n、邊數(shù)設(shè)為m）

?不進(jìn)行任］可處理

0(nA2)

?@opalli:每一個(gè)頂點(diǎn)至少要和一個(gè)頂點(diǎn)相連，所以邊數(shù)m不會(huì)小于頂點(diǎn)數(shù)n,狄克斯

特拉算法的時(shí)間復(fù)雜度不會(huì)高于貝爾曼-福特算法的O(mn)。

?對數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化

0(m+nlogn)

?@opalli:數(shù)據(jù)結(jié)構(gòu)優(yōu)化是怎么優(yōu)化的？時(shí)間復(fù)雜度是如何算出來的？

?@opalli:Why?n個(gè)點(diǎn)逐次成為候選點(diǎn)，每個(gè)點(diǎn)最多被更新n-l次？

?@算法圖解

?計(jì)算非加權(quán)圖中的最短路徑，可使用廣度優(yōu)先搜索。要計(jì)算加權(quán)圖中的最短路徑，可使

用狄克斯特拉算法。

?狄克斯特拉算法只適用于有向無環(huán)圖(directedacyclicgraph,DAG)。環(huán)增加了權(quán)

重。如果愿意甚至可繞環(huán)兩次。

?@opalli:覺得有環(huán)圖也是可以用?。恳?yàn)榈铱怂固乩惴〞?huì)忽略走過的節(jié)點(diǎn)，就

不會(huì)走回原來的節(jié)點(diǎn)，即不會(huì)形成環(huán)(可以說有環(huán)圖狄克斯特拉算法也是當(dāng)做無環(huán)

圖來算的),所以有環(huán)也可以找到最短路徑呀(而且繞環(huán)也不可能是最短路徑)