數(shù)據(jù)結(jié)構(gòu)–圖(Graph)詳解(三)

文章目錄

• 數(shù)據(jù)結(jié)構(gòu)--圖(Graph)詳解(三)
• • 一、深度優(yōu)先生成樹和廣度優(yōu)先生成樹
  • • 1.鋪墊
    • 2.非連通圖的生成森林
    • 3.深度優(yōu)先生成森林
    • 4.廣度優(yōu)先生成森林
  • 二、幾個特別NB的算法詳解
  • • 1.普里姆算法(Prim算法)求最小生成樹
    • 2.克魯斯卡爾算法(Kruskal算法)求最小生成樹
    • 3.拓撲排序算法
    • 4.迪杰斯特拉(Dijkstra算法)算法
    • 5.弗洛伊德算法

一、深度優(yōu)先生成樹和廣度優(yōu)先生成樹

1.鋪墊

本博客來解決對于給定的無向圖，如何構(gòu)建它們相對應(yīng)的生成樹或者生成森林。

• 其實在對無向圖進行遍歷的時候，遍歷過程中所經(jīng)歷過的圖中的頂點和邊的組合，就是圖的生成樹或者生成森林。

例如，圖 1 中的無向圖是由 V1～V7 的頂點和編號分別為 a～i 的邊組成。

當使用深度優(yōu)先搜索算法時，假設(shè) V1 作為遍歷的起始點，涉及到的頂點和邊的遍歷順序為（不唯一）：

此種遍歷順序構(gòu)建的生成樹為：

• 由深度優(yōu)先搜索得到的樹為深度優(yōu)先生成樹。
• 同理，廣度優(yōu)先搜索生成的樹為廣度優(yōu)先生成樹

圖 1 無向圖以頂點 V1 為起始點進行廣度優(yōu)先搜索遍歷得到的樹，如圖 3 所示：

2.非連通圖的生成森林

• 非連通圖在進行遍歷時，實則是對非連通圖中每個連通分量分別進行遍歷，在遍歷過程經(jīng)過的每個頂點和邊，就構(gòu)成了每個連通分量的生成樹。
• 非連通圖中，多個連通分量構(gòu)成的多個生成樹為非連通圖的生成森林。

3.深度優(yōu)先生成森林

例如，對圖 4 中的非連通圖 （a） 采用深度優(yōu)先搜索算法遍歷時，得到的深度優(yōu)先生成森林（由 3 個深度優(yōu)先生成樹構(gòu)成）如 （b） 所示（不唯一）。

非連通圖在遍歷生成森林時，可以采用孩子兄弟表示法將森林轉(zhuǎn)化為一整棵二叉樹進行存儲。

• 具體實現(xiàn)的代碼：

