本篇主要涉及到圖論的基本算法，不包含有關(guān)最大流的內(nèi)容。圖論的大部分算法都是由性質(zhì)或推論得出來(lái)的，想樸素想出來(lái)確實(shí)不容易。

二分圖(Is-Bipartite)

一個(gè)圖的所有頂點(diǎn)可以劃分成兩個(gè)子集，使所有的邊的入度和出度頂點(diǎn)分別在這兩個(gè)子集中。

這個(gè)問(wèn)題可以轉(zhuǎn)換為上篇提到過(guò)的圖的著色問(wèn)題，只要看圖是否能著2個(gè)顏色就行了。當(dāng)然，可以回溯解決這個(gè)問(wèn)題，不過(guò)對(duì)于著2個(gè)顏色可以BFS解決。

同樣，一維數(shù)組colors表示節(jié)點(diǎn)已著的顏色。

偽代碼：

IS-BIPARTITE(g,colors)

let queue be new Queue

colors[0] = 1

queue.push(0)

while queue.empty() == false

let v = queue.top()

queue.pop()

for i equal to every vertex in g

if colors[i] == 0

colors[i] = 3 - colors[v]

queue.push(i)

else if colors[i] == colors[v]

return false

end

end

return true

時(shí)間復(fù)雜度:Θ(V+E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

DFS改良(DFS-Improve)

上篇文章提到過(guò)，搜索解空間是樹(shù)形的，也就是在說(shuō)BFS和DFS。那么在對(duì)圖進(jìn)行BFS和DFS有什么區(qū)別呢，這個(gè)問(wèn)題要從解空間角度去理解。對(duì)圖進(jìn)行BFS的解空間是一顆樹(shù)，可叫廣度優(yōu)先樹(shù)。而DFS是多棵樹(shù)構(gòu)成的森林，可叫深度優(yōu)先森林。

這里要對(duì)DFS進(jìn)行小小的改良，它的性質(zhì)會(huì)對(duì)解多個(gè)問(wèn)題會(huì)很有幫助。原版DFS搜索的時(shí)候，會(huì)先遍歷本頂點(diǎn)，再遞歸遍歷臨接的頂點(diǎn)。DFS改良希望能先遞歸遍歷臨接的頂點(diǎn)，再遍歷本頂點(diǎn)，并且按遍歷順序逆序存儲(chǔ)起來(lái)。

偽代碼：

DFS-IMPROVE(v,visited,stack)

visited[v] = true

for i equal to every vertex adjacent to v

if visited[i] == false

DFS-IMPROVE(i,visited,stack)

end

stack.push(v)

這個(gè)改良版DFS有個(gè)很有用的性質(zhì)就是，對(duì)于兩個(gè)頂點(diǎn)A、B，存在A到B的路徑，而不存在B到A的路徑，則從記錄的順序中取出的時(shí)候，一定會(huì)先取出頂點(diǎn)A，再取出頂點(diǎn)B。以下為這個(gè)性質(zhì)的證明。

假設(shè)：有兩個(gè)頂點(diǎn)A和B，存在路徑從A到B，不存在路徑從B到A。

證明：分為兩種情況，情況一，先搜索到A頂點(diǎn)，情況二，先搜索到B頂點(diǎn)。對(duì)于情況一，由命題可得，A一定存儲(chǔ)在B之后，那么取出時(shí)先取出的是頂點(diǎn)A。對(duì)于情況二，先搜索到B頂點(diǎn)，由于B頂點(diǎn)搜索不到A頂點(diǎn)，則A一定存儲(chǔ)在B之后，那么取出時(shí)仍先取出的是頂點(diǎn)A，命題得證。

DFS改良性質(zhì)：對(duì)于兩個(gè)頂點(diǎn)A、B，存在A到B的路徑，而不存在B到A的路徑，則從記錄的順序中取出的時(shí)候，一定會(huì)先取出頂點(diǎn)A，再取出頂點(diǎn)B。

歐拉回路(Eulerian-Path-And-Circuit)

在無(wú)向圖中，歐拉路徑定義為，一條路徑經(jīng)過(guò)所有的邊，每個(gè)邊只經(jīng)過(guò)一次。歐拉回路定義為，存在一條歐拉路徑且路徑的起點(diǎn)和終點(diǎn)為同一個(gè)頂點(diǎn)?？梢钥吹街挥羞B通圖才能有歐拉回路和歐拉路徑。

這個(gè)算法很巧。如果一條路徑要經(jīng)過(guò)一個(gè)頂點(diǎn)，本質(zhì)是從一條邊到達(dá)一個(gè)頂點(diǎn)，然后從這個(gè)頂點(diǎn)通過(guò)另一條邊出去。歐拉回路就是要求路徑要經(jīng)過(guò)所有的點(diǎn)，起點(diǎn)和終點(diǎn)還都是同一個(gè)頂點(diǎn)。那么就等價(jià)于要求所有頂點(diǎn)連接的邊是2個(gè)。實(shí)際上，路徑還可以經(jīng)過(guò)頂點(diǎn)多次，那么就等價(jià)于要求所有頂點(diǎn)連接的邊是偶數(shù)個(gè)。歐拉路徑的要求就等價(jià)于所有頂點(diǎn)連接的邊是偶數(shù)個(gè)，除了起點(diǎn)和終點(diǎn)兩個(gè)頂點(diǎn)可以是奇數(shù)個(gè)。

先判斷圖是否是連通圖。返回0代表沒(méi)有歐拉回路或者歐拉路徑，返回1代表有歐拉路徑，返回2代表有歐拉回路。

偽代碼：

EULERIAN-PATH-AND-CIRCUIT(g)

if isConnected(g) == false

return 0

let odd = 0

for v equal to every vertex in g

if v has not even edge

odd = odd + 1

end

if odd > 2

returon 0

if odd == 1

return 1

if odd == 0

return 2

時(shí)間復(fù)雜度:Θ(V+E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

拓?fù)渑判?Topological-Sorting)

將一張有向無(wú)環(huán)圖的頂點(diǎn)排序，排序規(guī)則是所有邊的入度頂點(diǎn)要在出度頂點(diǎn)之前。可以看到，無(wú)向和有環(huán)圖都不存在拓?fù)渑判颍⑶彝負(fù)渑判蚩赡艽嬖诙喾N解。

拓?fù)渑判蛴袃煞N解法，一種是從搜索角度。

如果我能保障先遞歸遍歷臨接的頂點(diǎn)，再遍歷本頂點(diǎn)的話，那么遍歷的順序的逆序就是一個(gè)拓?fù)渑判?。那么就可以直接用DFS改良求解出拓?fù)渑判颉?/p>

偽代碼：

TOPOLOGICAL-SORTING-DFS(g)

let visited be new Array

let result be new Array

let stack be new Stack

for v equal to every vertex in g

if visited[v] == false

DFS-IMPROVE(v,visited,stack)

end

while stack.empty() == false

result.append(stack.top())

stack.pop()

end

return result

時(shí)間復(fù)雜度:Θ(V+E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

另一種是貪心選擇。

直覺(jué)上，既然要所有邊的出度頂點(diǎn)在入度頂點(diǎn)之前，可以從入度和出度角度來(lái)解決問(wèn)題?？梢宰屓攵茸钚〉呐判蛟谇埃部梢宰尦龆茸畲蟮呐判蛟诤?，排序后，這個(gè)頂點(diǎn)的邊都不會(huì)再影響問(wèn)題了，可以去掉。去掉后再重新加入新的頂點(diǎn)，直到加入所有頂點(diǎn)。

這個(gè)問(wèn)題還有個(gè)隱含條件，挑選出、入度最小的頂點(diǎn)就等價(jià)于挑選出、入度為0的頂點(diǎn)。這是因?yàn)閳D必須是無(wú)環(huán)圖，所以肯定存在出、入度為0的頂點(diǎn)，那么出、入度最小的頂點(diǎn)就是出、入度為0的頂點(diǎn)。

