圖的表示
圖的記號是G = (V, E), 可以用兩種數(shù)據(jù)結構表示: 鄰接鏈表和鄰接矩陣;
- note: 實際應用中一般必須是用一個Vertex V[VNUM]一維數(shù)組來存放結點, 用一個二維矩陣w[VNUM][VNUM]或者鄰接鏈表來存放權重值;
鄰接鏈表
- 構成: |V|條鏈表構成的數(shù)組Adj, 其中某個結點的鏈表是Adj[u];
- 存儲空間: 有|V|條鏈表占據(jù)Θ(V), 這些鏈表的結點加起來總共要有|E| 條 或者 |2E| 個結點, 那么是Θ(E), 所以合起來就是Θ(V+E);
- 優(yōu)點: 鄰接鏈表比較緊湊節(jié)省空間, 適合稀疏圖(E遠小于V^2), 因此多數(shù)算法都假設圖是用鄰接鏈表來表示的.
- 缺點: 無法快速判斷u, v兩個結點之間是否有邊(u, v), 只能在Adj[u]中搜索一下鏈表;
鄰接矩陣
- 構成: |V| × |V| 矩陣來表示兩兩結點之間的邊的情況;
- 存儲空間: Θ(V^2)
- 優(yōu)點: 在稠密圖(E接近V^2)情況下, 鄰接矩陣更好; 鄰接矩陣能滿足快速判斷任意兩個節(jié)點之間是否有邊的需求;
- 缺點:更大的存儲空間消, 高了一個階;
廣度優(yōu)先搜索(BFS)
算法
BFS(G, s)
/*初始化*/
for each vertex u ∈ G.V - {s}
u.color = white;
u.pr = null;
u.d = ∞;
s.color = gray;
s.pr = null;
s.d = 0;
Q = ?; //Queue is empty;
Enqueue(Q, s);
/*搜索*/
while (Q != ?)
u = Dequeue(Q); //take u off from queue head;
for each v of G.Adj[u]
if (v.color == white)
v.color = gray;
v.pr = u;
v.d = u.d+1;
Enqueue(Q, v); //push v into the queue tail;
u.color = black; //u's job is done;
- 算法運行時間分析:
- 初始化階段: Θ(V);
- while循環(huán)里, 每個節(jié)點都要出隊一次, 且每個節(jié)點都要對其的邊進行一番探測, 那么對有向圖來說, 也就是V個節(jié)點, 探測總共E個邊, 耗時Θ(V+E);
BFS性質: 其算法能夠正確計算出任意結點的最短路徑距離δ
(1) 最短路徑距離性質: 對于邊(u, v)∈E, 有δ(s, v) ≤ δ(s, u)+1;
證明: 如果s能夠到達u, 也能到達v, 且存在邊(u, v), 則從s到v的最短路徑距離不可能比s到u的最短路徑加上邊還要長; 若s無法到達u, 則δ(s, u)=∞, 那么性質也成立;
接下去, 為了證明BFS算出的v.d = δ(s, v), 我們先證v.d≥, 再證≤;
(2) BFS算出的v.d ≥ δ(s, v);
證明: (數(shù)學歸納法, 對全過程進行觀察)
① 初始化時: for s, s.d = δ(s,s) = 0; for each v∈G.V - {s}, v.d = ∞ >= δ(s, v);
② 在BFS運算時: assume u has u.d >= δ(s, u).
when u just does its dequeue, then we see that for edge(u, v), the BFS algorithm says
v.d = u.d+1 ≥ δ(s, u)+1 [this is our assumption] ≥ δ(s, v) [cuz edge(u,v)exists, and we have property (1)].
And after this operation, node v's color turns gray and v.d no longer changes.
Thus we prove our property(2).
(3) BFS中隊列里, 隊列中最多包含兩個不同的d值, 且隊中d值保持升序( v[i].d<=v[i+1].d);
證明: (數(shù)學歸納法)
--頭部條件:
當只有s在隊中時, 只有s.d = 0, 定理滿足;
當s離隊后, 往隊中添加結點的階段, 添加進的所有s.adj結點都有v.d = 1, 定理也滿足, 即v[1]離隊前滿足了v[r].d=v[1].d=1 <= v[1].d+1 和 v[i].d = v[i+1].d = 1 <=v[i+1].d;
原v[1]離隊后, 往隊中添加新結點的階段, 添加進的結點都滿足v.d = 原v[1].d +1 = 2 <= v[2].d+1, 我們把原先的v[2]看成新v[1], 即顯然仍有v[r].d<=新v[1].d+1成立; 且我們知道現(xiàn)在v[1]~v[k]有d = 1, v[k+1]~v[r]有d = 2, 所以必有v[i].d <= v[i+1].d;
--歸納階段:
假設當u離隊前, 定理是滿足的, 把u記作v[1], 即v[r].d <= v[1].d+1成立; 同時假設v[i].d <= v[i+1].d也成立, 那么就有v[1].d <= v[2].d;
當u出隊, 往隊中添加元素的時候, 每個新加入的結點都有v.d = u.d+1 <= 原v[2].d+1, 把原v[2]記成新的v[1], 那么也就是說v[r].d <= v[1]+1仍然成立;
再看第二個假設, 對隊列中原先部分, 繼續(xù)成立; 對隊列中原先和新加部分交界處, 已知原v[r].d <= 原v[1].d + 1<= 原v[2]+1, 現(xiàn)在新加入的v=u+1=原v[1].d+1>=原v[r].d, 因此交接部分也有v[i]<=v[i+1]成立; 而對新加部分內, 則有v[i] = v[i+1], 仍然是符合v[i]<=v[i+1];
綜上, 初始條件和歸納階段都成立, 因此定理成立;
(4) BFS求出的v.d = δ(s, v)
已知所有v∈V都是s通過BFS算法發(fā)現(xiàn)的結點, 即s能到達所有的v;
證明: (反證法)
假設存在v.d != δ(s, v), 由v.d>=δ(s,v)定理, 得v.d>δ(s,v);
那么這樣的存在會有兩種情況: 要么圖中存在一部分結點的v.d>δ(s,v), 要么圖中所有結點都有v.d>δ(s,v).
--后者顯然不可能, 因為至少邊(s->a)能使得a結點滿足a.d = δ(s, a);
--看前者情況, 在s出發(fā)的一條路徑上, u之前的結點正常, 而從v開始往后的結點都出現(xiàn)了v.d>δ(s,v), 那唯一的可能就是因為結點v被另外一個更短的路徑給連接了, 此時其實是意味著BFS算法更長的路徑推進得比最短路徑還快了兩個身位, 注意他們的頭都是灰色的, 這與隊列d值只能同時保持兩個是矛盾的.
----也可以這么證: 在s到v的最短路徑上, 前一個結點為x, 那么x.d = δ(s, x), 且δ(s, v) = δ(s, x)+1(已經(jīng)明確說了這就是最短路徑), 已知v.d > δ(s, v) = δ(s, x)+1 = x.d+1, 這也就是我們上述所言的v被更長的路徑首先探索到的問題. 讓我們從x探索的角度看下為什么這不可能:
若在x探索到v時, v是白色, 那么v.d = x.d +1, 矛盾;
若v是黑色, 而此時x還是灰色, 也就是說v比x還先要出隊, 那么v.d <= x.d, 矛盾;
若v是灰色, 那么v肯定被某結點u已經(jīng)先探索了, 則u比x先進了隊列, 滿足u.d <= x.d, 那么v.d = u.d+1 <= x.d+1, 矛盾;
綜上, 在BSF算法能探測到的每個結點v, v.d = δ(s, v)必定成立;
深度優(yōu)先搜索
DFS(G) {
/*初始化*/
for each vertex u in G.V
u.color = white
u.pr = null;
time = 0 //init time;
for each vertex u in G.V
if (u.color == white)
DFS-Visit(G, u);
}
DFS-Visit(G, u) {
time = time+1;
u.d = time;
u.color = gray;
for each v of G.Adj[u]
if v.color == white
v.pr = u
DFS-Visit(G, v);
u.color = black;
time = time+1;
u.f = time;
}
- 算法運行時間分析:
- 初始化每個結點: Θ(V);
- 每個結點都會有入隊和出隊操作, Θ(V); 所有的vertex都將其邊探索到底, 導致所有的Edge都被檢查, Θ(E);
- 合計Θ(V+E);
DFS的重要性質
- 括號化: 對兩個結點u, v來說, 只有三種可能性: 區(qū)間分離, 區(qū)間u包含v, 區(qū)間v包含u;
- 白色路徑: v是u的后代 ? 在發(fā)現(xiàn)u的時候u.d, 能存在一條結點u到v的全部由白色結點所構成的路徑;
- 邊的分類: 當?shù)谝淮翁剿鞯竭?u, v)時, v為白->樹邊; v為灰->后向邊; v為黑->前向邊或者橫向邊;
拓撲排序
Topological-sort(G)
count finish time for each vertex using DFS(G);
once a vertex is finished (marked black), insert it into the linkedList;
return the linkedList
- 拓撲序定義: 若圖G包含邊(u, v), 則u結點在序中總是在v結點前面;
- 該定義直接推導出: 圖G若能生成拓撲序, 必須是有向無環(huán)圖;
證明: (反證法) 如果是有環(huán), 則有u->v, 也有v->u, 那么拓撲序中不可能既滿足u結點在v前面, 又滿足v結點在u前面, 形成矛盾;
- TS算法正確性: 對有向無環(huán)圖, TS算法能生成拓撲排序;
證明: 因為我們算法第二行使得返回序列是按照結束時間f的逆序排列(前大后小), 因此只要證明若邊(u, v)存在于G圖中, 則總有u.f>v.f成立就可以;
(分類討論)利用DFS性質中邊的分類, 對任意一條存在于G中的邊(u, v)進行討論, 若該邊在DFS中被探索到時,
(1) 若v結點是灰色, 則是后向邊, 與給定的有向無環(huán)圖條件矛盾(后向邊會形成環(huán)), 因此不可能存在;
(2) 若v結點是白色, 則這是樹邊, 由白色路徑定理, v是u的子結點, 再由括號化定理, 知道u.f > v.f, 命題成立;
(3) 若v結點是黑色, 則這是前向邊或者橫向邊, 此時v結點已經(jīng)被打上時間戳, 而u尚未結束, 那么u.f>v.f成立, 命題也成立;
所以, 只要前提條件 有向無環(huán)圖成立, TS算法總能生成拓撲序;
強連通分量(Strongly connected components)
Strongly-connected-components(G)
1. call DFS(G) to compute finish time for each vertex in the graph;
2. compute G<t> (reverse the direction of all edges);
3. call DFS(G<t>), but from latest finish time to earliest at the main loop;
4. the trees that formed by second DF, are the components we look for;
正確性證明:
(1) C和C', 假如有u->u', 不可能有v'->v, 因為如果能夠實現(xiàn)的話, 那么這兩個分量任意元素都能實現(xiàn)互相到達對方, 那么C和C'可以合為一個分量;
(2) C和C', 如果有u->u', 那么f(C')<f(C); 而對G<T>, 則是f(C)<f(C');
證明: (分類討論)如果若DFS從C的x節(jié)點開始, 那么最后就是x.f > max{Cnodes.f }, 則f(C)>f(C');
如果DFS從C'的y節(jié)點先開始, 那么就是先visit完C'的結點, 且C'無法到達C, 之后DFS再對C開始運算, 那么就得到f(C)>f(C');
對于G<T>, 同理成立;
(3) SCC算法能夠得到G<SCC>
證明: 可以把各個求出的分量看做n個結點, 如果算法第三行對G<t>進行DFS運算能夠形成n個獨立的樹夠成的一片森林的話, 那么算法就是正確的.
數(shù)學歸納法:
算法第三行的操作是, 按照拓撲序(C.f > C'.f, 則C在前)來對n個結點進行DFS, 注意這里G中的所有邊都已經(jīng)被反向過;
a. 當n=1時, 顯然森林只有一棵樹, 命題成立;
b. 假設當n>1時, 一般地, 對拓撲序中的C和C'來說, 那么如果先對C進行DFS, 由于C沒有邊能到拓撲序的下一個結點C'(在G中C->C', 但是已經(jīng)邊被反向了), 所以C單獨成了一棵樹, DFS在C的運算不會對C'有任何操作. 以此類推, 算法能連續(xù)生成n棵獨立的樹;
