【圖論】

　1、Dijkstra算法
　2、Floyd算法
　3、Kruskal算法
　4、Prim算法
　5、歐拉回路

Dijkstra算法
Dijkstra算法是典型最短路算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。
Dijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。
Dijkstra一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 算法和 D* 算法表述一致，這里均采用OPEN,CLOSE表的方式。

大概過(guò)程：
創(chuàng)建兩個(gè)表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問(wèn)過(guò)的節(jié)點(diǎn)。
1． 訪問(wèn)路網(wǎng)中里起始點(diǎn)最近且沒有被檢查過(guò)的點(diǎn)，把這個(gè)點(diǎn)放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點(diǎn)最近的點(diǎn)，找出這個(gè)點(diǎn)的所有子節(jié)點(diǎn)，把這個(gè)點(diǎn)放到CLOSE表中。
3． 遍歷考察這個(gè)點(diǎn)的子節(jié)點(diǎn)。求出這些子節(jié)點(diǎn)距起始點(diǎn)的距離值，放子節(jié)點(diǎn)到OPEN表中。
4． 重復(fù)2，3，步。直到OPEN表為空，或找到目標(biāo)點(diǎn)。

Floyd算法
Floyd-Warshall 算法用來(lái)找出每對(duì)點(diǎn)之間的最短距離。它需要用鄰接矩陣來(lái)儲(chǔ)存邊，這個(gè)算法通過(guò)考慮最佳子路徑來(lái)得到最佳路徑。

注意單獨(dú)一條邊的路徑也不一定是最佳路徑。

從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，或者無(wú)窮大，如果兩點(diǎn)之間沒有邊相連。
對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。
不可思議的是，只要按排適當(dāng)，就能得到結(jié)果。
// dist(i,j) 為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離
For i←1 to n do
For j←1 to n do
dist(i,j) = weight(i,j)

For k←1 to n do // k為“媒介節(jié)點(diǎn)”
For i←1 to n do
For j←1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路徑？
dist(i,j) = dist(i,k) + dist(k,j)這個(gè)算法的效率是O(V3)。它需要鄰接矩陣來(lái)儲(chǔ)存圖。
這個(gè)算法很容易實(shí)現(xiàn)，只要幾行。
即使問(wèn)題是求單源最短路徑，還是推薦使用這個(gè)算法，如果時(shí)間和空間允許(只要有放的下鄰接矩陣的空間，時(shí)間上就沒問(wèn)題)。
[編輯] 時(shí)間復(fù)雜度 O(N^3)

Kruskal算法
基本思想
假設(shè)WN=(V,{E})是一個(gè)含有n個(gè)頂點(diǎn)的連通網(wǎng)，則按照克魯斯卡爾算法構(gòu)造最小生成樹的過(guò)程為：先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)，而邊集為空的子圖，若將該子圖中各個(gè)頂點(diǎn)看成是各棵樹上的根結(jié)點(diǎn)，則它是一個(gè)含有n棵樹的一個(gè)森林。之后，從網(wǎng)的邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹，則將其加入子圖，也就是說(shuō)，將這兩個(gè)頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有n-1條邊為止。</p>

Procedure kruskal(V,E);
begin
sort(E,1,m);//將邊按照權(quán)值排序
for t:=1 to n do begin
if getfather(edge[t].u)<>getfather(edge[t].v) then begin //利用并查集判斷兩個(gè)頂點(diǎn)是否在同一集合內(nèi)
tot:=tot+edge[t].data;//計(jì)算權(quán)值和
union(edge[t].u,edge[t].v);//合并頂點(diǎn)
inc(k);//合并次數(shù)
end;
end;
if k=n-1 then 形成了一棵最小生成樹
else 不存在這樣的最小生成樹；
end;
優(yōu)化：在判斷兩個(gè)頂點(diǎn)是否在同一集合內(nèi)時(shí)可用并查集 　

Prim算法