直覺(jué)上這是一個(gè)可行的策略，細(xì)想一下，按出度最大排序和按入度為零排序是否等價(jià)。實(shí)際上是不等價(jià)的，按入度為零排序，如果出現(xiàn)了多個(gè)入度為零的頂點(diǎn)，這多個(gè)頂點(diǎn)排序的順序是無(wú)關(guān)的，可以任意排序。而按出度最大排序，出現(xiàn)了多個(gè)入度最大的頂點(diǎn)，這多個(gè)頂點(diǎn)排序是有關(guān)的，不能任意排序。所以，只能按入度為零排序。實(shí)際上，這個(gè)想法就是貪心選擇。下面以挑選入度為零的邊作為貪心選擇解決問(wèn)題，同樣地，還是先證明這個(gè)貪心選擇的正確性。

命題：入度為零的頂點(diǎn)v排序在前。

假設(shè)：S為圖的一個(gè)拓?fù)渑判?，l為此排序的首個(gè)頂點(diǎn)。

證明：如果l=v，則命題得證。如果l不等于v，將l頂點(diǎn)從S中去除，然后加入頂點(diǎn)v得到新的排序S‘。因?yàn)镾去除l以后l以后的排序沒(méi)有變，仍為拓?fù)渑判?，v入度為零，v前面可以沒(méi)有頂點(diǎn)，所以S’也為圖的一個(gè)拓?fù)渑判?，命題得證。

偽代碼：

TOPOLOGICAL-SORTING-GREEDY(g)

let inDegree be every verties inDegree Array

let stack be new Stack

let result be new Array

for v equal to every vertex in g

if inDegree[v] == 0

stack.push(v)

end

while stack.empty() == false

vertex v = stack.top()

stack.pop()

result.append(v)

for i equal to every vertex adjacent to v

inDegree[i] = inDegree[i] - 1

if inDegree[i] == 0

stack.push(i)

end

end

return result.reverse()

時(shí)間復(fù)雜度:Θ(V+E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

強(qiáng)連通分量(Strongly-Connected-Components)

圖中的一個(gè)頂點(diǎn)與另一個(gè)頂點(diǎn)互相都有路徑可以抵達(dá)，就說(shuō)這兩個(gè)頂點(diǎn)強(qiáng)連通。圖中有多個(gè)頂點(diǎn)兩兩之間都強(qiáng)連通，則這多個(gè)頂點(diǎn)構(gòu)成圖的強(qiáng)連通分量。

樸素的想法是，假如從一個(gè)頂點(diǎn)A可以搜索到另一個(gè)頂點(diǎn)B，如果從B頂點(diǎn)再能搜索回A頂點(diǎn)的話，A、B就在一個(gè)強(qiáng)連通分量中。不過(guò)，這樣每?jī)蓚€(gè)頂點(diǎn)要進(jìn)行兩次DFS，復(fù)雜度肯定會(huì)很高。這里可以引入轉(zhuǎn)置圖(將有向邊的方向翻轉(zhuǎn))的性質(zhì)。這樣問(wèn)題就轉(zhuǎn)換成了，從A頂點(diǎn)搜索到B頂點(diǎn)，將圖轉(zhuǎn)置后，如果再A頂點(diǎn)還能搜索到B頂點(diǎn)，A、B頂點(diǎn)就在一個(gè)強(qiáng)連通分量中。用算法表述出來(lái)就是先從A頂點(diǎn)DFS，然后將圖轉(zhuǎn)置，再?gòu)腁頂點(diǎn)DFS，兩次DFS都能搜索到B頂點(diǎn)的話，B頂點(diǎn)就與A頂點(diǎn)在同一個(gè)強(qiáng)連通分量中。然而樸素想法只能想到這里了。

有多個(gè)算法被研究出來(lái)解決這個(gè)問(wèn)題，下面先介紹Kosaraju算法。

Kosaraju

Kosaraju算法使用了DFS改良的性質(zhì)去解決問(wèn)題，想法很有趣。Kosaraju算法現(xiàn)將圖進(jìn)行DFS改良，然后將圖轉(zhuǎn)置，再進(jìn)行DFS。第二次DFS每個(gè)頂點(diǎn)能夠搜索到的點(diǎn)就是一個(gè)強(qiáng)連通分量。算法正確性和說(shuō)明如下。

通過(guò)DFS改良性質(zhì)可以得出定理，一個(gè)強(qiáng)連通分量C如果有到達(dá)另一個(gè)強(qiáng)連通分量C’的路徑，則C’比C先被搜索完，這個(gè)定理很明顯，如果C中有路徑到C’，那么根據(jù)DFS改良性質(zhì)一定會(huì)先搜索到C，再搜索完C’，再搜索完C。將這個(gè)定理做定理1。

定理1：一個(gè)強(qiáng)連通分量C如果有到達(dá)另一個(gè)強(qiáng)連通分量C’的路徑，則C’比C先被搜索完。

定理1還可以再進(jìn)行推論，如果一個(gè)強(qiáng)連通分量C有到達(dá)另一個(gè)強(qiáng)連通分量C’的路徑，則將圖轉(zhuǎn)置后，C比C’先被搜索完，這個(gè)推論也很明顯，將圖轉(zhuǎn)置后，不存在C到C’的路徑，存在C’到C的路徑，而仍是先搜索C再搜索C‘，所以C比C‘先被搜索完，這個(gè)推論作為推論1。

推論1：如果一個(gè)強(qiáng)連通分量C有到達(dá)另一個(gè)強(qiáng)連通分量C’的路徑，則將圖轉(zhuǎn)置后，C比C’先被搜索完。

以下為用結(jié)構(gòu)歸納法對(duì)算法正確性進(jìn)行證明。

命題：第二次DFS每個(gè)頂點(diǎn)能夠搜索到的點(diǎn)就是一個(gè)強(qiáng)連通分量。

假設(shè)：n代表圖中有多少個(gè)強(qiáng)連通分量。

證明：如果n=1，則第二次DFS就是搜索一遍所有頂點(diǎn)，命題得證?，F(xiàn)在假設(shè)n=k時(shí)，命題成立?，F(xiàn)證明n=k+1時(shí)，是否成立。假設(shè)搜索到第k+1個(gè)強(qiáng)連通分量的第一個(gè)頂點(diǎn)為u，u肯定能搜索到所有k+1個(gè)強(qiáng)連通分量的頂點(diǎn)。并且根據(jù)推論1，此時(shí)被轉(zhuǎn)置后的圖，所有從第k+1個(gè)強(qiáng)連通分量能到達(dá)的其他強(qiáng)連通分量都已經(jīng)被搜索過(guò)了。所以u(píng)只能搜索到所有第k+1個(gè)強(qiáng)連通分量的頂點(diǎn)，即第二次DFS每個(gè)頂點(diǎn)只能夠搜索到包含此頂點(diǎn)的強(qiáng)連通分量中的頂點(diǎn)，命題得證。

偽代碼：

KOSARAJU-STRONGLY-CONNECTED-COMPONENTS(g)

let visited be new Array

let stack be new Stack

for v equal to every vertex in g

if visited[v] == false

DFS-IMPROVE(v,visited,stack)

end

let gt = transpose of g

for v equal to every vertex in g

visited[v] = false

end

while stack.empty() == false

vertex v = stack.top()

stack.pop()

if visited[v] == false

DFS(v,visited)

print ' Found a Strongly Connected Components '

end

DFS(v,visited)

visited[v] = true

print v

for i equal to every vertex adjacent to v

if visited[i] == false

DFS(i,visited,stack)

end

