圖的基本操作與實(shí)現(xiàn)的課程設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目： 圖的基本操作與實(shí)現(xiàn)專 業(yè) 班 級(jí) 學(xué) 生 學(xué) 號(hào) 指導(dǎo)教師 起止時(shí)間 年 學(xué)期目 錄1.問(wèn)題描述：實(shí)現(xiàn)圖的一些基本操作32.基本要求：3(2)求每個(gè)頂點(diǎn)的度,輸出結(jié)果；33.測(cè)試數(shù)據(jù)：34.算法思想：3(1)自選存儲(chǔ)結(jié)構(gòu)創(chuàng)建一個(gè)圖：3(2)求每個(gè)頂點(diǎn)的度：3(3)圖的深度優(yōu)先遍歷：4(4)圖的廣度優(yōu)先遍歷：4(5)判斷有向圖的強(qiáng)連通性：4(6)用鄰接矩陣的信息生成鄰接表：46.數(shù)據(jù)結(jié)構(gòu)：57.功能模塊圖78.源程序：89.心得體會(huì)：281.問(wèn)題描述：實(shí)現(xiàn)圖的一些基本操作2.基本要求：(1)自選存儲(chǔ)結(jié)構(gòu),輸入含n個(gè)頂點(diǎn)（用字符表示頂點(diǎn)）和e條邊的圖G；(2)求每個(gè)

2、頂點(diǎn)的度,輸出結(jié)果；(3)指定任意頂點(diǎn)x為初始頂點(diǎn),對(duì)圖G作DFS遍歷,輸出DFS頂點(diǎn)序列(提示:使用一個(gè)棧實(shí)現(xiàn)DFS)；(4)指定任意頂點(diǎn)x為初始頂點(diǎn),對(duì)圖G作BFS遍歷,輸出BFS頂點(diǎn)序列(提示:使用一個(gè)隊(duì)列實(shí)現(xiàn)BFS)；(5)輸入頂點(diǎn)x,查找圖G:若存在含x的頂點(diǎn),則刪除該結(jié)點(diǎn)及與之相關(guān)連的邊,并作DFS遍歷(執(zhí)行操作3)；否則輸出信 息“無(wú)x”；(6)判斷圖G是否是連通圖，輸出信息“YES”/“NO”；(7)如果選用的存儲(chǔ)結(jié)構(gòu)是鄰接矩陣,則用鄰接矩陣的信息生成圖G的鄰接表,即復(fù)制圖G,然再執(zhí)行操作(2)；反之亦然。3.測(cè)試數(shù)據(jù)：有向圖的頂點(diǎn)數(shù)n和有向圖的邊數(shù)e由用戶從鍵盤敲入4.算法思

3、想：(1)自選存儲(chǔ)結(jié)構(gòu)創(chuàng)建一個(gè)圖：通過(guò)用戶從鍵盤敲入的兩個(gè)數(shù)值分別確定圖的頂點(diǎn)數(shù)和邊數(shù)，選擇鄰接矩陣存儲(chǔ)結(jié)構(gòu)將圖的結(jié)點(diǎn)信息存儲(chǔ)在一個(gè)順序表中，圖的邊信息存儲(chǔ)在一個(gè)二維數(shù)組中。(2)求每個(gè)頂點(diǎn)的度：1.鄰接矩陣存儲(chǔ)結(jié)構(gòu)下求每個(gè)頂點(diǎn)的度：利用圖的鄰接矩陣，每個(gè)頂點(diǎn)所在行和所在列的邊的權(quán)值如果存在則該頂點(diǎn)的度+1，依次算出每個(gè)頂點(diǎn)的度，并且記錄在一個(gè)數(shù)組中輸出。2.鄰接表存儲(chǔ)結(jié)構(gòu)下求每個(gè)頂點(diǎn)的度：定義一個(gè)鄰接邊指針循環(huán)指向頂點(diǎn)的鄰接邊單鏈表頭結(jié)點(diǎn)，當(dāng)結(jié)點(diǎn)不空時(shí)，該頂點(diǎn)的出度+1,鄰接邊弧頭結(jié)點(diǎn)的入度+1，依次求出每個(gè)頂點(diǎn)的出度和入度之和就為該頂點(diǎn)的度。(3)圖的深度優(yōu)先遍歷：采取鄰接矩陣結(jié)構(gòu)，指定任