#include <stdio.h> #include <stdlib.h> #define MAX_VERtEX_NUM 20 //頂點的最大個數(shù) #define VRType int //表示頂點之間的關(guān)系的變量類型 #define VertexType int //圖中頂點的數(shù)據(jù)類型 typedef enum{false,true}bool; //定義bool型常量 bool visited[MAX_VERtEX_NUM]; //設(shè)置全局數(shù)組，記錄標記頂點是否被訪問過typedef struct {VRType adj; //對于無權(quán)圖，用 1 或 0 表示是否相鄰；對于帶權(quán)圖，直接為權(quán)值。 }ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];typedef struct {VertexType vexs[MAX_VERtEX_NUM]; //存儲圖中頂點數(shù)據(jù)AdjMatrix arcs; //二維數(shù)組，記錄頂點之間的關(guān)系int vexnum,arcnum; //記錄圖的頂點數(shù)和弧（邊）數(shù) }MGraph;//孩子兄弟表示法的鏈表結(jié)點結(jié)構(gòu) typedef struct CSNode{VertexType data;struct CSNode * lchild;//孩子結(jié)點struct CSNode * nextsibling;//兄弟結(jié)點 }*CSTree,CSNode;//根據(jù)頂點本身數(shù)據(jù)，判斷出頂點在二維數(shù)組中的位置 int LocateVex(MGraph G,VertexType v){int i=0;//遍歷一維數(shù)組，找到變量vfor (; i<G.vexnum; i++) {if (G.vexs[i]==v) {break;}}//如果找不到，輸出提示語句，返回-1if (i>G.vexnum) {printf("no such vertex.\n");return -1;}return i; }//構(gòu)造無向圖 void CreateDN(MGraph *G){scanf("%d,%d",&(G->vexnum),&(G->arcnum));getchar();for (int i=0; i<G->vexnum; i++) {scanf("%d",&(G->vexs[i]));}for (int i=0; i<G->vexnum; i++) {for (int j=0; j<G->vexnum; j++) {G->arcs[i][j].adj=0;}}for (int i=0; i<G->arcnum; i++) {int v1,v2;scanf("%d,%d",&v1,&v2);int n=LocateVex(*G, v1);int m=LocateVex(*G, v2);if (m==-1 ||n==-1) {printf("no this vertex\n");return;}G->arcs[n][m].adj=1;G->arcs[m][n].adj=1;//無向圖的二階矩陣沿主對角線對稱} }int FirstAdjVex(MGraph G,int v) {//查找與數(shù)組下標為v的頂點之間有邊的頂點，返回它在數(shù)組中的下標for(int i = 0; i<G.vexnum; i++){if( G.arcs[v][i].adj ){return i;}}return -1; }int NextAdjVex(MGraph G,int v,int w) {//從前一個訪問位置w的下一個位置開始，查找之間有邊的頂點for(int i = w+1; i<G.vexnum; i++){if(G.arcs[v][i].adj){return i;}}return -1; }void DFSTree(MGraph G,int v,CSTree*T){//將正在訪問的該頂點的標志位設(shè)為truevisited[v]=true;bool first=true;CSTree q=NULL;//依次遍歷該頂點的所有鄰接點for (int w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G, v, w)) {//如果該臨界點標志位為false，說明還未訪問if (!visited[w]) {//為該鄰接點初始化為結(jié)點CSTree p=(CSTree)malloc(sizeof(CSNode));p->data=G.vexs[w];p->lchild=NULL;p->nextsibling=NULL;//該結(jié)點的第一個鄰接點作為孩子結(jié)點，其它鄰接點作為孩子結(jié)點的兄弟結(jié)點if (first) {(*T)->lchild=p;first=false;}//否則，為兄弟結(jié)點else{q->nextsibling=p;}q=p;//以當前訪問的頂點為樹根，繼續(xù)訪問其鄰接點DFSTree(G, w, &q);}} }//深度優(yōu)先搜索生成森林并轉(zhuǎn)化為二叉樹 void DFSForest(MGraph G,CSTree *T){(*T)=NULL;//每個頂點的標記為初始化為falsefor (int v=0; v<G.vexnum; v++) {visited[v]=false;}CSTree q=NULL;//遍歷每個頂點作為初始點，建立深度優(yōu)先生成樹for (int v=0; v<G.vexnum; v++) {//如果該頂點的標記位為false，證明未訪問過if (!(visited[v])) {//新建一個結(jié)點，表示該頂點CSTree p=(CSTree)malloc(sizeof(CSNode));p->data=G.vexs[v];p->lchild=NULL;p->nextsibling=NULL;//如果樹未空，則該頂點作為樹的樹根if (!(*T)) {(*T)=p; }//該頂點作為樹根的兄弟結(jié)點else{q->nextsibling=p;}//每次都要把q指針指向新的結(jié)點，為下次添加結(jié)點做鋪墊q=p;//以該結(jié)點為起始點，構(gòu)建深度優(yōu)先生成樹DFSTree(G,v,&p);}} }//前序遍歷二叉樹 void PreOrderTraverse(CSTree T){if (T) {printf("%d ",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->nextsibling);}return; }int main() {MGraph G;//建立一個圖的變量CreateDN(&G);//初始化圖CSTree T;DFSForest(G, &T);PreOrderTraverse(T);return 0; }