時(shí)間復(fù)雜度:Θ(V+E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

Kosaraju算法需要進(jìn)行兩次DFS，那么可不可以只進(jìn)行一次DFS，邊遍歷邊找強(qiáng)連通分量？Tarjan就是這樣的算法。

Tarjan

同樣，還是要基于DFS搜索性質(zhì)來(lái)思考問(wèn)題。DFS創(chuàng)建出的深度優(yōu)先搜索樹(shù)會(huì)先被訪問(wèn)根節(jié)點(diǎn)再被訪問(wèn)子孫節(jié)點(diǎn)。什么時(shí)候會(huì)出現(xiàn)強(qiáng)連通分量？只有子孫節(jié)點(diǎn)有連通祖先節(jié)點(diǎn)的邊的時(shí)候。如果從某個(gè)節(jié)點(diǎn)，其子孫節(jié)點(diǎn)都只有指向自己子孫節(jié)點(diǎn)的邊的時(shí)候，這是明顯沒(méi)有構(gòu)成強(qiáng)連通分量的。那么，出現(xiàn)了子孫節(jié)點(diǎn)指向其祖先節(jié)點(diǎn)的時(shí)候，從被指向的祖先節(jié)點(diǎn)一直搜索到指向的子孫節(jié)點(diǎn)所經(jīng)過(guò)所有頂點(diǎn)就構(gòu)成了一個(gè)強(qiáng)連通分量。如果出現(xiàn)了多個(gè)子孫節(jié)點(diǎn)都指向了祖先節(jié)點(diǎn)怎么辦？最早被指向、訪問(wèn)的祖先節(jié)點(diǎn)到最晚指向、訪問(wèn)的子孫節(jié)點(diǎn)構(gòu)成了“最大“的強(qiáng)連通分量，這才是想要找的強(qiáng)連通分量。如果遇到了一個(gè)指向祖先節(jié)點(diǎn)的子孫節(jié)點(diǎn)，就算構(gòu)成一個(gè)強(qiáng)連通分量，會(huì)導(dǎo)致找到多個(gè)互相嵌套的強(qiáng)連通分量。那么，要記錄訪問(wèn)順序就要為每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)被訪問(wèn)順序的編號(hào)，讓屬于同一個(gè)強(qiáng)連通分量的頂點(diǎn)編號(hào)一致。上面討論的是構(gòu)成了一個(gè)強(qiáng)連通分量怎么處理，如果沒(méi)有多個(gè)節(jié)點(diǎn)構(gòu)成的強(qiáng)連通分量怎么處理？在搜索節(jié)點(diǎn)之前，為這個(gè)節(jié)點(diǎn)默認(rèn)設(shè)置上被訪問(wèn)的順序編號(hào)，這樣如果沒(méi)有搜索到多個(gè)節(jié)點(diǎn)構(gòu)成的強(qiáng)連通分量，每個(gè)節(jié)點(diǎn)就是自己的強(qiáng)連通分量。

算法表述為，從某個(gè)節(jié)點(diǎn)開(kāi)始搜索，默認(rèn)設(shè)置自己為一個(gè)強(qiáng)連通分量。只要節(jié)點(diǎn)有子孫節(jié)點(diǎn)，就要等待子孫節(jié)點(diǎn)都搜索完，再更新自己強(qiáng)連通分量信息。只要節(jié)點(diǎn)有指向祖先節(jié)點(diǎn)，也要更新自己的強(qiáng)連通分量。判斷子孫節(jié)點(diǎn)構(gòu)成的強(qiáng)連通分量”大“還是自己構(gòu)成的強(qiáng)連通分量”大“，自己屬于最”大“的強(qiáng)連通分量。也就是說(shuō)，算法找出了所有頂點(diǎn)的所屬的最“大”強(qiáng)連通分量。

數(shù)組disc表示頂點(diǎn)被訪問(wèn)順序的編號(hào)，數(shù)組low表示頂點(diǎn)所在的強(qiáng)連通分量編號(hào)。最后當(dāng)頂點(diǎn)在disc和low中編號(hào)一致時(shí)，代表頂點(diǎn)是所在強(qiáng)連通分量中第一個(gè)被搜索到的頂點(diǎn)。此時(shí)，輸出所在的強(qiáng)連通分量所包括的頂點(diǎn)。

偽代碼：

TARJAN-STRONGLY-CONNECTED-COMPONENTS(g)

let disc be new Array

let low be new Array

let stack be new Stack

let isInStack be new Array

for i from 1 to the number of vertex in g

disc [i] = -1

low [i] = -1

end

for u from 1 to the number of vertex in g

if disc[i] != -1

TARJAN-STRONGLY-CONNECTED-COMPONENTS-UTIL(u,disc,low,stack,isInStack)

end

TARJAN-STRONGLY-CONNECTED-COMPONENTS-UTIL(u,disc,low,stack,isInStack)

let time be static

time = time + 1

disc[u] = low[u] = time

stack.push(u)

isInStack[u] = true

for v equal to every vertex adjacent to u

if disc[v] == -1

TARJAN-STRONGLY-CONNECTED-COMPONENTS-UTIL(v,disc,low,stack,isInStack)

low[u] = min(low[u],low[v])

else if isInStack[v] == true

low[u] = min(low[u],disc[v])

end

let w = 0

if low[u] == disc[u]

while stack.top() != u

w = stack.top()

isInStack[w] = false

stack.pop()

print w

end

w = stack.top()

isInStack[w] = false

stack.pop()

print w

print ' Found a Strongly Connected Components '

時(shí)間復(fù)雜度:Θ(V+E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

圖的割點(diǎn)(Articulation Points)、橋(Bridge)、雙連通分量(Biconnected Components)

圖的割點(diǎn)(Articulation-Points)

圖的割點(diǎn)也叫圖的關(guān)節(jié)點(diǎn)，定義為無(wú)向圖中分割兩個(gè)連通分量的點(diǎn)，或者說(shuō)去掉這個(gè)點(diǎn)，圖中的連通分量數(shù)增加了?？梢钥吹饺绻蟪隽诉B通分量，那么不同連通分量中間的頂點(diǎn)就是割點(diǎn)。什么時(shí)候某個(gè)頂點(diǎn)不是這樣的割點(diǎn)？如果這個(gè)頂點(diǎn)的子孫頂點(diǎn)有連接這個(gè)頂點(diǎn)祖先頂點(diǎn)的邊，那么去掉這個(gè)頂點(diǎn)，這個(gè)頂點(diǎn)的子孫頂點(diǎn)和祖先頂點(diǎn)仍然連通。那么，尋找割點(diǎn)的過(guò)程就等價(jià)于尋找子孫頂點(diǎn)沒(méi)有連接祖先頂點(diǎn)的頂點(diǎn)。這個(gè)問(wèn)題的求解過(guò)程類似于Tarjan強(qiáng)連通分量的求解過(guò)程。

不過(guò)，這個(gè)問(wèn)題有個(gè)例外就是根頂點(diǎn)，對(duì)一般頂點(diǎn)的處理方式處理根頂點(diǎn)行得通嗎？根頂點(diǎn)肯定沒(méi)有子孫頂點(diǎn)指向祖先頂點(diǎn)，但是根頂點(diǎn)可以是割點(diǎn)。所以，根頂點(diǎn)需要特殊處理。根頂點(diǎn)什么時(shí)候是割點(diǎn)？當(dāng)根頂點(diǎn)有多顆子樹(shù)，且之間無(wú)法互相到達(dá)的時(shí)候。那么，存不存在根頂點(diǎn)有多顆子樹(shù)，且之間可以互相到達(dá)？不存在，如果互相之間可以到達(dá)，那在根頂點(diǎn)搜索第一顆子樹(shù)的時(shí)候，就會(huì)搜索到可到達(dá)的子樹(shù)，就不會(huì)存在多顆子樹(shù)了。所以，根頂點(diǎn)有多顆子樹(shù)，那么這多顆子樹(shù)之間一定無(wú)法互相到達(dá)。根頂點(diǎn)有多顆子樹(shù)，且之間無(wú)法互相到達(dá)的時(shí)候就等價(jià)于根頂點(diǎn)有多顆子樹(shù)。所以，只要根頂點(diǎn)有多顆子樹(shù)，那么根頂點(diǎn)就是割點(diǎn)。

同樣地，數(shù)組disc表示頂點(diǎn)被訪問(wèn)順序的編號(hào)，數(shù)組low表示頂點(diǎn)所在的強(qiáng)連通分量編號(hào)。數(shù)組parent找出根頂點(diǎn)。

偽代碼：

ARTICULATION-POINTS(g)

let disc be new Array

let low be new Array

let result be new Array

let parent be new Array

let visited be new Array

for i from 1 to the number of vertex in g

result [i] = false

visited [i] = false

parent [i] = -1

end

for u from 1 to the number of vertex in g

if visited[i] == false

ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)

