數據結構–圖(Graph)詳解(四)

文章目錄

• 數據結構--圖(Graph)詳解(四)
• • 一、圖中幾個NB的算法
  • • 1.普里姆算法(Prim算法)求最小生成樹
    • 2.克魯斯卡爾算法(Kruskal算法)求最小生成樹
    • 3.拓撲排序算法
    • 4.迪杰斯特拉(Dijkstra算法)算法
    • 5.弗洛伊德算法

一、圖中幾個NB的算法

1.普里姆算法(Prim算法)求最小生成樹

普里姆算法(Prim算法)求最小生成樹：https://blog.csdn.net/wolfGuiDao/article/details/107588112

該算法從頂點的角度為出發點，時間復雜度為O(n2)，更適合與解決邊的綢密度更高的連通網。

2.克魯斯卡爾算法(Kruskal算法)求最小生成樹

• 克魯斯卡爾算法，從邊的角度求網的最小生成樹，時間復雜度為O(eloge)。和普里姆算法恰恰相反，更適合于求邊稀疏的網的最小生成樹。
• 對于任意一個連通網的最小生成樹來說，在要求總的權值最小的情況下，最直接的想法就是將連通網中的所有邊按照權值大小進行升序排序，從小到大依次選擇。
• 由于最小生成樹本身是一棵生成樹，所以需要時刻滿足以下兩點：
• 生成樹中任意頂點之間有且僅有一條通路，也就是說，生成樹中不能存在回路；
• 對于具有 n 個頂點的連通網，其生成樹中只能有 n-1 條邊，這 n-1 條邊連通著 n 個頂點。
• 連接 n 個頂點在不產生回路的情況下，只需要 n-1 條邊。
• 所以克魯斯卡爾算法的具體思路是：將所有邊按照權值的大小進行升序排序，然后從小到大一一判斷
• 條件為：如果這個邊不會與之前選擇的所有邊組成回路，就可以作為最小生成樹的一部分；反之，舍去。
• 直到具有 n 個頂點的連通網篩選出來 n-1 條邊為止。篩選出來的邊和所有的頂點構成此連通網的最小生成樹。
• 判斷是否會產生回路的方法為：在初始狀態下給每個頂點賦予不同的標記，對于遍歷過程的每條邊，其都有兩個頂點，判斷這兩個頂點的標記是否一致，如果一致，說明它們本身就處在一棵樹中，如果繼續連接就會產生回路；如果不一致，說明它們之間還沒有任何關系，可以連接(也可以使用并查集來判斷)。

假設遍歷到一條由頂點 A 和 B 構成的邊，而頂點 A 和頂點 B 標記不同，此時不僅需要將頂點 A 的標記更新為頂點 B 的標記，還需要更改所有和頂點 A 標記相同的頂點的標記，全部改為頂點 B 的標記。

• 例如，使用克魯斯卡爾算法找圖 1 的最小生成樹的過程為：
• 首先，在初始狀態下，對各頂點賦予不同的標記（用顏色區別），如下圖所示：

• 對所有邊按照權值的大小進行排序，按照從小到大的順序進行判斷，首先是（1，3）
• 由于頂點 1 和頂點 3 標記不同，所以可以構成生成樹的一部分，遍歷所有頂點，將與頂點 3 標記相同的全部更改為頂點 1 的標記，如（2）所示：
  
• 其次是（4，6）邊，兩頂點標記不同，所以可以構成生成樹的一部分，更新所有頂點的標記為：

• 其次是（2，5）邊，兩頂點標記不同，可以構成生成樹的一部分，更新所有頂點的標記為：

• 然后最小的是（3，6）邊，兩者標記不同，可以連接，遍歷所有頂點，將與頂點 6 標記相同的所有頂點的標記更改為頂點 1 的標記：

• 繼續選擇權值最小的邊，此時會發現，權值為 5 的邊有 3 個，其中（1，4）和（3，4）各自兩頂點的標記一樣，如果連接會產生回路，所以舍去
• 而（2，3）標記不一樣，可以選擇，將所有與頂點 2 標記相同的頂點的標記全部改為同頂點 3 相同的標記：
  
• 當選取的邊的數量相比與頂點的數量小 1 時，說明最小生成樹已經生成。所以最終采用克魯斯卡爾算法得到的最小生成樹為（6）所示

