數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)——圖的基本操作

1、圖的基本操作實(shí)驗(yàn)報(bào)告圖的基本操作實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)名稱圖的基本操作實(shí)驗(yàn)?zāi)康?. 掌握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)，特別要熟練掌握鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)；2. 遍歷是圖各種應(yīng)用的算法的基礎(chǔ)，要熟練掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的算法，復(fù)習(xí)棧和隊(duì)列的應(yīng)用；3. 掌握以鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)的生成圖的最小生成樹的普利姆算法；實(shí)驗(yàn)內(nèi)容編制一個(gè)演示圖的鄰接表的創(chuàng)建、深度遍歷、廣度遍歷操作的程序。問題描述用數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)，實(shí)現(xiàn)鄰接表的定義和操作。該程序包括圖的鄰接表的結(jié)點(diǎn)類型定義以及對(duì)圖操作的具體的函數(shù)定義（包括：建立圖的鄰接表、深度優(yōu)先遍歷圖、廣度優(yōu)先遍歷圖）。問題分析該實(shí)驗(yàn)是基于C語言和數(shù)據(jù)結(jié)構(gòu)知識(shí)基礎(chǔ)的對(duì)圖

2、的基本操作的檢驗(yàn)，無需設(shè)計(jì)復(fù)雜的算法，程序語句也相對(duì)簡(jiǎn)單。因此，我直接按要求定義了對(duì)圖操作的具體函數(shù)，并于主函數(shù)中實(shí)現(xiàn)對(duì)應(yīng)的功能調(diào)用。 實(shí)驗(yàn)步驟1需求分析    本演示程序用VC+編寫，完成圖的鄰接表的生成、遍歷基本操作。  輸入的形式和輸入值的范圍：在輸入鄰接表頂點(diǎn)信息前，必須先確定該信息能正確創(chuàng)建鄰接表。   輸出的形式：在所有三種操作中都顯示操作是否正確以及操作后圖的內(nèi)容。   程序所能達(dá)到的功能：完成圖的鄰接表的生成、深度優(yōu)先遍歷、廣度優(yōu)先遍歷基本操作。   測(cè)試數(shù)據(jù)：創(chuàng)建操作中依次輸入

3、7,7作為頂點(diǎn)數(shù)和邊數(shù)，以（0,1）（0,2）（1,3）（1,5）（3,4）（3,6）（4,5）作為各頂點(diǎn)信息生成一個(gè)鄰接表。 2概要設(shè)計(jì)   1）為了實(shí)現(xiàn)上述程序功能，需要定義二叉樹的抽象數(shù)據(jù)類型：   ADT Graph   數(shù)據(jù)對(duì)象：頂點(diǎn)的有窮非空集合和邊的集合數(shù)據(jù)關(guān)系：結(jié)點(diǎn)具有相同的數(shù)據(jù)類型及層次結(jié)構(gòu) 基本操作： Void InitGraph(ALGraph *G)    初始條件：無   

4、0;操作結(jié)果：初始化圖  Void DFSTraverse(ALGraph *G)     初始條件：圖Graph已存在    操作結(jié)果：按深度優(yōu)先遍歷圖的鄰接表Void BFSTraverse(ALGraph *G)     初始條件：圖Graph已存在    操作結(jié)果：按廣度優(yōu)先遍歷圖的鄰接表2）本程序包含7個(gè)函數(shù)：   主函數(shù)main()  

5、建立一個(gè)圖的鄰接表函數(shù)CreateGraphAL () 深度優(yōu)先遍歷圖 DFS ()廣度優(yōu)先遍歷 BFS() 函數(shù)說明#include <stdio.h>#include <stdlib.h>#define MaxVertexNum 100#define QueueSize 30 typedef enumFALSE,TRUEBoolean; Boolean visitedMaxVertexNum; typedef char VertexType;typedef int EdgeType;typedef struct node/邊表結(jié)點(diǎn)int adjvex;/鄰