end

for i from 1 to the number if vertex in g

if result[i] == true

print ' Found a Articulation Points i '

end

ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)

let time be static

time = time + 1

let children = 0

disc[u] = low[u] = time

visited[u] = true

for v equal to every vertex adjacent to u

if visited[v] == false

children = children + 1

parent[v] = u

ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)

low[u] = min(low[u],low[v])

if parnet[u] == -1 and children > 1

result[u] = true

if parent[u] != -1 and low[v] >= disc[u]

result[u] = true

else if v != parent[u]

low[u] = min(low[u],disc[v])

end

時(shí)間復(fù)雜度:Θ(V+E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

橋(Bridge)

橋定義為一條邊，且去掉這個(gè)邊，圖中的連通分量數(shù)增加了。類似于尋找割點(diǎn)，尋找橋就是尋找這樣一條，一端的頂點(diǎn)的子孫頂點(diǎn)沒(méi)有連接這個(gè)頂點(diǎn)和其祖先頂點(diǎn)的邊。求解過(guò)程和求割點(diǎn)基本一致。

偽代碼：

BRIDGE(g)

let disc be new Array

let low be new Array

let parent be new Array

let visited be new Array

for i from 1 to the number of vertex in g

visited [i] = false

parent [i] = -1

end

for u from 1 to the number of vertex in g

if visited[i] == false

BRIDGE-UTIL(u,disc,low,parent,visited)

end

BRIDGE-UTIL(u,disc,low,parent,visited)

let time be static

time = time + 1

disc[u] = low[u] = time

for v equal to every vertex adjacent to u

if visited[v] == false

parent[v] = u

BRIDGE-UTIL(u,disc,low,parent,visited)

low[u] = min(low[u],low[v])

if low[v] > disc[u]

print ' Found a Bridge u->v '

else if v != parent[u]

low[u] = min(low[u],disc[v])

end

時(shí)間復(fù)雜度:Θ(V+E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

雙連通分量(Biconnected-Components)

雙連通圖定義為沒(méi)有割點(diǎn)的圖。雙連通圖的極大子圖就為雙連通分量。雙連通分量就是在割點(diǎn)分割成多個(gè)連通分量處，共享割點(diǎn)。也就是說(shuō)雙連通分量是去掉割點(diǎn)后構(gòu)成的連通分量，加上割點(diǎn)和到達(dá)割點(diǎn)的邊?？梢钥闯?，雙連通分量可分為不含有割點(diǎn)、一個(gè)割點(diǎn)、兩個(gè)割點(diǎn)三種情況。對(duì)于不含有割點(diǎn)，說(shuō)明圖為雙連通圖。對(duì)于含有一個(gè)割點(diǎn)，可能為初始搜索的頂點(diǎn)到第一個(gè)割點(diǎn)之間的邊構(gòu)成的雙連通分量，可能為遇到一個(gè)割點(diǎn)后到不再遇到割點(diǎn)之間的邊構(gòu)成雙連通分量。對(duì)于含有兩個(gè)割點(diǎn)，兩個(gè)割點(diǎn)之間的邊構(gòu)成了一個(gè)雙連通分量。

求解此問(wèn)題，只要在求割點(diǎn)的算法上做更改就可以了。按照求割點(diǎn)的算法求解割點(diǎn)，找到一個(gè)割點(diǎn)，輸出找到的邊，然后刪除找到的邊的記錄，再去搜索下一個(gè)割點(diǎn)。每搜索完圖某個(gè)頂點(diǎn)的可達(dá)頂點(diǎn)，輸出找到的邊。這樣就涵蓋了所有的情況。

偽代碼：

BICONNECTED-COMPONENTS(g)

let disc be new Array

let low be new Array

let stack be new Stack

let parent be new Array

for i from 1 to the number of vertex in g

disc [i] = -1

low [i] = -1

parent [i] = -1

end

for u from 1 to the number of vertex in g

if disc[i] == -1

BICONNECTED-COMPONENTS-UTIL(u,disc,low,stack,parent)

let flag = flase

while stack.empty() == false

flag = true

print stack.top().src -> stack.top().des

stack.pop()

end

if flag == true

print ' Found a Bioconnected-Components '

end

BICONNECTED-COMPONENTS-UTIL(u,disc,low,stack,parent)

let time be static

time = time + 1

let children = 0

disc[u] = low[u] = time

for v equal to every vertex adjacent to u

if disc[v] == -1

children = children + 1

parent[v] = u

stack.push(u->v)

BICONNECTED-COMPONENTS-UTIL(u,disc,low,stack,parent)

low[u] = min(low[u],low[v])

if (parnet[u] == -1 and children > 1) or (parent[u] != -1 and low[v] >= disc[u])

while stack.top().src != u or stack.top().des != v

print stack.top().src -> stack.top().des

stack.pop()

end

print stack.top().src -> stack.top().des

stack.pop()

print ' Found a Bioconnected-Components '

else if v != parent[u] and disc[v] < low[u]

low[u] = min(low[u],disc[v])

stack.push(u->v)

end

時(shí)間復(fù)雜度:Θ(V+E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

最小生成樹(shù)(Minimum-Spanning-Tree)

生成樹(shù)是指，在一個(gè)連通、無(wú)向、有權(quán)的圖中，所有頂點(diǎn)構(gòu)成的一顆樹(shù)。圖中可以有多顆生成樹(shù)，而生成樹(shù)的代價(jià)就是樹(shù)中所有邊的權(quán)重的和。最小生成樹(shù)就是生成樹(shù)中代價(jià)最小的。

樸素的想法就是從圖中選擇最小權(quán)重的邊，直到生成一顆樹(shù)?？赐ㄓ玫乃惴ㄖ?，同樣要討論一下最小生成樹(shù)的性質(zhì)。

對(duì)于一個(gè)連通、無(wú)向、有權(quán)圖中，一定有最小生成樹(shù)。如果圖不包含最小生成樹(shù)的任意一條邊，那么圖就是不連通的了，這與已知連通圖不符，所以圖必包含最小生成樹(shù)。

假設(shè)，A為某個(gè)最小生成樹(shù)的子集(任意一個(gè)頂點(diǎn)都是最小生成樹(shù)的子集)。

那么，為A一直添加對(duì)的邊，A最后就會(huì)成為一顆最小生成樹(shù)。那么最小生成樹(shù)問(wèn)題就轉(zhuǎn)換成為了，一直找到對(duì)的邊，直到成為一顆最小生成樹(shù)。這個(gè)對(duì)的邊可以叫做安全邊。

安全邊如何尋找顯然就成了解決這個(gè)問(wèn)題的關(guān)鍵點(diǎn)。

再假設(shè)，圖中所有頂點(diǎn)為V，將所有頂點(diǎn)切割成兩個(gè)部分S和V減去S。所有連接這兩個(gè)部分的邊，很形象的叫做橫跨切割，這些邊橫跨了兩個(gè)部分，成為這兩個(gè)部分的橋梁。這里還有個(gè)問(wèn)題，如何切割？使A不包含橫跨切割。這樣的切割有多種切法，切割后，橫跨切割的最小代價(jià)邊就為A的安全邊。將這個(gè)作為定理1。

定理1：存在這樣一個(gè)將所有頂點(diǎn)分成兩個(gè)部分的切割，且使某個(gè)最小生成樹(shù)子集A不包含橫跨切割。則橫跨此切割的最小代價(jià)邊，就是A的安全邊。

以下為此定理的證明，這個(gè)定理的基礎(chǔ)實(shí)際上是連通性。

命題：橫跨切割的最小代價(jià)邊為A的安全邊。

假設(shè)：橫跨切割后的最小代價(jià)邊為x，有最小生成樹(shù)T包含A，但是不包含x。

證明：既然T不包含x，那么T必須包含另一條連接x兩端頂點(diǎn)的路徑，這條路徑上又必須有條邊橫跨切割。假設(shè)這條邊為y。T將y減去后，x兩端的頂點(diǎn)就無(wú)法互相到達(dá)。這時(shí)如果再加上x(chóng)，那么x兩端的頂點(diǎn)又可以互相到達(dá)，并且構(gòu)造了另一顆生成樹(shù)T’?？梢钥吹剑瑇的代價(jià)小于或等于y的代價(jià)，那么T‘的代價(jià)也小于或等于T的代價(jià)，那么T’也就是一顆最小生成樹(shù)。那么x既不在A中，x又在一顆包含A的最小生成樹(shù)中。命題得證。

可以看到這個(gè)證明過(guò)程使用的就是經(jīng)常拿來(lái)證明貪心選擇的技巧，也就是說(shuō)最小生成樹(shù)問(wèn)題符合貪心算法的特征，也就解釋了為什么下面將要提到的兩個(gè)算法都是貪心算法。

定理1還可以進(jìn)行推論，既然切割有多種方法，那可不可以對(duì)A和其余的頂點(diǎn)進(jìn)行切割，設(shè)B為包括A和所有頂點(diǎn)構(gòu)成的一個(gè)森林，C是其中的一個(gè)連通分量，那么C連接其他的連通分量的最小代價(jià)邊是A的安全邊。這個(gè)推論很好證明，因?yàn)锳是B中的一個(gè)或者多個(gè)連通分量，如果按照C去切割圖分成C和B減去C，不可能切割A(yù)，即A中必定不包含橫跨切割。那么，橫跨這個(gè)切割的最小代價(jià)邊就是安全邊，即C連接其他連通分量的最小代價(jià)邊，推論成立。將這個(gè)推論作為推論1。

推論1:某個(gè)最小生成樹(shù)子集A和其他頂點(diǎn)構(gòu)成的森林中，任意一個(gè)連通分量連接其他連通分量的最小代價(jià)邊都為A的安全邊。

如果從所有不在A中的邊選擇最小代價(jià)的邊，這個(gè)邊一定連接著某個(gè)連通分量，這個(gè)推論也就將選安全邊的范圍拓展到任意一條不在A中的邊。這個(gè)推論正好可以證明樸素想法的正確性。

接下來(lái)看一下最小生成樹(shù)的三個(gè)通用的算法Kruskal、Prime、Boruvka。

Kruskal

樸素想法和Kruskal已經(jīng)很接近了。Kruskal算法做的就是一直選擇代價(jià)最小的邊，不過(guò)，如果選擇這個(gè)邊后，無(wú)生成最小生成樹(shù)，而生成圖了怎么辦？Kruskal比樸素想法巧的地方就是不選擇會(huì)成環(huán)的邊。

Kruskal常用的檢查是否成環(huán)的數(shù)據(jù)結(jié)構(gòu)是UnionFind(并查集)，UnionFind有個(gè)操作，一個(gè)是Find檢查元素所在集合的編號(hào)，Union將兩個(gè)元素合并成一個(gè)集合。

KRUSKAL(g)

let edges be all the edges of g

sort(edges)

let uf be new UnionFind

let e = 0

let i = 0

let result be new Array

while e < edges.length()

let edge = edges[i]

i = i + 1

if uf.find(edge.src) != uf.find(edge.des)

result.append(edge)

e = e + 1

uf.union(edge.src,edge.des)

end

return result

V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)，排序E個(gè)邊加上E次UnionFind操作

時(shí)間復(fù)雜度:O(Elog2E+Elog2V)

Prim

有了推論1，Prim算法的正確性理解起來(lái)就很簡(jiǎn)單了，一直只對(duì)最小生成樹(shù)子集進(jìn)行切割，然后選擇出最小生成樹(shù)子集與其他連通分量的最小代價(jià)邊就OK了。Prim算法就是一直選擇最小生成樹(shù)子集與其他頂點(diǎn)連接的最小代價(jià)邊。

Prim算法維持這樣一個(gè)最小堆，存儲(chǔ)最小生成樹(shù)子集以外的頂點(diǎn)，與最小生成樹(shù)子集臨接的頂點(diǎn)的權(quán)重是其臨接邊的值，其余的最小堆中的頂點(diǎn)權(quán)重都是無(wú)窮。Prim算法初始將起始頂點(diǎn)在最小堆中的權(quán)重置為0，其余的頂點(diǎn)置為無(wú)窮。然后從最小堆中一直取權(quán)重最小的頂點(diǎn)，即選擇最小代價(jià)邊加入最小生成樹(shù)，如果取出的頂點(diǎn)的臨接頂點(diǎn)不在最小生成樹(shù)中，且這個(gè)臨接頂點(diǎn)在最小堆中的權(quán)重比邊大，則更新臨接頂點(diǎn)在最小堆的權(quán)重，直到從最小堆中取出所有的頂點(diǎn)，就得到了一顆最小生成樹(shù)。

偽代碼：

PRIM(g,s)

let heap be new MinHeap

let result be new Array

for i from 1 to the number of vertex in g

let vertex be new Vertex(i)

vertex.weight = INT_MAX

heap.insert(vertex)

end

heap.decrease(s,0)

while heap.empty() == false

vertex v = heap.top()

for u equal to every vertex adjacent to v

if heap.isNotInHeap(u) and v->u < heap.getWeightOfNode(u)

result[u] = v

heap.decrease(u,v->u)

end

end

return result

V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)，對(duì)V個(gè)頂點(diǎn)和E條邊進(jìn)行decrease操作

