晚上學(xué)習(xí)了一些圖論相關(guān)算法:

單源最短路徑算法:

Bellman-Ford 算法:

Bellman-Ford 算法是一種用于計(jì)算帶權(quán)有向圖中單源最短路徑（SSSP：Single-Source Shortest Path）的算法。該算法由 Richard Bellman 和 Lester Ford 分別發(fā)表于 1958 年和 1956 年，而實(shí)際上 Edward F. Moore 也在 1957 年發(fā)布了相同的算法，因此，此算法也常被稱為 Bellman-Ford-Moore 算法。

Bellman-Ford 算法和 Dijkstra 算法同為解決單源最短路徑的算法。對(duì)于帶權(quán)有向圖 G = (V, E)，Dijkstra 算法要求圖 G 中邊的權(quán)值均為非負(fù)，而 Bellman-Ford 算法能適應(yīng)一般的情況（即存在負(fù)權(quán)邊的情況）。一個(gè)實(shí)現(xiàn)的很好的 Dijkstra 算法比 Bellman-Ford 算法的運(yùn)行時(shí)間要低。

Bellman-Ford 算法采用動(dòng)態(tài)規(guī)劃（Dynamic Programming）進(jìn)行設(shè)計(jì)，實(shí)現(xiàn)的時(shí)間復(fù)雜度為 O(V*E)，其中 V 為頂點(diǎn)數(shù)量，E 為邊的數(shù)量。Dijkstra 算法采用貪心算法（Greedy Algorithm）范式進(jìn)行設(shè)計(jì)，普通實(shí)現(xiàn)的時(shí)間復(fù)雜度為 O(V2)，若基于 Fibonacci heap 的最小優(yōu)先隊(duì)列實(shí)現(xiàn)版本則時(shí)間復(fù)雜度為 O(E + VlogV)。

Bellman-Ford 算法描述：

創(chuàng)建源頂點(diǎn) v 到圖中所有頂點(diǎn)的距離的集合 distSet，為圖中的所有頂點(diǎn)指定一個(gè)距離值，初始均為 Infinite，源頂點(diǎn)距離為 0；
計(jì)算最短路徑，執(zhí)行 V - 1 次遍歷；
對(duì)于圖中的每條邊：如果起點(diǎn) u 的距離 d 加上邊的權(quán)值 w 小于終點(diǎn) v 的距離 d，則更新終點(diǎn) v 的距離值 d；
檢測(cè)圖中是否有負(fù)權(quán)邊形成了環(huán)，遍歷圖中的所有邊，計(jì)算 u 至 v 的距離，如果對(duì)于 v 存在更小的距離，則說(shuō)明存在環(huán)；

?

代碼:

1 //從頂點(diǎn)from指向頂點(diǎn)to的權(quán)值為cost的邊 2 struct edge{ 3 int from,to,cost; 4 }; 5 6 edge es[MAX_V];//邊 7 8 int d[MAX_V]; //最短距離 9 int V,E; //V是頂點(diǎn)數(shù),E是邊數(shù) 10 11 //求解從頂點(diǎn)s出發(fā)到所有點(diǎn)的最短距離 12 void shortest_path(int s) 13 { 14 for(int i=0; i<V; i++) 15 d[i] = INF; //0x3f3f3f3f 16 d[s]=0; 17 while(true){ 18 bool update=false; 19 for(int i=0; i<E; i++){ 20 edge e=es[i]; 21 if(d[e.from]!=INF && d[e.to] >d[e.from]+e.cost){ 22 uopdate=true; 23 } 24 } 25 if(!update) 26 break; 27 } 28 }

?

?

Dijkstra算法 ?

1.定義概覽?

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。注意該算法要求圖中不存在負(fù)權(quán)邊。

問(wèn)題描述：在無(wú)向圖 G=(V,E) 中，假設(shè)每條邊 E[i] 的長(zhǎng)度為 w[i]，找到由頂點(diǎn) V0 到其余各點(diǎn)的最短路徑。（單源最短路徑）

?

2.算法描述

1)算法思想：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。

2)算法步驟：

