數(shù)據(jù)結(jié)構(gòu)圖的算法的畢業(yè)論文

1、 圖圖形結(jié)構(gòu)是一種比樹形結(jié)構(gòu)更復雜的非線性結(jié)構(gòu)。樹形結(jié)構(gòu)中的結(jié)點之間具有明顯的層次關(guān)系，且每一層上的結(jié)點只能和上一層中的一個結(jié)點相關(guān)，但可能和下一層的多個結(jié)點相關(guān)。在圖形結(jié)構(gòu)中，任意兩個結(jié)點之間都可能相關(guān)，即結(jié)點與結(jié)點之間的鄰接關(guān)系可以是任意的。因此，圖形結(jié)構(gòu)可用來描述更加復雜的對象。1 圖的基本概念和存儲結(jié)構(gòu) 1.1 圖的定義圖（Graph）是由非空的頂點集合V與描述頂點之間關(guān)系邊（或者弧）的集合E組成，其形式化定義為：G=(V, E) 如果圖G中的每一條邊都是沒有方向的，則稱G為無向圖。無向圖中邊是圖中頂點的無序偶對。無序偶對通常用圓括號“( )”表示。例如，頂點偶對(vi,vj)表示頂點

2、vi和頂點vj相連的邊，并且(vi,vj)與(vj,vi)表示同一條邊。 如果圖G中的每一條邊都是有方向的，則稱G為有向圖。有向圖中的邊是圖中頂點的有序偶對，有序偶對通常用尖括號“< >”表示。例如，頂點偶對<vi,vj>表示從頂點vi指向頂點vj的一條有向邊；其中，頂點vi稱為有向邊<vi,vj>的起點，頂點vj稱為有向邊<vi,vj>的終點。有向邊也稱為??；對弧<vi,vj>來說，vi為弧的起點，稱為弧尾；vj為弧的終點，稱為弧頭。圖是一種復雜的數(shù)據(jù)結(jié)構(gòu)，表現(xiàn)在不僅各頂點的度可以不同，而且頂點之間的邏輯關(guān)系也錯綜復雜。從圖的定義可

3、知：一個圖的信息包括兩個部分：圖中頂點的信息以及描述頂點之間的關(guān)系邊或弧的信息。因此無論采取什么方法來建立圖的存儲結(jié)構(gòu)，都要完整、準確地反映這兩部分的信息。為適于用C語言描述，從本節(jié)起頂點序號由0開始，即圖的頂點集的一般形式為：V=v0,v1,vn-1。下面介紹幾種常用的圖的存儲結(jié)構(gòu)。1.2 鄰接矩陣所謂鄰接矩陣存儲結(jié)構(gòu)，就是用一維數(shù)組存儲圖中頂點的信息，并用矩陣來表示圖中各頂點之間的鄰接關(guān)系。假定圖G=(V, E)有n個頂點，即V=v0,v1,vn-1，則表示G中各頂點相鄰關(guān)系需用一個n×n的矩陣，且矩陣元素為：1 若(vi,vj)或<vi,vj>是E中的邊0 若(vi

4、,vj)或<vi,vj>不是E中的邊Aij= 若G是帶權(quán)圖（網(wǎng)），則鄰接矩陣可定義為：wij 若(vi,vj)或<vi,vj>是E中的邊0或 若(vi,vj)或<vi,vj>不是E中的邊Aij= 其中，wij表示(vi,vj)或<vi,vj>上的權(quán)值；則為計算機上所允許的大于所有邊上權(quán)值的數(shù)值。無向圖的鄰接矩陣表示如圖7-6所示。圖7-6 無向圖及鄰接矩陣表示有向圖的鄰接矩陣表示如圖7-7所示。圖7-7 有向圖及鄰接矩陣表示帶權(quán)圖的鄰接矩陣表示如圖7-8所示。圖7-8 帶權(quán)圖及鄰接矩陣表示從圖的鄰接矩陣可以看出以下特點：（1）無向圖（包括帶權(quán)圖）