6、接點(diǎn)域struct node *next;/域鏈/若是要表示邊上的權(quán),則應(yīng)增加一個(gè)數(shù)據(jù)域EdgeNode;typedef struct vnode/頂點(diǎn)邊結(jié)點(diǎn)VertexType vertex;/頂點(diǎn)域EdgeNode *firstedge;/邊表頭指針VertexNode;typedef VertexNode AdjListMaxVertexNum;/AdjList是鄰接表類型typedef struct AdjList adjlist;/鄰接表int n,e;/圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)ALGraph;void CreateGraphAL (ALGraph *G) int i,j,k; Edge

7、Node * s; printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為:頂點(diǎn)數(shù),邊數(shù))：n"); scanf("%d,%d",&(G->n),&(G->e); / 讀入頂點(diǎn)數(shù)和邊數(shù) printf("請(qǐng)輸入頂點(diǎn)信息(輸入格式為:頂點(diǎn)號(hào)<CR>)每個(gè)頂點(diǎn)以回車作為結(jié)束:n"); for (i=0;i<G->n;i+) / 立有n個(gè)頂點(diǎn)的頂點(diǎn)表 scanf("n%c",&(G->adjlisti.vertex); / 讀入頂點(diǎn)信息 G->adjlisti

8、.firstedge=NULL; / 點(diǎn)的邊表頭指針設(shè)為空 printf("請(qǐng)輸入邊的信息(輸入格式為:i,j)：n"); for (k=0;k<G->e;k+) / 建立邊表 scanf("n%d,%d",&i,&j); / 讀入邊<Vi,Vj>的頂點(diǎn)對(duì)應(yīng)序號(hào) s=new EdgeNode; / 生成新邊表結(jié)點(diǎn)s s->adjvex=j; / 鄰接點(diǎn)序號(hào)為j s->next=G->adjlisti.firstedge; / 將新邊表結(jié)點(diǎn)s插入到頂點(diǎn)Vi的邊表頭部 G->adjlisti.f

9、irstedge=s; s=new EdgeNode;s->adjvex=i;s->next=G->adjlistj.firstedge;G->adjlistj.firstedge=s; /*/* 深度優(yōu)先遍歷 */*/ void DFS(ALGraph *G,int i) /以vi為出發(fā)點(diǎn)對(duì)鄰接表表示的圖G進(jìn)行深度優(yōu)先搜索 EdgeNode *p;printf("visit vertex:%cn",G->adjlisti.vertex); / 訪問頂點(diǎn)vivisitedi=TRUE; /標(biāo)記vi已訪問p=G->adjlisti.firs

10、tedge; /取vi邊表的頭指針while(p)/依次搜索vi的鄰接點(diǎn)vj，這里j=p->adjvexif (!visitedp->adjvex)/若vi尚未被訪問DFS(G,p->adjvex);/則以Vj為出發(fā)點(diǎn)向縱深搜索p=p->next; /找vi的下一鄰接點(diǎn)void DFSTraverseM(ALGraph *G) int i; for(i=0;i<G->n;i+) visitedi=FALSE; for(i=0;i<G->n;i+) if(!visitedi) DFS(G,i); /*/* 廣度優(yōu)先遍歷 */*/typedef st

11、ruct int front; int rear; int count; int dataQueueSize; CirQueue; void InitQueue(CirQueue *Q) Q->front=Q->rear=0; Q->count=0; int QueueEmpty(CirQueue *Q) return Q->front=Q->rear; int QueueFull(CirQueue *Q) return (Q->rear+1)%QueueSize=Q->front; void EnQueue(CirQueue *Q,int x) if