#include "stdio.h" #include "stdlib.h" #define MAX_VERtEX_NUM 20 #define VertexType inttypedef struct edge{VertexType initial;VertexType end;VertexType weight; }edge[MAX_VERtEX_NUM];//定義輔助數組 typedef struct {VertexType value;//頂點數據int sign;//每個頂點所屬的集合 }assist[MAX_VERtEX_NUM]; assist assists;//qsort排序函數中使用，使edges結構體中的邊按照權值大小升序排序 int cmp(const void *a,const void*b){return ((struct edge*)a)->weight-((struct edge*)b)->weight; }//初始化連通網 void CreateUDN(edge *edges,int *vexnum,int *arcnum){printf("輸入連通網的邊數：\n");scanf("%d %d",&(*vexnum),&(*arcnum));printf("輸入連通網的頂點：\n");for (int i=0; i<(*vexnum); i++) {scanf("%d",&(assists[i].value));assists[i].sign=i;}printf("輸入各邊的起始點和終點及權重：\n");for (int i=0 ; i<(*arcnum); i++) {scanf("%d,%d,%d",&(*edges)[i].initial,&(*edges)[i].end,&(*edges)[i].weight);} }//在assists數組中找到頂點point對應的位置下標 int Locatevex(int vexnum,int point){for (int i=0; i<vexnum; i++) {if (assists[i].value==point) {return i;}}return -1; }int main(){int arcnum,vexnum;edge edges;CreateUDN(&edges,&vexnum,&arcnum);//對連通網中的所有邊進行升序排序，結果仍保存在edges數組中qsort(edges, arcnum, sizeof(edges[0]), cmp);//創建一個空的結構體數組，用于存放最小生成樹edge minTree;//設置一個用于記錄最小生成樹中邊的數量的常量int num=0;//遍歷所有的邊for (int i=0; i<arcnum; i++) {//找到邊的起始頂點和結束頂點在數組assists中的位置int initial=Locatevex(vexnum, edges[i].initial);int end=Locatevex(vexnum, edges[i].end);//如果頂點位置存在且頂點的標記不同，說明不在一個集合中，不會產生回路if (initial!=-1&& end!=-1&&assists[initial].sign!=assists[end].sign) {//記錄該邊，作為最小生成樹的組成部分minTree[num]=edges[i];//計數+1num++;//將新加入生成樹的頂點標記全不更改為一樣的for (int k=0; k<vexnum; k++) {if (assists[k].sign==assists[end].sign) {assists[k].sign=assists[initial].sign;}}//如果選擇的邊的數量和頂點數相差1，證明最小生成樹已經形成，退出循環if (num==vexnum-1) {break;}}}//輸出語句for (int i=0; i<vexnum-1; i++) {printf("%d,%d\n",minTree[i].initial,minTree[i].end);}return 0; }

3.拓撲排序算法

• 拓撲排序指的是將有向無環圖（又稱“DAG”圖）中的頂點按照圖中指定的先后順序進行排序。
• 在圖論中，由一個有向無環圖的頂點組成的序列，當且僅當滿足下列條件時，稱為該圖的一個拓撲排序
• 每個頂點出現且只出現一次；
• 若存在一條從頂點 A 到頂點 B 的路徑，那么在序列中頂點 A 出現在頂點 B 的前面。

• 例如，圖 1 中的兩個圖都是有向無環圖，都可以使用拓撲排序對圖中的頂點進行排序

• 兩個圖形的區別是：左圖中的 V2 和 V3 之間沒有明確的前后順序；而右圖中任意兩個頂點之間都有前后順序。

• 所以，左圖中頂點之間的關系被稱為“偏序”關系；右圖中頂點之間的關系被稱為”全序“關系。

在有向無環圖中，弧的方向代表著頂點之間的先后次序，例如從 V1 指向 V2 的弧表示在進行排序時 V1 在前， V2 在后。

全序是偏序的一種特殊情況。對于任意一個有向無環圖來說，通過拓撲排序得到的序列首先一定是偏序，如果任意兩個頂點都具有前后順序，那么此序列是全序。

• 拓撲排序的方法
  對有向無環圖進行拓撲排序，只需要遵循兩個原則：