時(shí)間復(fù)雜度:O(Elog2V+Vlog2V)

Boruvka

Kruskal是根據(jù)所有邊中最小代價(jià)邊的一端的連通分量分割，Prim根據(jù)最小生成子樹(shù)的子集分割，Boruvka根據(jù)所有的連通分量分割，實(shí)際上都是基于推論1。Boruvka算法將所有連通分量與其他連通分量的最小代價(jià)邊選擇出來(lái)，然后將這些邊中未加入最小生成樹(shù)子集的加進(jìn)去，一直到生成最小生成樹(shù)。

Boruvka算法同樣使用了UnionFind去記錄連通分量，用cheapest數(shù)組記錄連通分量與其他連通分量連接的最小代價(jià)邊的編號(hào)。

偽代碼：

Boruvka(g)

let uf be new UnionFind

let cheapest be new Array

let edges be all the edge of g

let numTree = the number of vertex in g

let result be new Array

for i from 1 to number of vertex in g

cheapest[i] = -1

end

while numTree > 0

for i from 1 to the number of edge in g

let set1 = uf.find(edges[i].src)

let set2 = uf.find(edges[i].des)

if set1 == set2

continue

if cheapest[se1] == -1 or edges[cheapest[set1]].weight > edges[i].weight

cheapest[set1] = i