a.初始時(shí)，S只包含源點(diǎn)，即S＝{v}，v的距離為0。U包含除v外的其他頂點(diǎn)，即:U={其余頂點(diǎn)}，若v與U中頂點(diǎn)u有邊，則<u,v>正常有權(quán)值，若u不是v的出邊鄰接點(diǎn)，則<u,v>權(quán)值為∞。

b.從U中選取一個(gè)距離v最小的頂點(diǎn)k，把k，加入S中（該選定的距離就是v到k的最短路徑長(zhǎng)度）。

c.以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過(guò)頂點(diǎn)k）比原來(lái)距離（不經(jīng)過(guò)頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。

d.重復(fù)步驟b和c直到所有頂點(diǎn)都包含在S中。

執(zhí)行動(dòng)畫過(guò)程如下圖

STL代碼:

1 struct edge{int to, cost;};//圖的邊 2 typedef pair<int,int> P;//保存的結(jié)果，first為最短距離，second為相應(yīng)頂點(diǎn) 3 4 int V; 5 vector<edge> G[MAX_V]; 6 int d[MAX_V]; 7 8 void dijkstra(int s){ 9 //通過(guò)制定greater<P>參數(shù),堆按照f(shuō)irst從小到大的順序取出值 10 priority_queue<P,vector<P>,greater<P>> que; 11 fill(d,d+V,INF); 12 d[s]=0; 13 que.push(P(0,s)); 14 15 while(!que.empty()){ 16 P p=que.top(); que.pop(); 17 int v=p.second; 18 for(int i=0;i<G[v].size;i++){ 19 edge e=G[v][i]; 20 if(d[e.to]>d[v]+e.cost){ 21 d[e.to]=d[v]+e.cost; 22 que.push(P(d[e.to],e.to)); 23 } 24 } 25 } 26 }

?代碼實(shí)現(xiàn):

1 #define INF 0x3f3f3f3f 2 #define MAX 101 3 4 int dis[MAX],vis[MAX]; 5 int mp[MAX][MAX]; 6 7 int dijkstra(int s,int e) 8 { 9 memset(vis,0,sizeof(vis)); 10 for(int i=1; i<=e; i++) 11 dis[i]=mp[s][i]; 12 dis[s]=0; 13 vis[s]=1; 14 while(true){ 15 int min=INF; 16 int p; 17 for(int i=1; i<=e; i++){ 18 if(!vis[i] && dis[i]<min){ 19 min=dis[i]; 20 p=i; 21 } 22 } 23 if(min==INF) 24 break; 25 vis[p]=1; 26 for(int i=1; i<=e; i++){ 27 if(!vis[i] && dis[i]>min+mp[p][i]) 28 dis[i]=min+mp[p][i]; 29 } 30 } 31 }

?

SPFA:?

是一種求單源最短路的算法

幾乎所有的最短路算法其步驟都可以分為兩步

1.初始化

2.松弛操作

判斷有無(wú)負(fù)環(huán)：

　　如果某個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過(guò)N次則存在負(fù)環(huán)（SPFA無(wú)法處理帶負(fù)環(huán)的圖）

1 int spfa(int s) 2 { 3 queue<int> q; 4 while(!q.empty()) 5 q.pop(); 6 q.push(s); 7 dis[s]=1.0; 8 vis[s]=1; 9 num[s]++; 10 while(!q.empty()){ 11 s=q.front(); 12 q.pop(); 13 vis[s]=0; 14 for(int i=0; i<list[s].size(); i++){ 15 int p=list[s][i]; 16 if(dis[p]<dis[s]*mp[s][p]){ 17 dis[p]=dis[s]*mp[s][p]; 18 if(!vis[p]){ 19 vis[p]=1; 20 q.push(p); 21 num[p]++; 22 if(num[p]==n) 23 return 0; 24 } 25 } 26 } 27 } 28 return 1; 29 }

?

?