5、的鄰接矩陣一定是一個按對角線對稱的對稱矩陣。因此，在具體存放鄰接矩陣時只需存放上（或下）三角矩陣的元素即可。（2）對于無向圖，鄰接矩陣的第i行或第i列的非零元素（或非元素）個數(shù)正好是第i個頂點的度D(vi)。（3）對有向圖，鄰接矩陣的第i行非零元素（或非元素）的個數(shù)正好是第i個頂點的出度OD(vi)，第i列非零元素（或非元素）的個數(shù)正好是第i個頂點的入度ID(vi)。（4）用鄰接矩陣存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連；但是，要確定圖中具體有多少條邊，則必須按行、按列對每一個元素進行查找后方能確定，因此花費的時間代價較大，這也是用鄰接矩陣存儲圖的局限性。 在采用鄰接矩陣方式表示圖

6、時，除了用一個二維數(shù)組存儲用于表示頂點相鄰關(guān)系的鄰接矩陣之外，還需要用一個一維數(shù)組存儲頂點信息。這樣，一個圖在順序存儲結(jié)構(gòu)下的類型定義為； typedef struct char vertexMaxNum; /*頂點為字符型且頂點表的長度小于MaxNum*/ int edgesMaxNumMaxNum; /*邊為整型且edges為鄰接矩陣*/ MGraph; /*MGraph為采用鄰接矩陣存儲的圖類型*/建立一個無向圖的鄰接矩陣程序如下：#include<stdio.h>#include<stdlib.h>#define MAXSIZE 30typedef struct

