數(shù)據(jù)結構與算法實驗——圖的基本操作10頁

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

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

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

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

5、建立一個圖的鄰接表函數(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/邊表結點int adjvex;/鄰

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

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

8、.firstedge=NULL; / 點的邊表頭指針設為空 printf("請輸入邊的信息(輸入格式為:i,j)：n"); for (k=0;k<G->e;k+) / 建立邊表 scanf("n%d,%d",&i,&j); / 讀入邊<Vi,Vj>的頂點對應序號 s=new EdgeNode; / 生成新邊表結點s s->adjvex=j; / 鄰接點序號為j s->next=G->adjlisti.firstedge; / 將新邊表結點s插入到頂點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ā)點對鄰接表表示的圖G進行深度優(yōu)先搜索 EdgeNode *p;printf("visit vertex:%cn",G->adjlisti.vertex); / 訪問頂點vivisitedi=TRUE; /標記vi已訪問p=G->adjlisti.firs

10、tedge; /取vi邊表的頭指針while(p)/依次搜索vi的鄰接點vj，這里j=p->adjvexif (!visitedp->adjvex)/若vi尚未被訪問DFS(G,p->adjvex);/則以Vj為出發(fā)點向縱深搜索p=p->next; /找vi的下一鄰接點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為源點對用鄰接表表示的圖G進行廣度優(yōu)先搜索 int i;CirQueue Q;/須將隊列定義中DataType改為intEdgeNode *p;InitQueue(&Q);/隊列初始化printf("visit vertex:%cn",G->adjlistk.vertex);/訪問源點vkvisitedk=TRUE; EnQueue(&Q,k);/vk已訪問，將其人隊。（實際上是將其序號人隊）while(!QueueEmpty(

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

15、找vi的下一鄰接點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ù)調用 */*/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,置標志求V鄰接點有鄰接點w？求下一鄰接點wV W訪問過？返回NYNY深度優(yōu)先遍歷流程圖開始結束初始化visitvV入隊列對頭元素出隊，W= FirstAdjVex(G,u)初始化visitedv V入隊列w=NextAdjVex(G,u,w)!IsEmptyQueue(Q)w!=-1YYNN廣度優(yōu)先遍歷流程圖調試報告發(fā)現(xiàn)問題：1. 在創(chuàng)建圖的鄰接表以后，得到的深度優(yōu)先遍歷和自己在草稿紙上演算得到的序列不符。2. 在創(chuàng)建圖的鄰接表以后，得到的廣度優(yōu)先遍歷和自己在草稿紙上演算得到的序列不符。調試：1. 仔細檢查程序后，發(fā)現(xiàn)是因為創(chuàng)建鄰接表的方法是

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