基本思想
1. 在圖G=(V, E) （V表示頂點(diǎn) ，E表示邊）中，從集合V中任取一個(gè)頂點(diǎn)（例如取頂點(diǎn)v0）放入集合 U中，這時(shí) U={v0}，集合T(E)為空。
2. 從v0出發(fā)尋找與U中頂點(diǎn)相鄰（另一頂點(diǎn)在V中）權(quán)值最小的邊的另一頂點(diǎn)v1，并使v1加入U(xiǎn)。即U={v0,v1 }，同時(shí)將該邊加入集合T(E)中。
3. 重復(fù)2，直到U=V為止。
這時(shí)T(E)中有n-1條邊，T = (U, T(E))就是一棵最小生成樹。

PASCAL代碼
procedure prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do begin
lowcost[i]:=cost[v0,i];
closest[i]:=v0;
end;
for i:=1 to n-1 do begin
{尋找離生成樹最近的未加入頂點(diǎn)k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]<min) and (lowcost[j]<>0) then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {將頂點(diǎn)k加入生成樹}
{生成樹中增加一條新的邊k到closest[k]}
{修正各點(diǎn)的lowcost和closest值}
for j:=1 to n do
if cost[k,j]<lowcost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}

〖返回頂部〗

歐拉回路
定義：
在一個(gè)圖中，尋找一條只通過(guò)每條邊一次的路徑，這叫做歐拉路徑，如果起點(diǎn)和終點(diǎn)是同一點(diǎn)，那么這條回路叫做歐拉回路．
判定一個(gè)圖中是否存在歐拉回路：并不是每個(gè)圖都存在歐拉回路．以下分三種情況：
無(wú)向圖：每個(gè)點(diǎn)的度數(shù)是偶數(shù)，則存在歐拉回路．
有向圖：每個(gè)結(jié)點(diǎn)的入度等于出度，則這個(gè)有向圖中存在歐拉回路．
總結(jié)：以上兩種情況很簡(jiǎn)單，其原理歸根結(jié)底是每個(gè)結(jié)點(diǎn)進(jìn)入和出去的路徑條數(shù)相等，就存在歐拉回路．還有一種更加復(fù)雜的情況．那就是混合圖．
混合圖：（有時(shí)邊是單向的，有時(shí)邊是無(wú)向的，就像城市交通網(wǎng)絡(luò)，有的街道是單向的，有的街道是雙向的）找一個(gè)給每個(gè)無(wú)向邊定向的策略，這樣就可以把圖轉(zhuǎn)化成為有向圖，使每個(gè)頂點(diǎn)的入度與出度是相等的，這樣就會(huì)存在歐拉回路．
具體過(guò)程如下：新建一個(gè)圖，對(duì)于原圖中的無(wú)向邊，在新圖中新加一個(gè)頂點(diǎn)e(i);對(duì)于原圖中的每一個(gè)頂點(diǎn)j，在新圖中建一個(gè)頂點(diǎn)v(i)，對(duì)于原圖中每一個(gè)頂點(diǎn)j和k之間有一條無(wú)向邊i，那么在新圖中從e(i)出發(fā)，添加兩條邊，分別連向v(j)和v(k)，容量都是1．
在新圖中，從源點(diǎn)向所有的e(i)都連一條容量為1的邊．. 對(duì)于原圖中每一個(gè)頂點(diǎn)j，它原本都有一個(gè)入度in、出度out和無(wú)向度un。顯然我們的目的是要把所有無(wú)向度都變成入度或出度，從而使它的入度等于總度數(shù)的一半，也就是(in + out + un) / 2（顯然與此同時(shí)出度也是總度數(shù)的一半，如果總度數(shù)是偶數(shù)的話）。當(dāng)然，如果in已經(jīng)大于總度數(shù)的一半，或者總度數(shù)是奇數(shù)，那么歐拉回路肯定不存大。如果in小于總度數(shù)的一半，并且總度數(shù)是偶數(shù)，那么我們?cè)谛聢D中從v（j）到匯點(diǎn)連一條邊，容量就是(in + out + un) / 2 – in，也就是原圖中頂點(diǎn)j還需要多少入度。
按照這個(gè)網(wǎng)絡(luò)模型算出一個(gè)最大流，如果每條從v(j)到匯點(diǎn)的邊都達(dá)到滿流量的話，那么歐拉回路成立。

〖返回頂部〗