1 int spfa_bfs(int s) 2 { 3 queue <int> q; 4 memset(d,0x3f,sizeof(d)); 5 d[s]=0; 6 memset(c,0,sizeof(c)); 7 memset(vis,0,sizeof(vis)); 8 9 q.push(s); vis[s]=1; c[s]=1; 10 //頂點(diǎn)入隊(duì)vis要做標(biāo)記，另外要統(tǒng)計(jì)頂點(diǎn)的入隊(duì)次數(shù) 11 int OK=1; 12 while(!q.empty()) 13 { 14 int x; 15 x=q.front(); q.pop(); vis[x]=0; 16 //隊(duì)頭元素出隊(duì)，并且消除標(biāo)記 17 for(int k=f[x]; k!=0; k=nnext[k]) //遍歷頂點(diǎn)x的鄰接表 18 { 19 int y=v[k]; 20 if( d[x]+w[k] < d[y]) 21 { 22 d[y]=d[x]+w[k]; //松弛 23 if(!vis[y]) //頂點(diǎn)y不在隊(duì)內(nèi) 24 { 25 vis[y]=1; //標(biāo)記 26 c[y]++; //統(tǒng)計(jì)次數(shù) 27 q.push(y); //入隊(duì) 28 if(c[y]>NN) //超過(guò)入隊(duì)次數(shù)上限，說(shuō)明有負(fù)環(huán) 29 return OK=0; 30 } 31 } 32 } 33 } 34 35 return OK; 36 37 }

?

?

求多源、無(wú)負(fù)權(quán)邊的最短路:

Floyd算法

1.定義概覽

Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問(wèn)題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。Floyd-Warshall算法的時(shí)間復(fù)雜度為O(N³)，空間復(fù)雜度為O(N²)。

?

2.算法描述

1)算法思想原理：

?????Floyd算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。用通俗的語(yǔ)言來(lái)描述的話，首先我們的目標(biāo)是尋找從點(diǎn)i到點(diǎn)j的最短路徑。從動(dòng)態(tài)規(guī)劃的角度看問(wèn)題，我們需要為這個(gè)目標(biāo)重新做一個(gè)詮釋（這個(gè)詮釋正是動(dòng)態(tài)規(guī)劃最富創(chuàng)造力的精華所在）

????? 從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能，1是直接從i到j(luò)，2是從i經(jīng)過(guò)若干個(gè)節(jié)點(diǎn)k到j(luò)。所以，我們假設(shè)Dis(i,j)為節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)k，我們檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來(lái)，當(dāng)我們遍歷完所有節(jié)點(diǎn)k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。

2).算法描述：

a.從任意一條單邊路徑開(kāi)始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒(méi)有邊相連，則權(quán)為無(wú)窮大。 　　

b.對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。

3).Floyd算法過(guò)程矩陣的計(jì)算----十字交叉法

?

代碼:

1 int d[MAX_V][MAX_V]; //d[u][v] 表示邊e=(u,v)的權(quán)值(不存在時(shí)設(shè)為INF,不過(guò)d[i][i]=0) 2 int v; 3 4 void warshall_floyd(){ 5 for(int k=0; k<V; k++) 6 for(int i=0; i<V; i++) 7 for(int j=0; j<V; j++) 8 d[i][j]=min(d[i][j],d[i][k]+d[k][j]); 9 }

?

最小生成樹:?

Prim算法

1.概覽

普里姆算法（Prim算法），圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點(diǎn)（英語(yǔ)：Vertex (graph theory)），且其所有邊的權(quán)值之和亦為最小。該算法于1930年由捷克數(shù)學(xué)家沃伊捷赫·亞爾尼克（英語(yǔ)：Vojtěch Jarník）發(fā)現(xiàn)；并在1957年由美國(guó)計(jì)算機(jī)科學(xué)家羅伯特·普里姆（英語(yǔ)：Robert C. Prim）獨(dú)立發(fā)現(xiàn)；1959年，艾茲格·迪科斯徹再次發(fā)現(xiàn)了該算法。因此，在某些場(chǎng)合，普里姆算法又被稱為DJP算法、亞爾尼克算法或普里姆－亞爾尼克算法。

給定一個(gè)無(wú)向圖,如果它的某個(gè)子圖中任意兩個(gè)頂點(diǎn)都互相連通并且是一棵樹,那么這課樹就叫做生成樹(Spanning Tree).如果邊上有權(quán)值,那么是的邊權(quán)和最小的生成樹叫做最小生成樹(MST,Minimum Spanning Tree)?