圖中，3 種顏色的樹各代表一棵深度優(yōu)先生成樹，使用孩子兄弟表示法表示，也就是將三棵樹的樹根相連，第一棵樹的樹根作為整棵樹的樹根。

4.廣度優(yōu)先生成森林

• 非連通圖采用廣度優(yōu)先搜索算法進行遍歷時，經(jīng)過的頂點以及邊的集合為該圖的廣度優(yōu)先生成森林。

拿圖 4（a）中的非連通圖為例，通過廣度優(yōu)先搜索得到的廣度優(yōu)先生成森林用孩子兄弟表示法為：

• 實現(xiàn)代碼為：

#include <stdio.h> #include <stdlib.h> #define MAX_VERtEX_NUM 20 //頂點的最大個數(shù) #define VRType int //表示頂點之間的關(guān)系的變量類型 #define InfoType char //存儲弧或者邊額外信息的指針變量類型 #define VertexType int //圖中頂點的數(shù)據(jù)類型typedef enum{false,true}bool; //定義bool型常量bool visited[MAX_VERtEX_NUM]; //設(shè)置全局數(shù)組，記錄標記頂點是否被訪問過typedef struct {VRType adj; //對于無權(quán)圖，用 1 或 0 表示是否相鄰；對于帶權(quán)圖，直接為權(quán)值。InfoType * info; //弧或邊額外含有的信息指針 }ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];typedef struct {VertexType vexs[MAX_VERtEX_NUM]; //存儲圖中頂點數(shù)據(jù)AdjMatrix arcs; //二維數(shù)組，記錄頂點之間的關(guān)系int vexnum,arcnum; //記錄圖的頂點數(shù)和弧（邊）數(shù) }MGraph;typedef struct CSNode{VertexType data;struct CSNode * lchild;//孩子結(jié)點struct CSNode * nextsibling;//兄弟結(jié)點 }*CSTree,CSNode;typedef struct Queue{CSTree data;//隊列中存放的為樹結(jié)點struct Queue * next; }Queue;//根據(jù)頂點本身數(shù)據(jù)，判斷出頂點在二維數(shù)組中的位置 int LocateVex(MGraph * G,VertexType v){int i=0;//遍歷一維數(shù)組，找到變量vfor (; i<G->vexnum; i++) {if (G->vexs[i]==v) {break;}}//如果找不到，輸出提示語句，返回-1if (i>G->vexnum) {printf("no such vertex.\n");return -1;}return i; }//構(gòu)造無向圖 void CreateDN(MGraph *G){scanf("%d,%d",&(G->vexnum),&(G->arcnum));for (int i=0; i<G->vexnum; i++) {scanf("%d",&(G->vexs[i]));}for (int i=0; i<G->vexnum; i++) {for (int j=0; j<G->vexnum; j++) {G->arcs[i][j].adj=0;G->arcs[i][j].info=NULL;}}for (int i=0; i<G->arcnum; i++) {int v1,v2;scanf("%d,%d",&v1,&v2);int n=LocateVex(G, v1);int m=LocateVex(G, v2);if (m==-1 ||n==-1) {printf("no this vertex\n");return;}G->arcs[n][m].adj=1;G->arcs[m][n].adj=1;//無向圖的二階矩陣沿主對角線對稱} }int FirstAdjVex(MGraph G,int v) {//查找與數(shù)組下標為v的頂點之間有邊的頂點，返回它在數(shù)組中的下標for(int i = 0; i<G.vexnum; i++){if( G.arcs[v][i].adj ){return i;}}return -1; }int NextAdjVex(MGraph G,int v,int w) {//從前一個訪問位置w的下一個位置開始，查找之間有邊的頂點for(int i = w+1; i<G.vexnum; i++){if(G.arcs[v][i].adj){return i;}}return -1; }//初始化隊列 void InitQueue(Queue ** Q){(*Q)=(Queue*)malloc(sizeof(Queue));(*Q)->next=NULL; }//結(jié)點v進隊列 void EnQueue(Queue **Q,CSTree T){Queue * element=(Queue*)malloc(sizeof(Queue));element->data=T;element->next=NULL;Queue * temp=(*Q);while (temp->next!=NULL) {temp=temp->next;}temp->next=element; }//隊頭元素出隊列 void DeQueue(Queue **Q,CSTree *u){(*u)=(*Q)->next->data;(*Q)->next=(*Q)->next->next; }//判斷隊列是否為空 bool QueueEmpty(Queue *Q){if (Q->next==NULL) {return true;}return false; }void BFSTree(MGraph G,int v,CSTree*T){CSTree q=NULL;Queue * Q;InitQueue(&Q);//根結(jié)點入隊EnQueue(&Q, (*T));//當隊列為空時，證明遍歷完成while (!QueueEmpty(Q)) {bool first=true;//隊列首個結(jié)點出隊DeQueue(&Q,&q);//判斷結(jié)點中的數(shù)據(jù)在數(shù)組中的具體位置int v=LocateVex(&G,q->data);//已經(jīng)訪問過的更改其標志位visited[v]=true;//遍歷以出隊結(jié)點為起始點的所有鄰接點for (int w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v, w)) {//標志位為false，證明未遍歷過if (!visited[w]) {//新建一個結(jié)點 p，存放當前遍歷的頂點CSTree p=(CSTree)malloc(sizeof(CSNode));p->data=G.vexs[w];p->lchild=NULL;p->nextsibling=NULL;//當前結(jié)點入隊EnQueue(&Q, p);//更改標志位visited[w]=true;//如果是出隊頂點的第一個鄰接點，設(shè)置p結(jié)點為其左孩子if (first) {q->lchild=p;first=false;}//否則設(shè)置其為兄弟結(jié)點else{q->nextsibling=p;}q=p;}}} }//廣度優(yōu)先搜索生成森林并轉(zhuǎn)化為二叉樹 void BFSForest(MGraph G,CSTree *T){(*T)=NULL;//每個頂點的標記為初始化為falsefor (int v=0; v<G.vexnum; v++) {visited[v]=false;}CSTree q=NULL;//遍歷圖中所有的頂點for (int v=0; v<G.vexnum; v++) {//如果該頂點的標記位為false，證明未訪問過if (!(visited[v])) {//新建一個結(jié)點，表示該頂點CSTree p=(CSTree)malloc(sizeof(CSNode));p->data=G.vexs[v];p->lchild=NULL;p->nextsibling=NULL;//如果樹未空，則該頂點作為樹的樹根if (!(*T)) {(*T)=p;}//該頂點作為樹根的兄弟結(jié)點else{q->nextsibling=p;}//每次都要把q指針指向新的結(jié)點，為下次添加結(jié)點做鋪墊q=p;//以該結(jié)點為起始點，構(gòu)建廣度優(yōu)先生成樹BFSTree(G,v,&p);}} }//前序遍歷二叉樹 void PreOrderTraverse(CSTree T){if (T) {printf("%d ",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->nextsibling);}return; }int main() {MGraph G;//建立一個圖的變量CreateDN(&G);//初始化圖CSTree T;BFSForest(G, &T);PreOrderTraverse(T);return 0; }