7、 char vertexMAXSIZE; /頂點為字符型且頂點表的長度小于MAXSIZE int edgesMAXSIZEMAXSIZE; /邊為整型且edges為鄰接矩陣 MGraph; /MGraph為采用鄰接矩陣存儲的圖類型void CreatMGraph(MGraph *g,int e,int n) /建立無向圖的鄰接矩陣g->egdes，n為頂點個數(shù)，e為邊數(shù) int i,j,k; printf("Input data of vertexs(0n-1):n"); for(i=0;i<n;i+) g->vertexi=i; /讀入頂點信息 for(

8、i=0;i<n;i+) for(j=0;j<n;j+) g->edgesij=0; /初始化鄰接矩陣 for(k=1;k<=e;k+) /輸入e條邊*/ printf("Input edge of(i,j): "); scanf("%d,%d",&i,&j); g->edgesij=1; g->edgesji=1; void main()int i,j,n,e; MGraph *g; /建立指向采用鄰接矩陣存儲圖類型指針g=(MGraph *)malloc(sizeof(MGraph); /生成采用鄰接

9、矩陣存儲圖類型的存儲空間printf("Input size of MGraph: "); /輸入鄰接矩陣的大小scanf("%d",&n); printf("Input number of edge: "); /輸入鄰接矩陣的邊數(shù)scanf("%d",&e); CreatMGraph(g,e,n); /生成存儲圖的鄰接矩陣printf("Output MGraph:n"); /輸出存儲圖的鄰接矩陣for(i=0;i<n;i+)for(j=0;j<n;j+)print

10、f("%4d",g->edgesij);printf("n");【說明】無向圖的鄰接矩陣表示如圖15-1所示。 0 1 0 1 A= 1 0 1 1 0 1 0 0 1 1 0 0 V0V3V1V2圖15-1 無向圖及鄰接矩陣表示對圖15-1所示的無向圖，程序執(zhí)行如下：輸入： Input size of MGraph: 4Input number of edge: 4Input data of vertexs(0n-1):Input edge of(i,j): 0,1Input edge of(i,j): 0,3Input edge of(i,j)

11、: 1,3Input edge of(i,j): 1,2輸出： Output MGraph: 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0Press any key to continue 1.3 鄰接表 鄰接表是圖的一種順序存儲與鏈式存儲相結(jié)合的存儲方法。鄰接表表示法類似于樹的孩子表示法。也即，對于圖G中的每個頂點vi，將所有鄰接于vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表；然后，將所有頂點的鄰接表表頭指針放入到一個一維數(shù)組中，就構(gòu)成了圖的鄰接表。用鄰接表表示的圖有兩種結(jié)構(gòu)，如圖7-9所示。頂點域 鄰接表表頭指針 鄰接點域 指針域vertexfirste

12、dgeadjvexnext 頂點表結(jié)點 鄰接表結(jié)點圖7-9 鄰接表表示的結(jié)點結(jié)構(gòu) 一種是用一維數(shù)組表示的頂點表的結(jié)點（即數(shù)組元素）結(jié)構(gòu)，它由頂點域（vertex）和指向該頂點第一條鄰接邊的指針域（firstedge）（也即，這個指針指向該頂點的鄰接表）所構(gòu)成。另一種是鄰接表結(jié)點（邊結(jié)點），它由鄰接點域(adjvex)和指向下一條鄰接邊的指針域（next）所構(gòu)成。對帶權(quán)圖（網(wǎng)）的鄰接表結(jié)點則需增加一個存儲邊上權(quán)值信息的這樣一個域。因此，帶權(quán)圖的鄰接表結(jié)點結(jié)構(gòu)如圖7-10所示。adjvexinfonext圖7-10 帶權(quán)圖（網(wǎng)）的鄰接表結(jié)點結(jié)構(gòu)圖7-11給出了圖7-6所示的無向圖所對應(yīng)的鄰接表表示

13、。圖7-11 無向圖的鄰接表表示鄰接表表示下的類型定義為：typedef struct node /*鄰接表結(jié)點*/ int adjvex; /*鄰接點域*/ struct node *next; /*指向下一個鄰接邊結(jié)點的指針域*/EdgeNode; /*鄰接表結(jié)點類型*/typedef struct vnode /*頂點表結(jié)點*/ int vertex; /*頂點域*/ EdgeNode *firstedge; /*指向鄰接表第一個鄰接邊結(jié)點的指針域*/VertexNode /*頂點表結(jié)點類型*/ 建立一個無向圖的鄰接表存儲算法如下：void CreatAdjlist（VetexNode

14、g,int e,int n）/*建立無向圖的鄰接表，n為頂點數(shù)，e為邊數(shù)，g存儲n個頂點表結(jié)點*/ EdgeNode *p;int i,j,k; printf(“Input date of vetex(0n-1);n”); for(i=0;i<n;i+) /*建立有n個頂點的頂點表*/ gi.vertex=i; /*讀入頂點i信息*/ gi.firstedge=NULL; /*初始化指向頂點i的鄰接表表頭指針*/ for(k=1;k<=e;k+) /*輸入e條邊*/ printf("Input edge of(i,j): "); scanf("%d,%

15、d",i,j); p=(EdgeNode *)malloc(sizeof(EdgeNode); p->adjex=j; /*在頂點vi的鄰接表中添加鄰接點為j的結(jié)點*/ p->next=gi.firstedge; /*插入是在鄰接表表頭進行的*/ gi.firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode); p->adjvex=i; /*在頂點vj的鄰接表中添加鄰接點為i的結(jié)點*/ p->next=gj.firstedge; /*插入是在鄰接表表頭進行的*/ gi.firstedge=p; 2 圖的遍歷 圖的遍歷

16、是指從圖中的任一頂點出發(fā)，按照事先確定的某種搜索方法依次對圖中所有頂點進行訪問且僅訪問一次的過程。圖的遍歷要比樹的遍歷復雜得多，其復雜性主要表現(xiàn)在以下4個方面：（1） 在圖結(jié)構(gòu)中，沒有象樹根結(jié)點那樣 “自然” 的首結(jié)點，即圖中的任何一個頂點都可以作為第一個被訪問的結(jié)點。（2） 在非連通圖中，從一個頂點出發(fā)只能訪問它所在的連通分量上的所有頂點；因此，還需考慮如何選取下一個未被訪問的頂點來繼續(xù)訪問圖中其余的連通分量。（3） 在圖結(jié)構(gòu)中如果有回路存在，則一個頂點被訪問后有可能沿回路又回到該頂點。（4） 在圖結(jié)構(gòu)中一個頂點可以和其它多個頂點相鄰，當該頂點訪問過后則存在如何從眾多相鄰頂點中選取下一個要訪

17、問的頂點問題。圖的遍歷是圖的一種基本操作，它是求解圖的連通性問題、拓撲排序以及求關(guān)鍵路徑等算法的基礎(chǔ)。圖的遍歷通常采用深度優(yōu)先搜索（Depth First Search,DFS）和廣度優(yōu)先搜索（Breadth First Search,BFS）兩種方式，這兩種方式對無向圖和有向圖的遍歷都適用。2.1 深度優(yōu)先搜索深度優(yōu)先搜索對圖的遍歷類似于樹的先根遍歷，是樹的先根遍歷的一種推廣；也即，搜索頂點的次序是沿著一條路徑盡量向縱深發(fā)展。深度優(yōu)先搜索的基本思想是：假設(shè)初始狀態(tài)是圖中所有頂點都未曾訪問過，則深度優(yōu)先搜索可以從圖中某個頂點v出發(fā)即先訪問v，然后依次從v的未曾訪問過的鄰接點出發(fā)，繼續(xù)深度優(yōu)先搜

18、索圖，直至圖中所有和v有路徑相通的頂點都被訪問過；若此時圖中尚有頂點未被訪問過，則另選一個未曾訪問過的頂點作為起始點，重復上述深度優(yōu)先搜索的過程，直到圖中的所有頂點都被訪問過為止。我們以圖7-18的無向圖為例進行圖的深度優(yōu)先搜索。假定從頂點v0出發(fā)，在訪問了頂點v0后選擇鄰接點v1作為下一個訪問的頂點；由于v1未曾訪問過，則訪問v1并繼續(xù)由v1開始搜索下一個鄰接點v3作為訪問頂點；v3同樣沒有訪問過，則訪問v3并繼續(xù)搜索下一個鄰接點v6；v6也未訪問過，則訪問v6再繼續(xù)搜索下一個鄰接點v4；v4未曾訪問過，則訪問v4并繼續(xù)搜索下一個鄰接點v1，此時由于v1已被訪問過則回退至v4繼續(xù)搜索v4的下

19、一個鄰接點；由于v4已無未被訪問過的鄰接點，則繼續(xù)回退到v6再搜索v6的未被訪問鄰接點；這種回退一直持續(xù)到v0，此時可搜索到v0的未被訪問鄰接點v2，即訪問v2并繼續(xù)搜索下一個鄰接點v5；由于v5未被訪問，則訪問v5并繼續(xù)搜索v5的鄰接點；因v5已無未被訪問過的鄰接點故回退至v2，繼續(xù)搜索v2的未被訪問鄰接點，但v2已無未被訪問過的鄰接點，則回退至v0，而v0也無未被訪問的鄰接點。由于v0為搜索圖時的出發(fā)結(jié)點，故到此搜索結(jié)束。由此得到深度優(yōu)先搜索遍歷圖的結(jié)點序列為：v0v1v3v6v4v2v5圖7-18 無向圖深度優(yōu)先搜索示意顯然，深度優(yōu)先搜索遍歷圖的過程是一個遞歸過程，我們可以用遞歸算法來實

20、現(xiàn)。在算法中為了避免在訪問過某頂點后又沿著某條回路回到該頂點這種重復訪問的情況出現(xiàn)，就必須在圖的遍歷過程中對每一個訪問過的頂點進行標識，這樣才可以避免一個頂點被重復訪問的情況出現(xiàn)。所以，我們在遍歷算法中對n個頂點的圖設(shè)置了一個長度為n的訪問標志數(shù)組visitedn，每個數(shù)組元素被初始化0，一旦某個頂點i被訪問則相應(yīng)的visitedi就置為1來做為訪問過的標志。對以鄰接表為存儲結(jié)構(gòu)的圖（可為非連通圖）進行深度優(yōu)先搜索的程序如下：#include<stdio.h>#include<stdlib.h>#define MAXSIZE 30typedef struct node

21、/鄰接表結(jié)點 int adjvex; /鄰接點域 struct node *next; /指向下一個鄰接邊結(jié)點的指針域EdgeNode; /鄰接表結(jié)點類型typedef struct vnode /頂點表結(jié)點 int vertex; /頂點域 EdgeNode *firstedge; /指向鄰接表第一個鄰接邊結(jié)點的指針域VertexNode; /頂點表結(jié)點類型void CreatAdjlist(VertexNode g,int e,int n)/建立無向圖的鄰接表，n為頂點數(shù)，e為邊數(shù)，g存儲n個頂點表結(jié)點 EdgeNode *p; int i,j,k; printf("Input

22、date of vetex(0n-1);n"); for(i=0;i<n;i+) /建立有n個頂點的頂點表 gi.vertex=i; /讀入頂點i信息 gi.firstedge=NULL; /初始化指向頂點i的鄰接表表頭指針 for(k=1;k<=e;k+) /輸入e條邊 printf("Input edge of(i,j): "); scanf("%d,%d",&i,&j); p=(EdgeNode *)malloc(sizeof(EdgeNode); p->adjvex=j; /在頂點vi的鄰接表中添加鄰接

23、點為j的結(jié)點 p->next=gi.firstedge; /插入是在鄰接表表頭進行的 gi.firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode); p->adjvex=i; /在頂點vj的鄰接表中添加鄰接點為i的結(jié)點 p->next=gj.firstedge; /插入是在鄰接表表頭進行的 gj.firstedge=p; int visitedMAXSIZE; /MAXSIZE為大于或等于無向圖頂點個數(shù)的常量void DFS(VertexNode g,int i) EdgeNode *p; printf("%4d&quo

24、t;,gi.vertex); /輸出頂點i信息，即訪問頂點i visitedi=1; /置頂點i為訪問過標志 p=gi.firstedge; /根據(jù)頂點i的指針firstedge查找其鄰接表的第一個鄰接邊結(jié)點 while(p!=NULL) /當鄰接邊結(jié)點不為空時 if(!visitedp->adjvex) /如果鄰接的這個邊結(jié)點未被訪問過 DFS(g,p->adjvex); /對這個邊結(jié)點進行深度優(yōu)先搜索 p=p->next; /查找頂點i的下一個鄰接邊結(jié)點 void DFSTraverse(VertexNode g,int n)/深度優(yōu)先搜索遍歷以鄰接表存儲的圖，其中g(shù)為頂

25、點表，n為頂點個數(shù) int i; for(i=0;i<n;i+) visitedi=0; /訪問標志置0 for(i=0;i<n;i+) /對n個頂點的圖查找未訪問過的頂點并由該頂點開始遍歷 if(!visitedi) /當visitedi等于0時即頂點i未訪問過 DFS(g,i); /從未訪問過的頂點i開始遍歷void main()int e,n; VertexNode gMAXSIZE; /定義頂點表結(jié)點類型數(shù)組gprintf("Input number of node:n"); /輸入圖中結(jié)點個數(shù)scanf("%d",&n);

26、printf("Input number of edge:n"); /輸入圖中邊的個數(shù)scanf("%d",&e); printf("Make adjlist:n");CreatAdjlist(g,e,n); /建立無向圖的鄰接表 printf("DFSTraverse:n"); DFSTraverse(g,n); /深度優(yōu)先遍歷以鄰接表存儲的無向圖printf("n");【說明】對圖15-1所示的無向圖，程序執(zhí)行如下：輸入： Input number of node:4Input nu

27、mber of edge:4Make adjlist:Input date of vetex(0n-1);Input edge of(i,j): 0,1Input edge of(i,j): 0,3Input edge of(i,j): 1,3Input edge of(i,j): 1,2輸出： DFSTraverse: 0 3 1 2Press any key to continue2.2 廣度優(yōu)先搜索廣度優(yōu)先搜索遍歷圖類似于樹的按層次遍歷。廣度優(yōu)先搜索的基本思想是：從圖中某頂點v出發(fā)，訪問頂點v后再依次訪問與v相鄰接的未曾訪問過的其余鄰接邊結(jié)點v1，v2，vk；接下來再按上述方法訪問與v1

28、鄰接的未曾訪問過的各鄰接邊結(jié)點、與v2鄰接的未曾訪問過的各鄰接邊結(jié)點、與vk鄰接的未曾訪問過的各鄰接邊結(jié)點；這樣逐層下去直至圖中的全部頂點都被訪問過。廣度優(yōu)先搜索遍歷圖的特點是盡可能先進行橫向搜索，即先訪問的頂點其鄰接邊結(jié)點也先訪問，后訪問的頂點其鄰接邊結(jié)點也后訪問。例如，對圖7-19所示的無向圖進行廣度優(yōu)先搜索遍歷，首先訪問v0，然后訪問v0未被訪問的鄰接邊結(jié)點v1和v3（注意，先是v1然后才是v3），接下來訪問v1未被訪問的鄰接邊結(jié)點v4，再訪問v3未被訪問鄰接邊結(jié)點v2（v3的鄰接邊結(jié)點v4已被訪問過）。此時，圖中所有頂點都被訪問過即完成了圖的遍歷，所得到的頂點訪問序列為：v0v1v3v

29、4v2為了實現(xiàn)圖的廣度優(yōu)先搜索，必須引入隊列結(jié)構(gòu)來保存已訪問過的頂點序列；即從指定的頂點開始，每訪問一個頂點就同時使該頂點進入隊尾；然后由隊頭取出一個頂點并訪問該頂點的所有未被訪問過的鄰接邊結(jié)點并且使該鄰接邊結(jié)點進入隊尾，如此進行下去直到隊空時為止，則圖中所有由開始頂點所能到達的全部頂點均已訪問過。對以鄰接表為存儲結(jié)構(gòu)的圖進行廣度優(yōu)先搜索的程序如下：#include<stdio.h>#include<stdlib.h>#define MAXSIZE 30typedef struct node1 /鄰接表結(jié)點 int adjvex; /鄰接點域 struct node1

30、*next; /指向下一個鄰接邊結(jié)點的指針域EdgeNode; /鄰接表結(jié)點類型typedef struct vnode /頂點表結(jié)點 int vertex; /頂點域 EdgeNode *firstedge; /指向鄰接表第一個鄰接邊結(jié)點的指針域VertexNode; /頂點表結(jié)點類型void CreatAdjlist(VertexNode g,int e,int n)/建立無向圖的鄰接表，n為頂點數(shù)，e為邊數(shù)，g存儲n個頂點表結(jié)點 EdgeNode *p; int i,j,k; printf("Input date of vetex(0n-1);n"); for(i=0

31、;i<n;i+) /建立有n個頂點的頂點表 gi.vertex=i; /讀入頂點i信息 gi.firstedge=NULL; /初始化指向頂點i的鄰接表表頭指針 for(k=1;k<=e;k+) /輸入e條邊 printf("Input edge of(i,j): "); scanf("%d,%d",&i,&j); p=(EdgeNode *)malloc(sizeof(EdgeNode); p->adjvex=j; /在頂點vi的鄰接表中添加鄰接點為j的結(jié)點 p->next=gi.firstedge; /插入是在

32、鄰接表表頭進行的 gi.firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode); p->adjvex=i; /在頂點vj的鄰接表中添加鄰接點為i的結(jié)點 p->next=gj.firstedge; /插入是在鄰接表表頭進行的 gj.firstedge=p; typedef struct node int data; struct node *next;QNode; /鏈隊列結(jié)點的類型typedef struct QNode *front,*rear; /將頭、尾指針納入到一個結(jié)構(gòu)體的鏈隊列LQueue;void Init_LQueue(L

33、Queue *q) /創(chuàng)建一個帶頭結(jié)點的空隊列 QNode *p; *q=(LQueue *)malloc(sizeof(LQueue);/申請帶頭、尾指針的結(jié)點 p=(QNode*)malloc(sizeof(QNode);/申請鏈隊列的頭結(jié)點 p->next=NULL; /頭結(jié)點的next指針置為空 (*q)->front=p; /隊頭指針指向頭結(jié)點 (*q)->rear=p; /隊尾指針指向頭結(jié)點int Empty_LQueue(LQueue *q) /判隊空 if(q->front=q->rear)/隊為空 return 1; else return 0;

34、void In_LQueue(LQueue *q,int x) /入隊 QNode *p; p=(QNode *)malloc(sizeof(QNode);/申請新鏈隊列結(jié)點 p->data=x; p->next=NULL;/新結(jié)點作為隊尾結(jié)點時其next域為空 q->rear->next=p; /將新結(jié)點*p鏈到原隊尾結(jié)點之后 q->rear=p; /使隊尾指針指向新的隊尾結(jié)點*pvoid Out_LQueue(LQueue *q,int *x) /出隊 QNode *p; if(Empty_LQueue(q) printf("Queue is emp

35、ty!n");/隊空，出隊失敗 else p=q->front->next;/指針p指向鏈隊列第一個數(shù)據(jù)結(jié)點（即隊頭結(jié)點） q->front->next=p->next; /頭結(jié)點的next指針指向鏈隊列第二個數(shù)據(jù)結(jié)點（即刪除第一個數(shù)據(jù)結(jié)點） *x=p->data;/將刪除的隊頭結(jié)點數(shù)據(jù)經(jīng)由x返回 free(p); if(q->front->next=NULL)/出隊后隊為空，則置為空隊列 q->rear=q->front; int visitedMAXSIZE; /MAXSIZE為大于或等于無向圖頂點個數(shù)的常量void B

36、FS(VertexNode g,LQueue *Q,int i)/廣度優(yōu)先搜索遍歷鄰接表存儲的圖，g為頂點表，Q為隊指針，i為第i個頂點 int j,*x=&j; EdgeNode *p; printf("%4d",gi.vertex); /輸出頂點i信息，即訪問頂點i visitedi=1; /置頂點i為訪問過標志 In_LQueue(Q,i); /頂點i入隊Q while(!Empty_LQueue(Q) /當隊Q非空時 Out_LQueue(Q,x); /隊頭頂點出隊并送j（暫記為頂點j） p=gj.firstedge;/根據(jù)頂點j的表頭指針查找其鄰接表的第一

37、個鄰接邊結(jié)點 while(p!=NULL) if(!visitedp->adjvex) /如果鄰接的這個邊結(jié)點未被訪問過 printf("%4d",gp->adjvex.vertex);/輸出這個鄰接邊結(jié)點的頂點信息 visitedp->adjvex=1; /置該鄰接邊結(jié)點為訪問過標志 In_LQueue(Q,p->adjvex); /將該鄰接邊結(jié)點送入隊Q p=p->next; /在頂點j 的鄰接表中查找j的下一個鄰接邊結(jié)點 void main()int e,n; VertexNode gMAXSIZE; /定義頂點表結(jié)點類型數(shù)組gLQueu

38、e *q;printf("Input number of node:n"); /輸入圖中結(jié)點個數(shù)scanf("%d",&n); printf("Input number of edge:n"); /輸入圖中邊的個數(shù)scanf("%d",&e); printf("Make adjlist:n");CreatAdjlist(g,e,n); /建立無向圖的鄰接表 Init_LQueue(&q); /隊列q初始化printf("BFSTraverse:n");

39、 BFS(g,q,0); /廣度優(yōu)先遍歷以鄰接表存儲的無向圖printf("n");【說明】對圖15-1所示的無向圖，程序執(zhí)行如下：輸入： Input number of node:4Input number of edge:4Make adjlist:Input date of vetex(0n-1);Input edge of(i,j): 0,1Input edge of(i,j): 0,3Input edge of(i,j): 1,3Input edge of(i,j): 1,2輸出： BFSTraverse: 0 3 1 2Press any key to cont

40、inue2.3圖的連通性問題 判斷一個圖的連通性是圖的應(yīng)用問題，我們可以利用圖的遍歷算法來求解這一問題。1. 無向圖的連通性 在對無向圖進行遍歷時，對連通圖僅需從圖中任一頂點出發(fā)進行深度優(yōu)先搜索或廣度優(yōu)先搜索，就可訪問到圖中的所有頂點；對于非連通圖，則需要由不連通的多個頂點開始進行搜索，且每一次從一個新的頂點出發(fā)進行搜索過程中得到的頂點訪問序列，就是包含該出發(fā)頂點的這個連通分量中的頂點集。 因此，要想判斷一個無向圖是否為連通圖，或者有幾個連通分量，則可增加一個計數(shù)變量count并設(shè)其初值為0，在深度優(yōu)先搜索算法DFSTraverse函數(shù)里的第二個for循環(huán)中，每調(diào)用一次DFS就給count增1

41、；這樣當算法執(zhí)行結(jié)束時的count值即為連通分量的個數(shù)。 無向圖連通分量的計算程序如下#include<stdio.h>#include<stdlib.h>#define MAXSIZE 30typedef struct node1 /鄰接表結(jié)點 int adjvex; /鄰接點域 struct node1 *next; /指向下一個鄰接邊結(jié)點的指針域EdgeNode; /鄰接表結(jié)點類型typedef struct vnode /頂點表結(jié)點 int vertex; /頂點域 EdgeNode *firstedge; /指向鄰接表第一個鄰接邊結(jié)點的指針域VertexNod

42、e; /頂點表結(jié)點類型void CreatAdjlist(VertexNode g,int e,int n)/建立無向圖的鄰接表，n為頂點數(shù)，e為邊數(shù)，g存儲n個頂點表結(jié)點 EdgeNode *p; int i,j,k; printf("Input date of vetex(0n-1);n"); for(i=0;i<n;i+) /建立有n個頂點的頂點表 gi.vertex=i; /讀入頂點i信息 gi.firstedge=NULL; /初始化指向頂點i的鄰接表表頭指針 for(k=1;k<=e;k+) /輸入e條邊 printf("Input edg

43、e of(i,j): "); scanf("%d,%d",&i,&j); p=(EdgeNode *)malloc(sizeof(EdgeNode); p->adjvex=j; /在頂點vi的鄰接表中添加鄰接點為j的結(jié)點 p->next=gi.firstedge; /插入是在鄰接表表頭進行的 gi.firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode); p->adjvex=i; /在頂點vj的鄰接表中添加鄰接點為i的結(jié)點 p->next=gj.firstedge; /插入是在鄰

44、接表表頭進行的 gj.firstedge=p; int visitedMAXSIZE; /MAXSIZE為大于或等于無向圖頂點個數(shù)的常量void DFS(VertexNode g,int i) /圖的深度優(yōu)先遍歷 EdgeNode *p; printf("%4d",gi.vertex); /輸出頂點i信息，即訪問頂點i visitedi=1; /置頂點i為訪問過標志 p=gi.firstedge; /根據(jù)頂點i的指針firstedge查找其鄰接表的第一個鄰接邊結(jié)點 while(p!=NULL) /當鄰接邊結(jié)點不為空時 if(!visitedp->adjvex) /如果

45、鄰接的這個邊結(jié)點未被訪問過 DFS(g,p->adjvex); /對這個邊結(jié)點進行深度優(yōu)先搜索 p=p->next; /查找頂點i的下一個鄰接邊結(jié)點 int count=0; /連通分量計數(shù)count初值為0void ConnectEdge(VertexNode g,int n) /求圖的連通分量/深度優(yōu)先搜索遍歷以鄰接表存儲的圖，其中g(shù)為頂點表，n為頂點個數(shù) int i; for(i=0;i<n;i+) visitedi=0; /訪問標志置0 for(i=0;i<n;i+)/對n個頂點的圖查找未訪問過的頂點并由該頂點開始遍歷 if(!visitedi) /當visit

46、edi等于0時即頂點i未訪問過 DFS(g,i); /從未訪問過的頂點i開始遍歷 count+; /訪問過一個連通分量則count加1 void main()int e,n; VertexNode gMAXSIZE; /定義頂點表結(jié)點類型數(shù)組gprintf("Input number of node:n"); /輸入圖中結(jié)點個數(shù)scanf("%d",&n); printf("Input number of edge:n"); /輸入圖中邊的個數(shù)scanf("%d",&e); printf("

47、;Make adjlist:n");CreatAdjlist(g,e,n); /建立無向圖的鄰接表printf("DFSTraverse:n"); ConnectEdge(g,n); /求圖的連通分量printf("nNumber of connect is %dn",count); /輸出連通分量【說明】圖15-2無向圖示意對圖15-2所示的無向圖，程序執(zhí)行如下：輸入： Input number of node:8Input number of edge:7Make adjlist:Input date of vetex(0n-1);Inpu

48、t edge of(i,j): 0,1Input edge of(i,j): 0,2Input edge of(i,j): 0,4Input edge of(i,j): 1,3Input edge of(i,j): 2,3Input edge of(i,j): 5,6Input edge of(i,j): 5,7輸出： DFSTraverse: 0 4 2 3 1 5 7 6Number of connect is 2Press any key to continue 3 生成樹與最小生成樹 3.1 生成樹和生成森林 對于連通的無向圖和強連通的有向圖G=(V, E)，如果從圖中任一頂點出發(fā)遍歷

49、圖時，必然會將圖中邊的集合E(G)分別為兩個子集T(G)和B(G)；其中，T(G)為遍歷中所經(jīng)過的邊的集合，而B(G)為遍歷中未經(jīng)過的邊的集合。顯然，T(G)和圖G中所有頂點一起構(gòu)成了連通圖G的一個極小連通子圖；也即，G'=(V, T)是G的一個子圖。按照生成樹的定義，圖G'為圖G的一棵生成樹。 連通圖的生成樹不是唯一的。從不同頂點出發(fā)進行圖的遍歷，或者雖然從圖的同一個頂點出發(fā)但圖的存儲結(jié)構(gòu)不同都可能得到不同的生成樹。當一個連通圖具有n個頂點時，該連通圖的生成樹就包含圖中的全部n個頂點但卻僅有連接這n個頂點的n-1條邊。生成樹不具有回路，在生成樹G'=(V, T)中任意添加一條屬于B(G)的邊則必定產(chǎn)生回路。 我們將由深度優(yōu)先搜索遍歷圖所得到的生成樹稱為深度優(yōu)先生成樹，將由廣度優(yōu)先搜索遍歷圖所得到的生成樹稱為廣度優(yōu)先生成樹。圖7-22(b)和圖7-22(c)就是由圖7-22(a)所得到的深度優(yōu)先生成樹和廣度優(yōu)先生成樹；圖中