if cheapest[set2] == -1 or edges[cheapest[set2]].weight > edges[i].weight

cheapest[set2] = i

end

for i from 1 to the number of vertex in g

if cheapest[i] != -1

let set1 = uf.find(edges[cheapest[i]].src)

let set2 = uf.find(edges[cheapest[i]].des)

if set1 == set2

continue

result[edges[cheapest[i]].src] = edges[cheapest[i]].des

uf.union(set1,set2)

numTree = numTree - 1

end

end

return result

時(shí)間復(fù)雜度:O(Elog2V)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

單源最短路徑(Single-Source-Shortest-Paths)

給出一張連通、有向圖，找出一個(gè)頂點(diǎn)s到其他所有頂點(diǎn)的最短路徑?？梢钥吹?，如果圖中存在負(fù)環(huán)，不存在最短路徑。因?yàn)榇嬖谪?fù)環(huán)就可以無(wú)限循環(huán)負(fù)環(huán)得到更短的路徑。

看通用的算法之前，同樣要討論一下問(wèn)題的性質(zhì)。

假設(shè)，存在一條頂點(diǎn)s到頂點(diǎn)v的最短路徑，i、j為路徑上的兩個(gè)頂點(diǎn)。那么在這條s到v最短路徑上，i到j(luò)的路徑是否是i到j(luò)的最短路徑？是的，如果存在i到j(luò)的更短路徑，就等價(jià)于存在一條s到v的更短路徑，這與假設(shè)不符。也就是說(shuō)，如果存在一條從s到v的最短路徑，這條路徑上任意兩個(gè)頂點(diǎn)的路徑都是這兩個(gè)頂點(diǎn)的最短路徑。那么，這個(gè)問(wèn)題就具有動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移特征。

解決此問(wèn)題的樸素想法就是求出所有頂點(diǎn)s到頂點(diǎn)v的路徑，然后取最小值。那么要是實(shí)現(xiàn)這個(gè)步驟，就要為v點(diǎn)存儲(chǔ)一個(gè)估計(jì)值d，并設(shè)起始為無(wú)窮，如果有到達(dá)v的路徑小于這個(gè)估計(jì)值，更新這個(gè)估計(jì)值，并且記錄v的現(xiàn)階段最小路徑。這步操作叫做松弛操作(relax)。假設(shè)u為小于估計(jì)值路徑上的上個(gè)頂點(diǎn)。

RELAX(u,v,result)

if v.d > u.d + u->v

v.d = u.d + u->v

result[v] = u

那么，算法要做的就是一直松弛到達(dá)v頂點(diǎn)的路徑，從無(wú)窮直到最小路徑?？梢钥吹剑械那笞疃搪窂降乃惴ǘ家谶@個(gè)操作去求解，不同的算法只能就是執(zhí)行這個(gè)操作順序不同或者次數(shù)不同。那么松弛操作會(huì)不會(huì)出問(wèn)題，會(huì)不會(huì)松弛操作做過(guò)頭了，將v的估計(jì)值松弛的比最短路徑還?。坎粫?huì)，在算法運(yùn)行期間，對(duì)于所有頂點(diǎn)，一直對(duì)頂點(diǎn)進(jìn)行松弛操作，頂點(diǎn)的預(yù)估值不會(huì)低于最短路徑。以下用結(jié)構(gòu)證明法證明。

假設(shè)：u代表任意一個(gè)連接v的頂點(diǎn)，s->v代表s到v的邊，s~>v代表s到v的最短路徑。

命題：對(duì)到達(dá)v的所有路徑松弛操作有v.d >= s~>v

證明：

對(duì)于v=s的情況，v.d=0 s~v即s~s也為0，命題得證

假設(shè)對(duì)于頂點(diǎn)u，u.d >= s~>u成立。

有s~>v <= s~>u + u->v，因?yàn)閟~>v是一條最短路徑，對(duì)于任意一條經(jīng)過(guò)u到達(dá)v的路徑，必小于最短路徑。

s~>v <= u.d + u->v

因?yàn)榻?jīng)過(guò)松弛操作v.d = u.d + u->v，所以v.d >= s~>v，命題得證。

松弛操作只能同時(shí)對(duì)一條邊起作用。所以，最短路徑長(zhǎng)為n的路徑，只能從最短路徑長(zhǎng)為n-1的路徑，轉(zhuǎn)移過(guò)來(lái)。這里就得到了這個(gè)問(wèn)題最重要的性質(zhì)，單源最短路徑問(wèn)題是個(gè)最短路徑每次遞增一的動(dòng)態(tài)規(guī)劃問(wèn)題。

單源最短路徑性質(zhì)：此問(wèn)題是個(gè)最短路徑每次長(zhǎng)度遞增一的動(dòng)態(tài)規(guī)劃問(wèn)題。

在介紹通用算法之前，先介紹一種專對(duì)于有向無(wú)環(huán)圖很巧的算法。

有向無(wú)環(huán)圖單源最短路徑(DAG-Shortest-Paths)

對(duì)于有向無(wú)環(huán)圖，可以先對(duì)圖進(jìn)行拓?fù)渑判颍缓蟀赐負(fù)渑判虻捻樞驅(qū)γ總€(gè)頂點(diǎn)作為出度的邊進(jìn)行松弛操作，就得到了問(wèn)題的一個(gè)解。以下證明算法的正確性。

假設(shè)v為對(duì)圖拓?fù)渑判蚝蟮哪硞€(gè)頂點(diǎn)。當(dāng)對(duì)v作為出度的邊進(jìn)行松弛操作前，所有能到達(dá)v的路徑都已經(jīng)做過(guò)了松弛操作，此時(shí)已經(jīng)找到了到達(dá)v的最短路徑。那么，當(dāng)對(duì)所有頂點(diǎn)作為出度的邊進(jìn)行松弛操作后，所有頂點(diǎn)的最短路徑就已經(jīng)被找到。算法的正確性得到證明。

偽代碼：

DAG-SHORTEST-PATHS(g)

let sorted = TOPOLOGICAL-SORTING-GREEDY(g)

let result be new Array

for u equal to every vertex in sorted

for v equal to every vertex adjacent to u

if v.d > u.d + u->v

RELAX(u,v,result)

end

end

return result

時(shí)間復(fù)雜度:Θ(V+E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

接下來(lái)介紹兩種通用的算法Bellman-Ford和Dijkstra。Bellman-Ford和Dijkstra有什么聯(lián)系呢？Bellman-Ford可以解決有負(fù)權(quán)重圖的單源最短路徑問(wèn)題，并且可以偵測(cè)出圖中是否存在負(fù)環(huán)。Dijkstra只能解決沒(méi)有負(fù)權(quán)重邊的圖的單源最短路徑問(wèn)題。Bellman-Ford是進(jìn)行必須的最少次數(shù)的松弛操作。而Dijkstra發(fā)現(xiàn)，只要沒(méi)有負(fù)權(quán)重邊，還能進(jìn)行更少的松弛操作解決問(wèn)題。

Bellman-Ford

Bellman-Ford是最通用的解決單源最短路徑算法，初始將所有頂點(diǎn)估計(jì)值設(shè)為無(wú)窮，將源點(diǎn)設(shè)為零。然后，對(duì)所有邊進(jìn)行松弛操作，這個(gè)步驟作為內(nèi)部循環(huán)。再將這個(gè)步驟做圖的頂點(diǎn)個(gè)數(shù)減一次。

Bellman-Ford的正確性不難證明，可以看到隨著B(niǎo)ellman-Ford算法內(nèi)部的循環(huán)，Bellman-Ford找到的最短路徑的長(zhǎng)度也在增加。首先證明內(nèi)部循環(huán)在循環(huán)到第n次時(shí)，找到了所有最短路徑長(zhǎng)為n的路徑。我們用結(jié)構(gòu)證明法。在以下證明中，可以看出Bellman-Ford雖然不是經(jīng)典的動(dòng)態(tài)規(guī)劃算法，但是其原理是基于這個(gè)問(wèn)題的動(dòng)態(tài)規(guī)劃性質(zhì)的。

證明：

對(duì)于n=0時(shí)，最短路徑為0，命題得證。

假設(shè)所有最短路徑為n-1的路徑已經(jīng)被找到。因?yàn)楦鶕?jù)單源最短路徑的動(dòng)態(tài)規(guī)劃性質(zhì)，最短路徑長(zhǎng)為n的路徑，可以從最短路徑長(zhǎng)為n-1的路徑，轉(zhuǎn)移過(guò)來(lái)的。因?yàn)锽ellman-Ford算法會(huì)對(duì)所有的邊進(jìn)行松弛操作。所以，所有長(zhǎng)為n的最短路徑會(huì)從相應(yīng)的長(zhǎng)為n-1的最短路徑找到。命題得證。