?

?

2.算法簡(jiǎn)單描述

1).輸入：一個(gè)加權(quán)連通圖，其中頂點(diǎn)集合為V，邊集合為E；

2).初始化：V_new?= {x}，其中x為集合V中的任一節(jié)點(diǎn)（起始點(diǎn)），E_new?= {},為空；

3).重復(fù)下列操作，直到V_new?= V：

a.在集合E中選取權(quán)值最小的邊<u, v>，其中u為集合V_new中的元素，而v不在V_new集合當(dāng)中，并且v∈V（如果存在有多條滿足前述條件即具有相同權(quán)值的邊，則可任意選取其中之一）；

b.將v加入集合V_new中，將<u, v>邊加入集合E_new中；

4).輸出：使用集合V_new和E_new來(lái)描述所得到的最小生成樹。

?

?代碼:

1 void prim() 2 { 3 memset(vis,0,sizeof(vis)); 4 memset(dis,INF,sizeof(dis)); 5 dis[1]=0; 6 ans=0; 7 dis[0]=INF; 8 while(true){ 9 int m=0; 10 for(int i=1; i<=n; i++){ 11 if(!vis[i] && dis[i]<dis[m]) 12 m=i; 13 } 14 if(m==0) 15 break; 16 vis[m]=1; 17 ans+=dis[m]; 18 for(int i=1; i<=n; i++) 19 dis[i]=min(dis[i],mp[m][i]); 20 } 21 }

?

Kruskal算法

?

1.概覽

Kruskal算法是一種用來(lái)尋找最小生成樹的算法，由Joseph Kruskal在1956年發(fā)表。用來(lái)解決同樣問(wèn)題的還有Prim算法和Boruvka算法等。三種算法都是貪婪算法的應(yīng)用。和Boruvka算法不同的地方是，Kruskal算法在圖中存在相同權(quán)值的邊時(shí)也有效。

?

2.算法簡(jiǎn)單描述

1).記Graph中有v個(gè)頂點(diǎn)，e個(gè)邊

2).新建圖Graph_new，Graph_new中擁有原圖中相同的e個(gè)頂點(diǎn)，但沒(méi)有邊

3).將原圖Graph中所有e個(gè)邊按權(quán)值從小到大排序

4).循環(huán)：從權(quán)值最小的邊開(kāi)始遍歷每條邊 直至圖Graph中所有的節(jié)點(diǎn)都在同一個(gè)連通分量中

??????????????? if 這條邊連接的兩個(gè)節(jié)點(diǎn)于圖Graph_new中不在同一個(gè)連通分量中

????????????????????????????????????? ?? 添加這條邊到圖Graph_new中

?

?

1 struct edge{int u,v,cost;}; 2 3 bool cmp(edge &e1,const edge &e2){ 4 return e1.cost < e2.cost; 5 } 6 7 edge es[MAX_E]; 8 int V,E; //頂點(diǎn)數(shù)和邊數(shù) 9 10 int kruskal(){ 11 sort(es,es+E,cmp); //按照edge.cost的順序從小到大排列 12 init_union_find(V); //并查集的初始化 13 int res=0; 14 for(int i=0; i<E; i++){ 15 edge e=es[i]; 16 if(!same(e.u,e.v)){ 17 unite(e.u,e.v); 18 res+=e.cost; 19 } 20 } 21 return res; 22 }

?

?

?

?

?

?

?

?圖論所刷題目的鏈接: ??http://www.cnblogs.com/qscqesze/p/4547000.html

?

?

參考書籍:<<挑戰(zhàn)程序設(shè)計(jì)競(jìng)賽>>

參考博客:http://blog.csdn.net/yutianzuijin/article/details/11618651

? ? ? ? ? ? http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

? ? ? ? ? ? http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

? ? ? ? ? ??http://www.cnblogs.com/scau20110726/archive/2012/11/18/2776124.html

? ? ? ? ? ??http://blog.csdn.net/v_july_v/article/details/6181485

轉(zhuǎn)載于:https://www.cnblogs.com/wangmengmeng/p/5277225.html

總結(jié)

以上是生活随笔為你收集整理的图论相关算法理解和总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。