4、意頂點(diǎn)x為初始頂點(diǎn)1.訪問(wèn)結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v已訪問(wèn)；2.查找結(jié)點(diǎn)v的第一個(gè)鄰接結(jié)點(diǎn)w；3.若結(jié)點(diǎn)v的鄰接結(jié)點(diǎn)w存在，則繼續(xù)執(zhí)行，否則算法結(jié)束；4.若結(jié)點(diǎn)w尚未被訪問(wèn)，則遞歸訪問(wèn)結(jié)點(diǎn)w；5.查找結(jié)點(diǎn)v的w鄰接結(jié)點(diǎn)的下一個(gè)鄰接結(jié)點(diǎn)w,轉(zhuǎn)到步驟3。(4)圖的廣度優(yōu)先遍歷：采取鄰接矩陣結(jié)構(gòu)，指定任意頂點(diǎn)x為初始頂點(diǎn)，利用順序循環(huán)隊(duì)列以保持訪問(wèn)過(guò)的結(jié)點(diǎn)的順序1.首先訪問(wèn)初始結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v為已訪問(wèn)；2.結(jié)點(diǎn)v入隊(duì)列；3.當(dāng)隊(duì)列非空時(shí)則繼續(xù)執(zhí)行，否則算法結(jié)束；4.出隊(duì)列取得隊(duì)頭結(jié)點(diǎn)u；5.查找u的第一個(gè)鄰接結(jié)點(diǎn)w；6.若u的鄰接結(jié)點(diǎn)w不存在則轉(zhuǎn)到步驟3，否則循環(huán)執(zhí)行下列步驟：6.1若結(jié)點(diǎn)w尚未被訪問(wèn)，則

5、訪問(wèn)結(jié)點(diǎn)w并標(biāo)記結(jié)點(diǎn)w為已訪問(wèn)；6.2結(jié)點(diǎn)w入隊(duì)列；6.3查找結(jié)點(diǎn)u的w鄰接結(jié)點(diǎn)的下一個(gè)鄰接結(jié)點(diǎn)w，轉(zhuǎn)到步驟6 。(5)判斷有向圖的強(qiáng)連通性：采取鄰接表結(jié)構(gòu)，在圖中尋找一個(gè)包含所有頂點(diǎn)且首尾相連的環(huán)，若這樣的環(huán)存在，則該圖為強(qiáng)連通圖，否則不為強(qiáng)連通圖。(6)用鄰接矩陣的信息生成鄰接表：定義一個(gè)鄰接表的邊信息結(jié)構(gòu)體，將鄰接矩陣的邊信息轉(zhuǎn)換成鄰接表的邊信息存儲(chǔ)到鄰接邊的單鏈表中。5.模塊劃分：mian():主函數(shù)模塊。在主函數(shù)模塊中調(diào)用以下函數(shù)：(1) void CreatGraph(AdjMGraph *G,DataType v,int n,RowColWeight E,int e)：創(chuàng)建一個(gè)鄰

6、接矩陣存儲(chǔ)結(jié)構(gòu)的圖；(2) void Print(AdjMGraph *G)：輸出圖的鄰接矩陣；(3) void MVertices(AdjMGraph *G,DataType a)：求出鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的每個(gè)頂點(diǎn)的度；(4) void CreatLGraph(AdjLGraph *G,DataType v,int n,RowCol d,int e)：用鄰接矩陣的信息生成鄰接表；(5) void LVertices(AdjLGraph *G,DataType a)：求出鄰接表存儲(chǔ)結(jié)構(gòu)下圖的每個(gè)頂點(diǎn)的度；(6) int LianTong(AdjLGraph *G,DataType a)：判斷