二、幾個特別NB的算法詳解

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

通過前面的學(xué)習(xí)，對于含有 n 個頂點的連通圖來說可能包含有多種生成樹，例如圖 1 所示：

圖 1 中的連通圖和它相對應(yīng)的生成樹，可以用于解決實際生活中的問題：

假設(shè)A、B、C 和 D 為 4 座城市，為了方便生產(chǎn)生活，要為這 4 座城市建立通信。

對于 4 個城市來講，本著節(jié)約經(jīng)費的原則，只需要建立 3 個通信線路即可，就如圖 1（b）中的任意一種方式。

在具體選擇采用（b）中哪一種方式時，需要綜合考慮城市之間間隔的距離，建設(shè)通信線路的難度等各種因素，將這些因素綜合起來用一個數(shù)值表示，當作這條線路的權(quán)值。

假設(shè)通過綜合分析，城市之間的權(quán)值如圖 2（a）所示，對于（b）的方案中，選擇權(quán)值總和為 7 的兩種方案最節(jié)約經(jīng)費。

這就是要討論的最小生成樹的問題，簡單得理解就是給定一個帶有權(quán)值的連通圖（連通網(wǎng)），如何從眾多的生成樹中篩選出權(quán)值總和最小的生成樹，即為該圖的最小生成樹。