12、 (QueueFull(Q) printf("Queue overflow"); else Q->count+; Q->dataQ->rear=x; Q->rear=(Q->rear+1)%QueueSize; int DeQueue(CirQueue *Q) int temp; if(QueueEmpty(Q) printf("Queue underflow"); return false; else temp=Q->dataQ->front; Q->count-; Q->front=(Q->

13、front+1)%QueueSize; return temp; void BFS(ALGraph*G,int k)/ 以vk為源點(diǎn)對(duì)用鄰接表表示的圖G進(jìn)行廣度優(yōu)先搜索 int i;CirQueue Q;/須將隊(duì)列定義中DataType改為intEdgeNode *p;InitQueue(&Q);/隊(duì)列初始化printf("visit vertex:%cn",G->adjlistk.vertex);/訪問源點(diǎn)vkvisitedk=TRUE; EnQueue(&Q,k);/vk已訪問，將其人隊(duì)。（實(shí)際上是將其序號(hào)人隊(duì)）while(!QueueEmpty(

14、&Q)/隊(duì)非空則執(zhí)行i=DeQueue(&Q);/相當(dāng)于vi出隊(duì)p=G->adjlisti.firstedge;/取vi的邊表頭指針while(p)/依次搜索vi的鄰接點(diǎn)vj(令p->adjvex=j)if(!visitedp->adjvex)/若vj未訪問過printf("visit vertex:%cn",G->adjlistp->adjvex.vertex);/訪問vjvisitedp->adjvex=TRUE; EnQueue(&Q,p->adjvex);/訪問過的vj人隊(duì)p=p->next;/

15、找vi的下一鄰接點(diǎn)void BFSTraverseM(ALGraph *G) int i; for (i=0;i<G->n;i+) visitedi=FALSE; for (i=0;i<G->n;i+) if (!visitedi) BFS(G,i); /*/* 主函數(shù)調(diào)用 */*/int main()int n; ALGraph G; CreateGraphAL(&G); printf("深度優(yōu)先遍歷：n");DFSTraverseM(&G); printf("廣度優(yōu)先遍歷：n");BFSTraverseM(&a

16、mp;G);return 0;程序流程圖開始訪問V,置標(biāo)志求V鄰接點(diǎn)有鄰接點(diǎn)w？求下一鄰接點(diǎn)wV W訪問過？返回NYNY深度優(yōu)先遍歷流程圖開始結(jié)束初始化visitvV入隊(duì)列對(duì)頭元素出隊(duì)，W= FirstAdjVex(G,u)初始化visitedv V入隊(duì)列w=NextAdjVex(G,u,w)!IsEmptyQueue(Q)w!=-1YYNN廣度優(yōu)先遍歷流程圖調(diào)試報(bào)告發(fā)現(xiàn)問題：1. 在創(chuàng)建圖的鄰接表以后，得到的深度優(yōu)先遍歷和自己在草稿紙上演算得到的序列不符。2. 在創(chuàng)建圖的鄰接表以后，得到的廣度優(yōu)先遍歷和自己在草稿紙上演算得到的序列不符。調(diào)試：1. 仔細(xì)檢查程序后，發(fā)現(xiàn)是因?yàn)閯?chuàng)建鄰接表的方法是

17、頭插法；2. 檢查程序，發(fā)現(xiàn)依據(jù)隊(duì)列的長(zhǎng)度而判斷隊(duì)滿和隊(duì)空的條件不能實(shí)現(xiàn)。解決方案：1. 我重新在草稿紙上對(duì)用頭插法建立的鄰接表進(jìn)行深度遍歷；2. 將隊(duì)滿的條件修改為：(rear+1)%QueueSize=front;將隊(duì)空的條件修改為：rear=front結(jié)果：結(jié)果運(yùn)行正確！使用說明建立鄰接表深度優(yōu)先遍歷廣度優(yōu)先遍歷心得體會(huì)數(shù)據(jù)結(jié)構(gòu)顧名思義講求的是一種存儲(chǔ)結(jié)構(gòu)，一路走來先后學(xué)習(xí)了表、樹，最后學(xué)習(xí)的是圖，對(duì)于每種存儲(chǔ)結(jié)構(gòu)學(xué)習(xí)之初都會(huì)學(xué)習(xí)一些基本操作，而操作之中又以創(chuàng)建和遍歷為最基本的操作，只有熟練掌握了以后才能對(duì)其他操作進(jìn)行研究和學(xué)習(xí)。 圖的存儲(chǔ)結(jié)構(gòu)相比表和樹都要復(fù)雜，其操作過程也較難進(jìn)行掌握。僅僅是創(chuàng)建圖的存儲(chǔ)結(jié)構(gòu)便分為矩陣、臨接鏈表、十字鏈表等，對(duì)于每一種存儲(chǔ)結(jié)構(gòu)又分為有向與無向之分。然而，深度優(yōu)先和廣度優(yōu)先是兩種算法，