只要最短路徑上不存在負(fù)環(huán)，那么所有最短路徑就必小于V-1。所以，Bellman-Ford內(nèi)部循環(huán)執(zhí)行V-1次，能找到最長(zhǎng)的最短路徑，也就是能找到所有的最短路徑。Bellman-Ford正確性證畢。

Bellman-Ford實(shí)現(xiàn)也很簡(jiǎn)單，這里添加一個(gè)flag位，提前省去不必要的循環(huán)。

偽代碼：

BELLMAN-FORD(g,s)

let edges be all the edge of g

let result be new Array

for i from 1 to the number of vertex of g

result[i] = INT_MAX

end

result[s] = 0

for i from 1 to the number of vertex of g minus 1

let flag = false

for j from 1 to the numnber of edge of g

let edge = edges[j]

if result[edge.src] != INT_MAX and edge.src > edge.des + edge.weight

RELAX(u,v,result)

flag = true

end

if flag == false

break

end

return result

時(shí)間復(fù)雜度:O(V?E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

為什么Bellman-Ford算法可以偵測(cè)出有負(fù)環(huán)？算法完成后再對(duì)圖的所有邊進(jìn)行一次松弛操作，如果最短路徑求得的值改變了，就是出現(xiàn)了負(fù)環(huán)。這個(gè)證明看一下松弛操作的定義就行了。根據(jù)松弛操作的性質(zhì)，頂點(diǎn)的估計(jì)在等于最短路徑后不會(huì)再改變了，如果改變了就是出現(xiàn)了負(fù)環(huán)，從而沒(méi)有得到最短路徑。

Dijkstra

Dijkstra是個(gè)貪心算法，樸素的想一下，用貪心算法怎么解決問(wèn)題。既然沒(méi)有負(fù)權(quán)邊，選出當(dāng)前階段最短的路徑，這個(gè)路徑就應(yīng)該是到達(dá)這個(gè)路徑終點(diǎn)的最短路徑。

Dijkstra就是這樣一個(gè)貪心算法，初始將所有頂點(diǎn)估計(jì)值設(shè)為無(wú)窮，將源點(diǎn)設(shè)為零。維護(hù)一個(gè)集合S代表已經(jīng)找到的最短路徑頂點(diǎn)，然后從集合S外所有頂點(diǎn)，選擇有最小的估計(jì)值的頂點(diǎn)加入到集合中，然后再對(duì)這個(gè)頂點(diǎn)在S中的臨接頂點(diǎn)做松弛操作，一直到所有頂點(diǎn)都在集合S中。

Dijkstra的貪心選擇使用簡(jiǎn)單的反證法就可以證出。

假設(shè)，現(xiàn)階段要選從s到某個(gè)頂點(diǎn)u的路徑作為最短路徑加入到集合S中，并且這個(gè)選擇是錯(cuò)誤的。有另一條最短路徑從s到達(dá)u，那么這條路徑和原選擇的路徑肯定不一致，經(jīng)過(guò)不同的頂點(diǎn)，假設(shè)這條最短路徑上到達(dá)u的前一個(gè)頂點(diǎn)為k，既然這是一條從s到達(dá)u的最短路徑，那么從s到k肯定比從s到v小，那么算法會(huì)先選擇從s到k，然后選擇最短路徑，不會(huì)選擇假設(shè)的路徑，這與假設(shè)矛盾，假設(shè)不成立，貪心選擇正確性得證。

以下是算法導(dǎo)論上的證明，嘗試從實(shí)際發(fā)生了什么去證明正確性，我認(rèn)為有點(diǎn)clumsy(笨重)，核心的想法其實(shí)和上面簡(jiǎn)單的反證法一致。

命題：選擇有最小估計(jì)值的頂點(diǎn)加入集合S，那么這個(gè)估計(jì)值必定是這個(gè)頂點(diǎn)的最小路徑。

同樣使用反證法來(lái)證，并且關(guān)注已經(jīng)選擇了最小預(yù)估值的頂點(diǎn)但還沒(méi)加入頂點(diǎn)S時(shí)的情形。

假如選擇了頂點(diǎn)u，這時(shí)，將從s到u作為最小條路徑加入到S中，分為兩種情況。情況一，選擇的從s到u的路徑就是最短路徑，那么命題已經(jīng)得證。情況二，選擇的從s到u的路徑不是最短路徑，存在u.d>s~>u。這種情況下，可以找到一個(gè)頂點(diǎn)x，使得x在集合S中，并在對(duì)x進(jìn)行松弛操作后，找到另一個(gè)頂點(diǎn)y，使得y不在集合中且y的估計(jì)值就等于s到y(tǒng)的最短路徑即s~>y。x可以與s重合，y可以與u重合。

那么有y.d = s~>y

因?yàn)閺膕到y(tǒng)是從s到u的子路徑，有s~>u >= s~>y

得出s~>u >= y.d

因?yàn)檫x擇了頂點(diǎn)u，有u.d <= y.d

得出s~>u >= u.d

這與假設(shè)矛盾，所以假設(shè)不成立，命題得證。

實(shí)現(xiàn)和時(shí)間復(fù)雜度與Prim算法類似，集合S用最小堆實(shí)現(xiàn)。

偽代碼：

DIJKSTRA(g,s)

let heap be new MinHeap

let result be new Array

for i from 1 to the number of vertex in g

let vertex be new Vertex(i)

vertex.d = INT_MAX

heap.insert(vertex)

end

heap.decrease(s,0)

while heap.empty() == false

vertex u = heap.top()

for v equal to every vertex adjacent to u

if heap.isNotInHeap(v) and u.d v.d > u.d + u->v

RELAX(u,v,result)

heap.decrease(v,v.d)

end

end

return result

V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)，對(duì)V個(gè)頂點(diǎn)和E條邊進(jìn)行decrease操作

時(shí)間復(fù)雜度:O(Elog2V+Vlog2V)

可以看到，如果運(yùn)氣好，Bellman-Ford不需要V次循環(huán)就可以找到所有最短路徑，但是運(yùn)氣不好，Bellman-Ford要經(jīng)過(guò)最少V次循環(huán)，這就是上文說(shuō)到的，Bellman-Ford是進(jìn)行必須的最少次數(shù)的松弛操作。而如果不存在負(fù)權(quán)重邊，Dijkstra可以進(jìn)行更少次的松弛操作，至多對(duì)每個(gè)頂點(diǎn)連接的邊進(jìn)行一次松弛操作就可以了，Bellman-Ford與Dijkstra的聯(lián)系實(shí)際上就是動(dòng)態(tài)規(guī)劃與貪心算法的聯(lián)系。Bellman-Ford和Dijkstra算法本質(zhì)都是單源最短路徑性質(zhì)。