7、有向圖的強(qiáng)連通性；(7) void DepthFirstSearch(AdjMGraph G,void Visit(DataType item)：對(duì)圖作DFS遍歷,輸出DFS頂點(diǎn)序列；(8) void BroadFirstSearch(AdjMGraph G,void Visit(DataType item)：對(duì)圖作BFS遍歷,輸出BFS頂點(diǎn)序列；(9) int ChaZhao(AdjMGraph *G,int v)：查找頂點(diǎn)v；(10) void MDelete(AdjMGraph *G,int v)：刪除查找到的結(jié)點(diǎn)v并刪除該結(jié)點(diǎn)及與之相關(guān)的邊；6.數(shù)據(jù)結(jié)構(gòu)：(1)有向圖頂點(diǎn)的數(shù)據(jù)類型Da

8、taType 定義如下： typedef int DataType ；(2)鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的結(jié)構(gòu)體定義如下：typedef structSeqList Vertices； /存放結(jié)點(diǎn)的順序表int edgeMaxVerticesMaxVertices； /存放邊的鄰接矩陣int numOfEdges； /邊的條數(shù)AdjMGraph； /邊的結(jié)構(gòu)體定義(3)鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的邊信息結(jié)構(gòu)體定義如下：typedef structint row； /行下標(biāo)int col； /列下標(biāo)int weight； /權(quán)值RowColWeight； /邊信息結(jié)構(gòu)體定義(4)鄰接表存儲(chǔ)結(jié)構(gòu)下圖的結(jié)構(gòu)體定義

9、如下：typedef struct Node int dest； /鄰接邊的弧頭結(jié)點(diǎn)序號(hào)struct Node *next； Edge； /鄰接邊單鏈表的結(jié)點(diǎn)結(jié)構(gòu)體typedef structDataType data； /結(jié)點(diǎn)數(shù)據(jù)元素 int sorce； /鄰接邊的弧尾結(jié)點(diǎn)序號(hào)Edge *adj； /鄰接邊的頭指針AdjLHeight； /數(shù)組的數(shù)據(jù)元素類型結(jié)構(gòu)體typedef structAdjLHeight aMaxVertices； /鄰接表數(shù)組int numOfVerts； /結(jié)點(diǎn)個(gè)數(shù)int numOfEdges； /邊個(gè)數(shù)AdjLGraph； /鄰接表結(jié)構(gòu)體(5)鄰接表存儲(chǔ)結(jié)構(gòu)下

10、圖的邊信息結(jié)構(gòu)體定義如下：typedef structint row； /行下標(biāo)int col； /列下標(biāo)RowCol； /邊信息結(jié)構(gòu)體定義(6)順序循環(huán)隊(duì)列的結(jié)構(gòu)體定義如下：typedef struct DataType queueMaxQueueSize；int rear；int front；int count；SeqCQueue；(7)順序表的結(jié)構(gòu)體定義如下：typedef structDataType listMaxSize；int size；SeqList；7.功能模塊圖：main（）PrintCreatGraphMVerticesDepthFirstSearchCreatLGrap

11、hMDeleteBroadFirstSearchChaZhaoLianTongLVerticesInsertVertexInsertEdgeLInsertVertexLAdjInitiateDeleteVertenDeleteEdgeLInsertEdgeInitiate8.源程序：源程序存放在八個(gè)文件夾中，文件SeqList.h是順序表的結(jié)構(gòu)體定義和操作函數(shù)，文件SeqCQueue.h是順序循環(huán)隊(duì)列的結(jié)構(gòu)體定義和操作函數(shù)，文件AdjMGraph.h是鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的結(jié)構(gòu)體定義和操作函數(shù)，文件AdjMGraphCreate.h是鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的創(chuàng)建函數(shù)，文件AdjLGraph.h是

12、鄰接表存儲(chǔ)結(jié)構(gòu)下圖的結(jié)構(gòu)體定義和操作函數(shù)，文件AdjLGraphCreate.h是鄰接表存儲(chǔ)結(jié)構(gòu)下圖的創(chuàng)建函數(shù)，文件AdjMGraphTraverse.h是鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷操作函數(shù)，文件圖的基本操作與實(shí)現(xiàn).c是主函數(shù)。(1)/* 文件SeqList.h */typedef structDataType listMaxSize;int size;SeqList;void ListInitiate(SeqList *L)L-size=0;int ListLength(SeqList L)return L.size;int ListInsert(SeqList *L,

13、int i,DataType x)int j;if(L-size=MaxSize)printf(數(shù)組已滿無(wú)法插入！n);return 0;else if(iL-size)printf(參數(shù)不合法！n);return 0;elsefor(j=L-size;ji;i-)L-listj=L-listj-1;L-listi=x;L-size+;return 1;int ListDelete(SeqList *L,int i,DataType *x)int j;if(L-size=0)printf(順序表已空無(wú)數(shù)據(jù)元素可刪！n);return 0;else if(iL-size-1)printf(參數(shù)i

14、不合法！n);return 0;else*x=L-listi;for(j=i+1;jsize-1;j+)L-listj-1=L-listj;L-size-;return 1;int ListGet(SeqList L,int i,DataType *x)if(iL.size-1)printf(參數(shù)i不合法！n);return 0;else*x=L.listi;return 1;(2)/* 文件SeqCQueue.h */typedef struct DataType queueMaxQueueSize;int rear;int front;int count;SeqCQueue;void Qu

15、eueInitiate(SeqCQueue *Q)Q-rear=0;Q-front =0;Q-count =0;int QueueNotEmpty(SeqCQueue Q)if(Q.count !=0) return 1;else return 0;int QueueAppend(SeqCQueue *Q,DataType x)if(Q-count0&Q-rear=Q-front)printf(隊(duì)列已滿無(wú)法插入!);return 0;else Q-queue Q-rear=x;Q-rear =(Q-rear +1)%MaxQueueSize;Q-count +;return 1;int Que

16、ueDelete(SeqCQueue *Q,DataType *d)if(Q-count =0)printf(隊(duì)列已空無(wú)數(shù)據(jù)出隊(duì)列!n);return 0;else*d=Q-queueQ-front; Q-front=(Q-front+1)%MaxQueueSize;Q-count -;return 1;int QueueGet(SeqCQueue Q,DataType*d)if(Q.count =0)printf(隊(duì)列已空無(wú)數(shù)據(jù)出隊(duì)列!n);return 0;else*d=Q.queue Q.front ;return 1;(3)/* 文件AdjMGraph.h*/#includeSeqLi

17、st.htypedef structSeqList Vertices; /存放結(jié)點(diǎn)的順序表int edgeMaxVerticesMaxVertices; /存放邊的鄰接矩陣int numOfEdges; /邊的條數(shù)AdjMGraph; /邊的結(jié)構(gòu)體定義void Initiate(AdjMGraph *G,int n) /初始化int i,j;for(i=0;in;i+)for(j=0;jedgeij=0;elseG-edgeij=MaxWeight;G-numOfEdges=0; /邊的條數(shù)置為0ListInitiate(&G-Vertices); /順序表初始化void InsertVert

18、ex(AdjMGraph *G,DataType vertex) /在圖G中插入結(jié)點(diǎn)vertexListInsert(&G-Vertices,G-Vertices.size,vertex); /順序表尾插入void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)/在圖G中插入邊,邊的權(quán)為weightif(v1G-Vertices.size|v2G-Vertices.size)printf(參數(shù)v1或v2越界出錯(cuò)!n);exit(1);G-edgev1v2=weight;G-numOfEdges+;void DeleteEdge(AdjMGra

19、ph *G,int v1,int v2) /在圖中刪除邊if(v1G-Vertices.size|v2G-Vertices.size|v1=v2)printf(參數(shù)v1或v2越界出錯(cuò)!n);exit(1);if(G-edgev1v2=MaxWeight|v1=v2)printf(該邊不存在!n);exit(0);G-edgev1v2=MaxWeight;G-numOfEdges-;void DeleteVerten(AdjMGraph *G,int v) /刪除結(jié)點(diǎn)vint n=ListLength(G-Vertices),i,j; DataType x;for(i=0;in;i+) /計(jì)算刪

20、除后的邊數(shù)for(j=0;jedgeij0&G-edgeijnumOfEdges-; /計(jì)算被刪除邊f(xié)or(i=v;in;i+) /刪除第v行for(j=0;jedgeij=G-edgei+1j;for(i=0;in;i+) /刪除第v列for(j=v;jedgeij=G-edgeij+1;ListDelete(&G-Vertices,v,&x); /刪除結(jié)點(diǎn)vint GetFistVex(AdjMGraph *G,int v) /在圖G中尋找序號(hào)為v的結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)/如果這樣的鄰接結(jié)點(diǎn)存在，返回該鄰接結(jié)點(diǎn)的序號(hào)；否則，返回-1int col;if(vG-Vertices.size)pr

21、intf(參數(shù)v1越界出錯(cuò)!n);exit(1);for(col=0;colVertices.size;col+)if(G-edgevcol0&G-edgevcolMaxWeight)return col;return -1;int GetNextVex(AdjMGraph*G,int v1,int v2)/在圖中尋找v1結(jié)點(diǎn)的鄰接結(jié)點(diǎn)v2的下一個(gè)鄰接結(jié)點(diǎn)/如果這樣的結(jié)點(diǎn)存在，返回該鄰接結(jié)點(diǎn)的序號(hào)；否則，返回-1/v1和v2都是相應(yīng)結(jié)點(diǎn)的序號(hào)int col;if(v1G-Vertices.size|v2G-Vertices.size)printf(參數(shù)v1或v2越界出錯(cuò)!n);exit(1);

22、 for(col=v2+1;colVertices.size;col+)if(G-edgev1col0&G-edgev1colMaxWeight)return col;return -1;/輸出圖G的鄰接矩陣void Print(AdjMGraph *G) int i,j;for(i=0;iVertices.size;i+)for(j=0;jVertices.size;j+)printf(%6d ,G-edgeij);printf(n);/鄰接矩陣存儲(chǔ)結(jié)構(gòu)下求出每個(gè)頂點(diǎn)的度并輸出void MVertices(AdjMGraph *G,DataType a) int i,j,m;DataType

23、 bMaxVertices;/用數(shù)組b記錄相應(yīng)結(jié)點(diǎn)的度f(wàn)or(i=0;iVertices.size;i+)bi=0; /置0printf(鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的頂點(diǎn)的度為:n);for(m=0;mVertices.size;m+) /求出每個(gè)結(jié)點(diǎn)的度f(wàn)or(i=0;iVertices.size;i+)for(j=0;jVertices.size;j+)if(i=m&G-edgeij0&G-edgeijMaxWeight)/求出鄰接矩陣第i行權(quán)值存在的邊的個(gè)數(shù),當(dāng)邊存在時(shí),bm加1bm+;if(j=m&i!=m&G-edgeij0&G-edgeijMaxWeight)/求出鄰接矩陣第j列權(quán)值存在

24、的邊的個(gè)數(shù),當(dāng)邊存在時(shí)，bm加1bm+;printf(頂點(diǎn)%d的度為:%dn,am,bm); /查找圖G中是否存在點(diǎn)vint ChaZhao(AdjMGraph *G,int v) if(0=v&vVertices.size)printf(存在頂點(diǎn)%dn,v);return 1;elseprintf(不存在頂點(diǎn)%dn,v);return 0;/刪除查找到的結(jié)點(diǎn)v并刪除該結(jié)點(diǎn)及與之相關(guān)的邊void MDelete(AdjMGraph *G,int v)int i;for(i=0;iVertices.size;i+)if(G-edgevi0&G-edgeviMaxWeight)/當(dāng)鄰接矩陣的第v行

25、有邊存在時(shí),刪除邊DeleteEdge(G,v,i);if(G-edgeiv0&G-edgeivMaxWeight)/當(dāng)鄰接矩陣的第j行有邊存在時(shí),刪除邊DeleteEdge(G,i,v);DeleteVerten(G,v);/刪除結(jié)點(diǎn)v(4)/* 文件AdjMGraphCreate.h */typedef structint row; /行下標(biāo)int col; /列下標(biāo)int weight; /權(quán)值RowColWeight; /邊信息結(jié)構(gòu)體定義void CreatGraph(AdjMGraph *G,DataType v,int n,RowColWeight E,int e)/在圖G中插入n

26、個(gè)結(jié)點(diǎn)信息v和e條邊信息Eint i,k;Initiate(G,n); /結(jié)點(diǎn)順序表初始化for(i=0;in;i+)InsertVertex(G,vi); /結(jié)點(diǎn)插入for(k=0;knumOfVerts=0;G-numOfEdges=0;for(i=0;iai.sorce=i;G-ai.adj=NULL;/撤銷操作函數(shù)void LAdjDestroy(AdjLGraph *G)/撤銷圖G中的所有鄰接邊單鏈表int i;Edge *p,*q;for(i=0;inumOfVerts;i+)p=G-ai.adj;while(p!=NULL)q=p-next;free(p);p=q;/插入結(jié)點(diǎn)操作

27、函數(shù)void LInsertVertex(AdjLGraph *G,int i,DataType vertex)/在圖G中的第i(0=i=0&iai.data=vertex; /存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)元素vertexG-numOfVerts+; /個(gè)數(shù)加1elseprintf(結(jié)點(diǎn)越界);/插入邊操作函數(shù)void LInsertEdge(AdjLGraph *G,int v1,int v2)/在圖G中加入邊的信息Edge *p; /定義一個(gè)鄰接邊指針if(v1=G-numOfVerts|v2=G-numOfVerts)printf(參數(shù)v1或v2越界出錯(cuò));exit(0);p=(Edge *)mallo

28、c(sizeof(Edge); /申請(qǐng)鄰接邊單鏈表結(jié)點(diǎn)空間p-dest=v2; /置鄰接邊弧頭序號(hào)p-next=G-av1.adj; /新結(jié)點(diǎn)插入單鏈表的表頭G-av1.adj=p; /頭指針指向新的單鏈表表頭G-numOfEdges+; /邊數(shù)個(gè)數(shù)加1 /刪除邊操作函數(shù)void LDeleteEdge(AdjLGraph *G,int v1,int v2)/刪除圖G中的邊信息Edge *curr,*pre;if(v1=G-numOfVerts|v2=G-numOfVerts)printf(參數(shù)v1或v2越界出錯(cuò)!);exit(0);pre=NULL;curr=G-av1.adj;while(

29、curr!=NULL&curr-dest!=v2)/在v1結(jié)點(diǎn)的鄰接邊單鏈表中查找v2結(jié)點(diǎn)pre=curr;curr=curr-next;/刪除表示鄰接邊的結(jié)點(diǎn)if(curr!=NULL&curr-dest=v2&pre=NULL) /當(dāng)鄰接邊的結(jié)點(diǎn)是單鏈表的第一個(gè)結(jié)點(diǎn)時(shí)G-av1.adj=curr-next;free(curr);G-numOfEdges-;else if(curr!=NULL&curr-dest=v2&pre!=NULL)/當(dāng)鄰接邊的結(jié)點(diǎn)不是單鏈表的第一個(gè)結(jié)點(diǎn)時(shí)pre-next=curr-next;free(curr);G-numOfEdges-;else/當(dāng)鄰接邊結(jié)點(diǎn)不存

30、在時(shí)printf(邊不存在時(shí));/取第一個(gè)鄰接結(jié)點(diǎn)int LGetFirstVex(AdjLGraph *G,int v)/取圖G中結(jié)點(diǎn)v的第一個(gè)鄰接結(jié)點(diǎn)/取到時(shí)返回該鄰接結(jié)點(diǎn)的對(duì)應(yīng)序號(hào)，否則返回-1Edge *p;if(vG-numOfVerts)printf(參數(shù)v1或v2越界出錯(cuò)!);exit(0);p=G-av.adj;if(p!=NULL)return p-dest; /返回該鄰接結(jié)點(diǎn)的對(duì)應(yīng)序號(hào)elsereturn -1; /返回-1/取下一個(gè)鄰接結(jié)點(diǎn)int LGetNextVex(AdjLGraph *G,int v1,int v2)/取圖G中結(jié)點(diǎn)v1的鄰接結(jié)點(diǎn)v2的下一個(gè)鄰接結(jié)點(diǎn)

31、/取到時(shí)返回該鄰接結(jié)點(diǎn)的對(duì)應(yīng)序號(hào)，否則返回-1Edge *p;if(v1G-numOfVerts|v2G-numOfVerts)printf(參數(shù)v1或v2越界出錯(cuò)!);exit(0);p=G-av1.adj;while(p!=NULL) /尋找結(jié)點(diǎn)v1的鄰接結(jié)點(diǎn)v2if(p-dest!=v2)p=p-next;continue;elsebreak;p=p-next; /p指向鄰接結(jié)點(diǎn)v2的下一個(gè)鄰接結(jié)點(diǎn)if(p!=NULL)return p-dest; /返回該鄰接結(jié)點(diǎn)的對(duì)應(yīng)序號(hào)elsereturn -1; /返回-1/鄰接表存儲(chǔ)下求每個(gè)頂點(diǎn)的度并輸出結(jié)果void LVertices(Adj

32、LGraph *G,DataType a)printf(鄰接表存儲(chǔ)結(jié)構(gòu)下的圖的頂點(diǎn)的度為:n);int OutDegreeMaxVertices,InDegreeMaxVertices;/定義一個(gè)出度和入度的數(shù)組int i;for(i=0;inumOfVerts;i+) /首先將出度和入度數(shù)組的每個(gè)成員都置0OutDegreei=0;InDegreei=0;Edge *p; /定義一個(gè)鄰接邊指針for(i=0;inumOfVerts;i+)p=G-ai.adj; /指針指向ai的鄰接邊單鏈表頭結(jié)點(diǎn)while(p!=NULL)/當(dāng)p所指向的鄰接邊結(jié)點(diǎn)不空時(shí)OutDegreei+; /出度加1In

33、Degreep-dest+; /鄰接邊弧頭結(jié)點(diǎn)的入度加1p=p-next; /p指向下一個(gè)鄰接邊結(jié)點(diǎn)for(i=0;inumOfVerts;i+) /輸出每個(gè)結(jié)點(diǎn)的度printf(頂點(diǎn)%d的度為:,ai);printf(%d,OutDegreei+InDegreei); /每個(gè)結(jié)點(diǎn)的度即出度與入度相加的和printf(n);/判斷有向圖G是否為強(qiáng)連通圖int LianTong(AdjLGraph *G,DataType a) int i,bMaxVertices,k=0;for(i=0;inumOfVerts;i+)bi=0;Edge *q,*p; /定義一個(gè)鄰接邊指針for(i=0;inum

34、OfVerts;i+)q=G-ai.adj;while(q!=NULL)bi+;q=q-next;for(i=0;inumOfVerts;i+)if(bi=1)k+;p=G-aG-numOfVerts-1.adj;if(k=G-numOfVerts&p-dest=a0)return 1;elsereturn 0;(6)/* 文件AdjLGraphCreate.h */typedef structint row; /行下標(biāo)int col; /列下標(biāo)RowCol; /邊信息結(jié)構(gòu)體定義void CreatLGraph(AdjLGraph *G,DataType v,int n,RowCol d,in

35、t e)int i,k;LAdjInitiate(G);for(i=0;in;i+)LInsertVertex(G,i,vi);for(k=0;ke;k+)LInsertEdge(G,dk.row,dk.col);(7)/* 文件AdjMGraphTraverse.h */void Visit(DataType item)printf(%d ,item);void DepthFSearch(AdjMGraph G,int v,int visited,void Visit(DataType item)/連通圖G以v為初始結(jié)點(diǎn)的訪問(wèn)操作為Visit()的深度優(yōu)先遍歷/數(shù)組visited標(biāo)記了相應(yīng)結(jié)

36、點(diǎn)是否已訪問(wèn)過(guò)，0表示未訪問(wèn)，1表示已訪問(wèn)int w;Visit(G.Vertices.listv); /訪問(wèn)結(jié)點(diǎn)vvisitedv=1; /置已訪問(wèn)標(biāo)記w=GetFistVex(&G,v); /取第一個(gè)鄰接結(jié)點(diǎn)while(w!=-1)if(!visitedw)/非0 還未訪問(wèn)DepthFSearch(G,w,visited,Visit);w=GetNextVex(&G,v,w);void DepthFirstSearch(AdjMGraph G,void Visit(DataType item)/非連通圖G的訪問(wèn)操作為Visit()的深度優(yōu)先遍歷int i;int *visited=(int

37、 *)malloc(sizeof(int)*G.Vertices.size);for(i=0;iG.Vertices.size;i+)visitedi=0;for(i=0;iG.Vertices.size;i+)if(!visitedi)DepthFSearch(G,i,visited,Visit);free(visited);#includeSeqCQueue.h /包括順序循環(huán)隊(duì)列void BroadFSearch(AdjMGraph G,int v,int visited,void Visit(DataType item)/連通圖G以v為初始結(jié)點(diǎn)的訪問(wèn)操作為Visit()的廣度優(yōu)先遍歷/

38、數(shù)組visited標(biāo)記了相應(yīng)結(jié)點(diǎn)是否已訪問(wèn)過(guò)，0表示未訪問(wèn)，1表示已訪問(wèn)DataType u,w;SeqCQueue queue;Visit(G.Vertices.listv); /訪問(wèn)結(jié)點(diǎn)vvisitedv=1; /置已訪問(wèn)標(biāo)記QueueInitiate(&queue); /隊(duì)列初始化QueueAppend(&queue,v); /初始結(jié)點(diǎn)v入隊(duì)列while(QueueNotEmpty(queue) /隊(duì)列非空時(shí)QueueDelete(&queue,&u); /出隊(duì)列w=GetFistVex(&G,u); /取結(jié)點(diǎn)u的第一個(gè)鄰接結(jié)點(diǎn)while(w!=-1) /鄰接結(jié)點(diǎn)w存在時(shí)if(!visi

39、tedw) /若沒有訪問(wèn)過(guò)Visit(G.Vertices.listw); /訪問(wèn)結(jié)點(diǎn)wvisitedw=1; /置已訪問(wèn)標(biāo)記QueueAppend(&queue,w); /結(jié)點(diǎn)w入隊(duì)列w=GetNextVex(&G,u,w); /取下一個(gè)鄰接結(jié)點(diǎn) void BroadFirstSearch(AdjMGraph G,void Visit(DataType item)/非連通圖G訪問(wèn)操作為Visit()的廣度優(yōu)先遍歷int i;int *visited=(int *)malloc(sizeof(int)*G.Vertices.size);for(i=0;iG.Vertices.size;i+)v

40、isitedi=0;for(i=0;iG.Vertices.size;i+)if(!visitedi)BroadFSearch(G,i,visited,Visit);free(visited);(8)/* 文件圖的基本操作與實(shí)現(xiàn).c */#include#include#includetypedef int DataType;/定義DataType為整形#define MaxSize 100#define MaxVertices 10#define MaxEdges 100#define MaxWeight 10000 /定義無(wú)窮大的具體值#define MaxQueueSize 100#in

41、clude AdjMGraph.h#includeAdjMGraphCreate.h#includeAdjMGraphTraverse.h#includeAdjLGraph.h#includeAdjLGraphCreate.hvoid main()AdjMGraph g1; /定義一個(gè)鄰接矩陣存儲(chǔ)結(jié)構(gòu)的圖g1RowColWeight rcwMaxEdges;/定義邊信息數(shù)組int n,e,i,j;printf(請(qǐng)輸入有向圖的頂點(diǎn)數(shù):);scanf(%d,&n);printf(請(qǐng)輸入有向圖的邊數(shù):);scanf(%d,&e);DataType aMaxVertices;/定義一個(gè)數(shù)組存儲(chǔ)頂點(diǎn)字符

42、為整形printf(該圖的%d個(gè)頂點(diǎn)字符分別為:,n);/輸出每個(gè)頂點(diǎn)字符for(i=0;in;i+)ai=i;printf(%2d,ai);printf(n);/存儲(chǔ)邊的信息for(i=0;ie;i+)printf(請(qǐng)輸入一條邊依附的頂點(diǎn)字符v1,v2及權(quán)值(v1,v2,w):);scanf(%d,%d,%d,&rcwi.row,&rcwi.col,&rcwi.weight);CreatGraph(&g1,a,n,rcw,e);/創(chuàng)建一個(gè)鄰接矩陣存儲(chǔ)結(jié)構(gòu)的圖g1printf(該圖的鄰接矩陣為:n);Print(&g1);/輸出圖g1的鄰接矩陣 /求出鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖g1的每個(gè)頂點(diǎn)的度MVertices(&g1,a);AdjLGraph g2;/定義一個(gè)鄰接表存儲(chǔ)結(jié)構(gòu)的圖g2RowCol rwcMaxEdges;/定義邊信息數(shù)組/用鄰接矩陣的信息生成鄰接表for(i=0;ie;i+)rwci.col=rcwi.col;rwci.row=rcwi.row;CreatLGraph(&g2,a,g1.Vertices.size,rwc,g1.numOfEdges);