• 普里姆算法
• 給定一個連通網(wǎng)，求最小生成樹的方法有：普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法。
• 普里姆算法在找最小生成樹時，將頂點分為兩類，一類是在查找的過程中已經(jīng)包含在樹中的（假設(shè)為 A 類），剩下的是另一類（假設(shè)為 B 類）。
• 對于給定的連通網(wǎng)，起始狀態(tài)全部頂點都歸為 B 類。
• 在找最小生成樹時，選定任意一個頂點作為起始點，并將之從 B 類移至 A 類；
• 然后找出 B 類中到 A 類中的頂點之間權(quán)值最小的頂點，將之從 B 類移至 A 類
• 如此重復(fù)，直到 B 類中沒有頂點為止。所走過的頂點和邊就是該連通圖的最小生成樹。
• 例如，通過普里姆算法查找圖 2（a）的最小生成樹的步驟為：
• 假如從頂點A出發(fā)，頂點 B、C、D 到頂點 A 的權(quán)值分別為 2、4、2，所以，對于頂點 A 來說，頂點 B 和頂點 D 到 A 的權(quán)值最小，假設(shè)先找到的頂點 B：

• 繼續(xù)分析頂點 C 和 D，頂點 C 到 B 的權(quán)值為 3，到 A 的權(quán)值為 4；
• 頂點 D 到 A 的權(quán)值為 2，到 B 的權(quán)值為無窮大（如果之間沒有直接通路，設(shè)定權(quán)值為無窮大）。
• 所以頂點 D 到 A 的權(quán)值最小：

• 最后，只剩下頂點 C，到 A 的權(quán)值為 4，到 B 的權(quán)值和到 D 的權(quán)值一樣大，為 3。所以該連通圖有兩個最小生成樹：