• 在圖中選擇一個沒有前驅的頂點 V(即入度為0）；
• 從圖中刪除頂點 V 和所有以該頂點為尾的弧（刪除該頂點和所有以它為起點的有向邊）。

例如，在對圖 1 中的左圖進行拓撲排序時的步驟如圖 2 所示

有向無環圖如果頂點本身具有某種實際意義，例如用有向無環圖表示大學期間所學習的全部課程，每個頂點都表示一門課程，有向邊表示課程學習的先后次序

例如要先學《程序設計基礎》和《離散數學》，然后才能學習《數據結構》。所以用來表示某種活動間的優先關系的有向圖簡稱為“AOV網”。

• 進行拓撲排序時，首先找到沒有前驅的頂點 V1，如圖 2（1）所示；
• 在刪除頂點 V1 及以 V1 作為起點的弧后，繼續查找沒有前驅的頂點，此時， V2 和 V3 都符合條件，可以隨機選擇一個，例如圖 2（2） 所示，選擇 V2
• 然后繼續重復以上的操作，直至最后找不到沒有前驅的頂點。

所以，針對圖 2 來說，拓撲排序最后得到的序列有兩種：

V1 -> V2 -> V3 -> V4 V1 -> V3 -> V2 -> V4

• 如果頂點之間只是具有偏序關系，那么拓撲排序的結果肯定不唯一；如果頂點之間是全序關系，那么拓撲排序得到的序列唯一。
• 拓撲排序的C語言實現
• 大致思路為：首先通過鄰接表將 AOV 網進行存儲，由于拓撲排序的整個過程中，都是以頂點的入度為依據進行排序，所以需要根據建立的鄰接表統計出各頂點的入度。
• 在得到各頂點的入度后，首先找到入度為 0 的頂點作為拓撲排序的起始點
• 然后查找以該頂點為起始點的所有頂點，如果入度為 1，說明如果刪除前一個頂點后，該頂點的入度為 0，為拓撲排序的下一個對象。

#include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 20//最大頂點個數 #define VertexType int//頂點數據的類型typedef enum{false,true} bool;typedef struct ArcNode{int adjvex;//鄰接點在數組中的位置下標struct ArcNode * nextarc;//指向下一個鄰接點的指針 }ArcNode;typedef struct VNode{VertexType data;//頂點的數據域ArcNode * firstarc;//指向鄰接點的指針 }VNode,AdjList[MAX_VERTEX_NUM];//存儲各鏈表頭結點的數組typedef struct {AdjList vertices;//圖中頂點及各鄰接點數組int vexnum,arcnum;//記錄圖中頂點數和邊或弧數 }ALGraph;//找到頂點對應在鄰接表數組中的位置下標 int LocateVex(ALGraph G,VertexType u){for (int i=0; i<G.vexnum; i++) {if (G.vertices[i].data==u) {return i;}}return -1; }//創建AOV網，構建鄰接表 void CreateAOV(ALGraph **G){*G=(ALGraph*)malloc(sizeof(ALGraph));scanf("%d,%d",&((*G)->vexnum),&((*G)->arcnum));for (int i=0; i<(*G)->vexnum; i++) {scanf("%d",&((*G)->vertices[i].data));(*G)->vertices[i].firstarc=NULL;}VertexType initial,end;for (int i=0; i<(*G)->arcnum; i++) {scanf("%d,%d",&initial,&end);ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=LocateVex(*(*G), end);p->nextarc=NULL;int locate=LocateVex(*(*G), initial);p->nextarc=(*G)->vertices[locate].firstarc;(*G)->vertices[locate].firstarc=p;} }//結構體定義棧結構 typedef struct stack{VertexType data;struct stack * next; }stack;//初始化棧結構 void initStack(stack* *S){(*S)=(stack*)malloc(sizeof(stack));(*S)->next=NULL; }//判斷鏈表是否為空 bool StackEmpty(stack S){if (S.next==NULL) {return true;}return false; }//進棧，以頭插法將新結點插入到鏈表中 void push(stack *S,VertexType u){stack *p=(stack*)malloc(sizeof(stack));p->data=u;p->next=NULL;p->next=S->next;S->next=p; }//彈棧函數，刪除鏈表首元結點的同時，釋放該空間，并將該結點中的數據域通過地址傳值給變量i; void pop(stack *S,VertexType *i){stack *p=S->next;*i=p->data;S->next=S->next->next;free(p); }//統計各頂點的入度 void FindInDegree(ALGraph G,int indegree[]){//初始化數組，默認初始值全部為0for (int i=0; i<G.vexnum; i++) {indegree[i]=0;}//遍歷鄰接表，根據各鏈表中結點的數據域存儲的各頂點位置下標，在indegree數組相應位置+1for (int i=0; i<G.vexnum; i++) {ArcNode *p=G.vertices[i].firstarc;while (p) {indegree[p->adjvex]++;p=p->nextarc;}} }void TopologicalSort(ALGraph G){int indegree[G.vexnum];//創建記錄各頂點入度的數組FindInDegree(G,indegree);//統計各頂點的入度//建立棧結構，程序中使用的是鏈表stack *S;initStack(&S);//查找度為0的頂點，作為起始點for (int i=0; i<G.vexnum; i++) {if (!indegree[i]) {push(S, i);}}int count=0;//當棧為空，說明排序完成while (!StackEmpty(*S)) {int index;//彈棧，并記錄棧中保存的頂點所在鄰接表數組中的位置pop(S,&index);printf("%d",G.vertices[index].data);++count;//依次查找跟該頂點相鏈接的頂點，如果初始入度為1，當刪除前一個頂點后，該頂點入度為0for (ArcNode *p=G.vertices[index].firstarc; p; p=p->nextarc) {VertexType k=p->adjvex;if (!(--indegree[k])) {//頂點入度為0，入棧push(S, k);}}}//如果count值小于頂點數量，表明該有向圖有環if (count<G.vexnum) {printf("該圖有回路");return;} }int main(){ALGraph *G;CreateAOV(&G);//創建AOV網TopologicalSort(*G);//進行拓撲排序return 0; }

4.迪杰斯特拉(Dijkstra算法)算法

由荷蘭計算機科學家艾茲赫爾·戴克斯特拉在1956年提出。戴克斯特拉算法使用了廣度優先搜索解決賦權有向圖的單源最短路徑問題。

#include <iostream> #include <bits/stdc++.h> using namespace std;#define MAX 100 #define MAXCOST 0x7fffffff //int型最大值void prim(int graph[][MAX],int n,int start,int end) {int lowcost[MAX];int mst[MAX];int sum=0;for(int i=1;i<=n;i++)//將與各點與起始點的距離存入lowcost中{lowcost[i]=graph[start][i];mst[i]=1;}mst[start]=0; //起始點被標記for(int i=1;i<=n;i++){if(mst[end]==0)//終點被標記結束{cout<<sum;break;}int min=MAXCOST;int minid=0;for(int j=1;j<=n;j++)//遍歷lowcost數組，找最小值{if(lowcost[j]<min && mst[j]!=0){min=lowcost[j]; //最小值minid=j; //最小值下標}}//cout<<"V"<<mst[minid]<<"-V"<<minid<<"="<<min<<endl;sum=min;//cout<<sum<<endl;mst[minid]=0; //最小值下標點被標記for(int j=1;j<=n;j++)//找最小值點與各點的距離{if(graph[minid][j]==MAXCOST)//如果此點與最小值點沒有聯系（距離為最大值）則lowcost不變，跳過{continue;}else if(graph[minid][j]+sum<lowcost[j] && mst[j]!=0)//此點與最小點有聯系，并且+sum<lowcost 并且此點沒有被標記，則賦值給lowcost{lowcost[j]=graph[minid][j]+sum;}}} }int main() {int n,m;int start,end;int graph[MAX][MAX];cin>>n>>m>>start>>end;//初始化圖Gfor(int i=1;i<=n;i++){for(int j=1;j<=n;j++){graph[i][j]=MAXCOST;}}//構建圖Gfor(int k=1;k<=m;k++){int i,j,cost;cin>>i>>j>>cost;graph[i][j]=cost;graph[j][i]=cost;}prim(graph,n,start,end);return 0; }

5.弗洛伊德算法

暑假，小哼準備去一些城市旅游。有些城市之間有公路，有些城市之間則沒有，如下圖。為了節省經費以及方便計劃旅程，小哼希望在出發之前知道任意兩個城市之前的最短路程。

上圖中有4個城市8條公路，公路上的數字表示這條公路的長短。

請注意這些公路是單向的。我們現在需要求任意兩個城市之間的最短路程，也就是求任意兩個點之間的最短路徑。這個問題這也被稱為“多源最短路徑”問題。

• 現在需要一個數據結構來存儲圖的信息，我們仍然可以用一個4*4的矩陣（二維數組e）來存儲。
• 比如1號城市到2號城市的路程為2，則設e[1][2]的值為2。
• 2號城市無法到達4號城市，則設置e[2][4]的值為∞。
• 另外此處約定一個城市自己是到自己的也是0，例如e[1][1]為0，具體如下。

• 現在回到問題：如何求任意兩點之間最短路徑呢？通過之前的學習我們知道通過深度或廣度優先搜索可以求出兩點之間的最短路徑。

• 所以進行n2遍深度或廣度優先搜索，即對每兩個點都進行一次深度或廣度優先搜索，便可以求得任意兩點之間的最短路徑。可是還有沒有別的方法呢？

• 我們來想一想，根據我們以往的經驗，如果要讓任意兩點（例如從頂點a點到頂點b）之間的路程變短，只能引入第三個點（頂點k），并通過這個頂點k中轉即a->k->b，才可能縮短原來從頂點a點到頂點b的路程。

• 那么這個中轉的頂點k是1~n中的哪個點呢？甚至有時候不只通過一個點，而是經過兩個點或者更多點中轉會更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b。

• 比如上圖中從4號城市到3號城市（4->3）的路程e[4][3]原本是12。如果只通過1號城市中轉（4->1->3），路程將縮短為11（e[4][1]+e[1][3]=5+6=11）。

• 其實1號城市到3號城市也可以通過2號城市中轉，使得1號到3號城市的路程縮短為5（e[1][2]+e[2][3]=2+3=5）。

• 所以如果同時經過1號和2號兩個城市中轉的話，從4號城市到3號城市的路程會進一步縮短為10。

• 通過這個的例子，我們發現每個頂點都有可能使得另外兩個頂點之間的路程變短。好，下面我們將這個問題一般化。

• 當任意兩點之間不允許經過第三個點時，這些城市之間最短路程就是初始路程，如下。

• 假如現在只允許經過1號頂點，求任意兩點之間的最短路程，應該如何求呢？
• 只需判斷e[i][1] + e[1][j]是否比e[i][j]要小即可。
• e[i][j]表示的是從i號頂點到j號頂點之間的路程。e[i][1] + e[1][j]表示的是從i號頂點先到1號頂點，再從1號頂點到j號頂點的路程之和。其中i是1~n循環，j也是1~n循環，代碼實現如下。

for (i = 1; i <= n; i++) {for (j = 1; j <= n; j++){if (e[i][j] > e[i][1] + e[1][j])e[i][j] = e[i][1] + e[1][j];} }

• 在只允許經過1號頂點的情況下，任意兩點之間的最短路程更新為：

• 通過上圖我們發現：在只通過1號頂點中轉的情況下，3號頂點到2號頂點（e[3][2]）、4號頂點到2號頂點（e[4][2]）以及4號頂點到3號頂點（e[4][3]）的路程都變短了。

• 接下來繼續求在只允許經過1和2號兩個頂點的情況下任意兩點之間的最短路程。

• 如何做呢？我們需要在只允許經過1號頂點時任意兩點的最短路程的結果下，再判斷如果經過2號頂點是否可以使得i號頂點到j號頂點之間的路程變得更短。

• 即判斷e[i][2]+e[2][j]是否比e[i][j]要小，代碼實現為如下。

//經過1號頂點 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if (e[i][j] > e[i][1]+e[1][j]) e[i][j]=e[i][1]+e[1][j]; //經過2號頂點 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if (e[i][j] > e[i][2]+e[2][j]) e[i][j]=e[i][2]+e[2][j];

• 在只允許經過1和2號頂點的情況下，任意兩點之間的最短路程更新為：

• 通過上圖得知，在相比只允許通過1號頂點進行中轉的情況下，這里允許通過1和2號頂點進行中轉，使得e[1][3]和e[4][3]的路程變得更短了。

• 同理，繼續在只允許經過1、2和3號頂點進行中轉的情況下，求任意兩點之間的最短路程。任意兩點之間的最短路程更新為：

• 最后允許通過所有頂點作為中轉，任意兩點之間最終的最短路程為：

#include <stdio.h>int main() {int e[10][10],k,i,j,n,m,t1,t2,t3;int inf=99999999; //用inf(infinity的縮寫)存儲一個我們認為的正無窮值//讀入n和m，n表示頂點個數，m表示邊的條數scanf("%d %d",&n,&m);//初始化for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j) e[i][j]=0;else e[i][j]=inf;//讀入邊for(i=1;i<=m;i++){scanf("%d %d %d",&t1,&t2,&t3);e[t1][t2]=t3;}//Floyd-Warshall算法核心語句for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(e[i][j]>e[i][k]+e[k][j] )e[i][j]=e[i][k]+e[k][j];//輸出最終的結果for(i=1;i<=n;i++){for(j=1;j<=n;j++){printf("%10d",e[i][j]);}printf("\n");}return 0; }

總結

以上是生活随笔為你收集整理的数据结构--图(Graph)详解(四)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。