全對(duì)最短路徑(All-Pair-Shortest-Paths)

全對(duì)最短路徑就是將圖中任意兩點(diǎn)之間的最短路徑求出來(lái)，輸出一個(gè)矩陣，每個(gè)元素代表橫坐標(biāo)作為標(biāo)號(hào)的頂點(diǎn)到縱坐標(biāo)作為標(biāo)號(hào)的頂點(diǎn)的最短路徑。當(dāng)然，可以對(duì)所有頂點(diǎn)運(yùn)行一次Bellman-Ford算法得出結(jié)果，不過(guò)這樣的復(fù)雜度就太高了。嘗試去找到更好的算法解決這個(gè)問(wèn)題。

既然單源最短路徑是個(gè)最短路徑遞增一的動(dòng)態(tài)規(guī)劃問(wèn)題，嘗試對(duì)全對(duì)最短路徑使用這種性質(zhì)，然后看看能不能降低復(fù)雜度。

假設(shè)有n個(gè)頂點(diǎn)，dpij代表從頂點(diǎn)i到頂點(diǎn)j的最短路徑，假設(shè)這條最短路徑長(zhǎng)為m，且k為任意頂點(diǎn)。那么，根據(jù)這個(gè)問(wèn)題的動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移特征，dpij是由長(zhǎng)度為m?1的dpik加上k->j轉(zhuǎn)移過(guò)來(lái)的。

看來(lái)即使在單源最短路徑動(dòng)態(tài)規(guī)劃的性質(zhì)上進(jìn)行求解，復(fù)雜度仍然很高。

嘗試不從最短路徑長(zhǎng)度角度考慮動(dòng)態(tài)規(guī)劃，從頂點(diǎn)角度去考慮動(dòng)態(tài)規(guī)劃，引出一個(gè)通用的算法Floyd-Warshall。

Floyd-Warshall

好，從頂點(diǎn)的角度去思考動(dòng)態(tài)規(guī)劃。從頂點(diǎn)i到頂點(diǎn)j要經(jīng)過(guò)其他頂點(diǎn)，假設(shè)經(jīng)過(guò)的頂點(diǎn)為k。然后根據(jù)解動(dòng)態(tài)規(guī)劃的經(jīng)驗(yàn)，猜想dpij與dpik和dpkj怎么能沾到邊？假設(shè)從i到j(luò)只需要經(jīng)過(guò)[1,k]集合中的頂點(diǎn)。如果從i到j(luò)經(jīng)過(guò)k，那么dpik就代表從i到k的最短路徑，dpkj就代表從k到j(luò)的最短路徑，dpij就等于從dpik和dpkj轉(zhuǎn)移過(guò)去，而dpik和dpkj都不經(jīng)過(guò)k，都只需要經(jīng)過(guò)[1,k-1]集合中的頂點(diǎn)。如果從i到j(luò)不經(jīng)過(guò)k，dpij就等于從i到j(luò)只需要經(jīng)過(guò)[i,k-1]集合中的頂點(diǎn)時(shí)的dpij。

偽代碼：

FLYOD-WARSHALL(g)

let dp be new Table

for i from 1 to the number of vertex in g

for j from 1 to the number of vertex in g

dp[i][j] = g[i][j]

end

end

for k from 1 to the number of vertex in g

for i from 1 to the number of vertex in g

for j from 1 to the number of vertex in g

if dp[i][k] + dp[k][j] < dp[i][j]

dp[i][j] = dp[i][k] + dp[k][j]

end

end

end

return dp

時(shí)間復(fù)雜度:Θ(V3)，$V$表示頂點(diǎn)的個(gè)數(shù)

Johnson

對(duì)于稀疏圖的話，還有辦法降低算法復(fù)雜度。直觀上看，對(duì)于稀疏圖，對(duì)每個(gè)頂點(diǎn)運(yùn)行Dijkstra算法是快過(guò)Floyd-Warshall算法的，但是這樣要求圖中不能有負(fù)權(quán)邊。那么，可不可以將有負(fù)權(quán)邊的圖轉(zhuǎn)化為沒(méi)有負(fù)權(quán)邊的圖。Johnson就是這樣一個(gè)算法，將所有的邊進(jìn)行重新賦權(quán)重(reweight)，然后再對(duì)所有頂點(diǎn)運(yùn)行Dijkstra算法。那怎么進(jìn)行重新賦權(quán)重呢？樸素想法是找出所有的邊中最小的值，然后所有邊增加這個(gè)值。很可惜，這樣不行?？紤]這樣一個(gè)情況，頂點(diǎn)a到b的最短路徑有3條邊，最短路徑為4。有a到b另一條路徑只經(jīng)過(guò)一條邊，路徑權(quán)重為5。如果對(duì)所有邊增加1權(quán)重，那么頂點(diǎn)a到頂點(diǎn)b的最短路徑就改變了。重新賦權(quán)重改變了最短路徑是明顯有問(wèn)題的。

可以看出重新賦權(quán)重有兩點(diǎn)要求：

1.對(duì)起點(diǎn)和終點(diǎn)相同的路徑改變同樣的權(quán)重，保持原來(lái)的最短路徑結(jié)果。

2.所有邊重新賦權(quán)以后不存在負(fù)權(quán)邊。

Johnson算法先對(duì)頂點(diǎn)重新賦值，然后將邊的重新賦值由兩端頂點(diǎn)的重新賦的值得出。假設(shè)u和v為相鄰的兩個(gè)頂點(diǎn)。

這樣定義w’()函數(shù)以后，對(duì)路徑重新賦的值影響的只有起點(diǎn)和終點(diǎn)兩個(gè)頂點(diǎn)，中間頂點(diǎn)重賦的值都被消掉了。等價(jià)于保持原來(lái)的最短路徑結(jié)果。那么，怎么保證第二點(diǎn)？Johnson算法會(huì)為圖增加一個(gè)頂點(diǎn)s，然后對(duì)圖運(yùn)行一次Bellman-Ford算法。得出新增的頂點(diǎn)s與所有原頂點(diǎn)的最短路徑，這個(gè)最短路徑就是h()數(shù)的值。

而且在運(yùn)行Bellman-Ford算法的時(shí)候，正好可以偵測(cè)出圖中是否有負(fù)環(huán)。

偽代碼：

JOHNSON(g)

let s be new Vertex

g.insert(s)

if BELLMAN-FORD(g,s) == flase

there is a negative cycle in graph

else

for v equal to every vertex in g

h(v) = min(v~>s)

end

for (u,v) equal to every edge in graph

w’(u,v) = w(u,v) + h(u) - h(v)

end

let result be new Table

for u equal to every vertex in g

DIJSKTRA(g,u)

for v equal to every vertex in g

result[u][v] = min(u~>v) + h(v) - h(u)

end

end

return result

時(shí)間復(fù)雜度:O(V?Elog2V+V2log2V+V?E)，V表示頂點(diǎn)的個(gè)數(shù)，E表示邊的個(gè)數(shù)

證明了這么多的算法正確性，可以看到，證明是有技巧的，常用的只有三個(gè)方法，反證法、結(jié)構(gòu)歸納法、Cut-And-Paste法。

經(jīng)過(guò)圖論的探討，便可以理解算法與數(shù)學(xué)之間緊密的聯(lián)系。解決問(wèn)題要對(duì)問(wèn)題本身的特征、屬性進(jìn)行總結(jié)或者提煉。有時(shí)要對(duì)問(wèn)題進(jìn)行相應(yīng)的轉(zhuǎn)化。然后根據(jù)問(wèn)題的特征、性質(zhì)推導(dǎo)出定理。再將定理拓展，提出推論