大數據結構與算法實驗——圖地基本操作

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

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

3、 ）（ 3,4 ）（3,6 ）（4,5 ）作為各頂點信息生成一個鄰接表。精彩文檔實用標準文案2概要設計1）為了實現上述程序功能，需要定義二叉樹的抽象數據類型：ADT Graph數據對象：頂點的有窮非空集合和邊的集合數據關系：結點具有相同的數據類型及層次結構基本操作：Void InitGraph(ALGraph *G)初始條件：無操作結果：初始化圖Void DFSTraverse( ALGraph *G )初始條件：圖 Graph 已存在操作結果：按深度優(yōu)先遍歷圖的鄰接表Void BFSTraverse( ALGraph *G )初始條件：圖 Graph 已存在操作結果：按廣度優(yōu)先遍歷圖的鄰接表

4、2）本程序包含 7 個函數：主函數 main() 建立一個圖的鄰接表函數 CreateGraphAL () 深度優(yōu)先遍歷圖 DFS () 廣度優(yōu)先遍歷 BFS()函數說明#include <stdio.h>#include <stdlib.h>#define MaxVertexNum 100#define QueueSize 30typedef enumFALSE,TRUEBoolean;Boolean visitedMaxVertexNum;typedef char VertexType;typedef int EdgeType;typedef struct node

5、/ 邊表結點int adjvex;/ 鄰接點域struct node *next;/ 域鏈/ 若是要表示邊上的權 , 則應增加一個數據域EdgeNode;typedef struct vnode/ 頂點邊結點VertexType vertex;/ 頂點域EdgeNode *firstedge;/邊表頭指針VertexNode;typedef VertexNode AdjListMaxVertexNum;/AdjList是鄰接表類型typedef structAdjList adjlist;/ 鄰接表精彩文檔實用標準文案int n,e;/ 圖中當前頂點數和邊數ALGraph;void Creat

6、eGraphAL (ALGraph *G)int i,j,k;EdgeNode * s;printf("請輸入頂點數和邊數( 輸入格式為 : 頂點數 , 邊數 ) ： n");scanf("%d,%d",&(G->n),&(G->e);/讀入頂點數和邊數printf("請輸入頂點信息( 輸入格式為 : 頂點號 <CR>)每個頂點以回車作為結束:n");for (i=0;i<G->n;i+)/立有 n 個頂點的頂點表scanf("n%c",&(G->a

7、djlisti.vertex); /讀入頂點信息G->adjlisti.firstedge=NULL;/點的邊表頭指針設為空printf("請輸入邊的信息( 輸入格式為 :i,j)： n");for (k=0;k<G->e;k+)/建立邊表scanf("n%d,%d",&i,&j); /讀入邊 <Vi,Vj>的頂點對應序號s=new EdgeNode;/生成新邊表結點ss->adjvex=j;/鄰接點序號為js->next=G->adjlisti.firstedge; /將新邊表結點s 插入

8、到頂點Vi 的邊表頭部G->adjlisti.firstedge=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;/ 標記

9、vi 已訪問p=G->adjlisti.firstedge;/取 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(!v

10、isitedi)DFS(G,i);/*/*廣度優(yōu)先遍歷*/*/ typedef structint 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

11、EnQueue(CirQueue *Q,int x)if (QueueFull(Q)printf("Queue overflow");elseQ->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;elsetemp=Q->dataQ->front;Q->co

12、unt-;Q->front=(Q->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已訪問，將其人隊。 （實際

13、上是將其序號人隊）while(!QueueEmpty(&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(&a

14、mp;Q,p->adjvex);/ 訪問過的vj 人隊p=p->next;/ 找 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);/*/*主函數調用*/*/ int main()int n;ALGraph G;CreateGraphAL(&G);printf("深度優(yōu)先遍歷：n");DFSTraverseM(&G)

15、;printf("廣度優(yōu)先遍歷：n");BFSTraverseM(&G);return 0;程序流程圖開始訪問V, 置標志求 V鄰接點有鄰接點 w？YW訪問過？N精彩文檔wVN返回Y求下一鄰接點深度優(yōu)先遍歷流程圖實用標準文案開始初始化 visitvV 入隊列N!IsEmptyQueue(Q)結束Y對頭元素出隊，W= FirstAdjVex(G,u)N初始化 visitedvw!=-1V 入隊列Yw=NextAdjVex(G,u,w)廣度優(yōu)先遍歷流程圖調試報告發(fā)現問題 ：1. 在創(chuàng)建圖的鄰接表以后，得到的深度優(yōu)先遍歷和自己在草稿紙上演算得到的序列不符。2. 在創(chuàng)建圖的

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