#include <stdio.h> #include <stdlib.h> #define VertexType int #define VRType int #define MAX_VERtEX_NUM 20 #define InfoType char #define INFINITY 65535typedef struct {VRType adj; //對于無權(quán)圖，用 1 或 0 表示是否相鄰；對于帶權(quán)圖，直接為權(quán)值。InfoType * info; //弧額外含有的信息指針 }ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];typedef struct {VertexType vexs[MAX_VERtEX_NUM]; //存儲圖中頂點數(shù)據(jù)AdjMatrix arcs; //二維數(shù)組，記錄頂點之間的關(guān)系int vexnum,arcnum; //記錄圖的頂點數(shù)和弧（邊）數(shù) }MGraph;//根據(jù)頂點本身數(shù)據(jù)，判斷出頂點在二維數(shù)組中的位置 int LocateVex(MGraph G,VertexType v){int i=0;//遍歷一維數(shù)組，找到變量vfor (; i<G.vexnum; i++) {if (G.vexs[i]==v) {return i;}}return -1; }//構(gòu)造無向網(wǎng) void CreateUDN(MGraph* G){scanf("%d,%d",&(G->vexnum),&(G->arcnum));for (int i=0; i<G->vexnum; i++) {scanf("%d",&(G->vexs[i]));}for (int i=0; i<G->vexnum; i++) {for (int j=0; j<G->vexnum; j++) {G->arcs[i][j].adj=INFINITY;G->arcs[i][j].info=NULL;}}for (int i=0; i<G->arcnum; i++) {int v1,v2,w;scanf("%d,%d,%d",&v1,&v2,&w);int m=LocateVex(*G, v1);int n=LocateVex(*G, v2);if (m==-1 ||n==-1) {printf("no this vertex\n");return;}G->arcs[n][m].adj=w;G->arcs[m][n].adj=w;} }//輔助數(shù)組，用于每次篩選出權(quán)值最小的邊的鄰接點 typedef struct {VertexType adjvex;//記錄權(quán)值最小的邊的起始點VRType lowcost;//記錄該邊的權(quán)值 }closedge[MAX_VERtEX_NUM]; closedge theclose;//創(chuàng)建一個全局數(shù)組，因為每個函數(shù)中都會使用到//在輔助數(shù)組中找出權(quán)值最小的邊的數(shù)組下標，就可以間接找到此邊的終點頂點。 int minimun(MGraph G,closedge close){int min=INFINITY;int min_i=-1;for (int i=0; i<G.vexnum; i++) {//權(quán)值為0，說明頂點已經(jīng)歸入最小生成樹中；然后每次和min變量進行比較，最后找出最小的。if (close[i].lowcost>0 && close[i].lowcost < min) {min=close[i].lowcost;min_i=i;}}//返回最小權(quán)值所在的數(shù)組下標return min_i; }//普里姆算法函數(shù)，G為無向網(wǎng)，u為在網(wǎng)中選擇的任意頂點作為起始點 void miniSpanTreePrim(MGraph G,VertexType u){//找到該起始點在頂點數(shù)組中的位置下標int k=LocateVex(G, u);//首先將與該起始點相關(guān)的所有邊的信息：邊的起始點和權(quán)值，存入輔助數(shù)組中相應(yīng)的位置，例如（1，2）邊，adjvex為0，lowcost為6，存入theclose[1]中，輔助數(shù)組的下標表示該邊的頂點2for (int i=0; i<G.vexnum; i++) {if (i !=k) {theclose[i].adjvex=k;theclose[i].lowcost=G.arcs[k][i].adj;}}//由于起始點已經(jīng)歸為最小生成樹，所以輔助數(shù)組對應(yīng)位置的權(quán)值為0，這樣，遍歷時就不會被選中theclose[k].lowcost=0;//選擇下一個點，并更新輔助數(shù)組中的信息for (int i=1; i<G.vexnum; i++) {//找出權(quán)值最小的邊所在數(shù)組下標k=minimun(G, theclose);//輸出選擇的路徑printf("v%d v%d\n",G.vexs[theclose[k].adjvex],G.vexs[k]);//歸入最小生成樹的頂點的輔助數(shù)組中的權(quán)值設(shè)為0theclose[k].lowcost=0;//信息輔助數(shù)組中存儲的信息，由于此時樹中新加入了一個頂點，需要判斷，由此頂點出發(fā)，到達其它各頂點的權(quán)值是否比之前記錄的權(quán)值還要小，如果還小，則更新for (int j=0; j<G.vexnum; j++) {if (G.arcs[k][j].adj<theclose[j].lowcost) {theclose[j].adjvex=k;theclose[j].lowcost=G.arcs[k][j].adj;}}}printf("\n"); }int main(){MGraph G;CreateUDN(&G);miniSpanTreePrim(G, 1); }

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

3.拓撲排序算法

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

5.弗洛伊德算法

2，3，4，5算法詳解請點擊：https://blog.csdn.net/wolfGuiDao/article/details/107593373

總結(jié)

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

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