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

1、實(shí)用標(biāo)準(zhǔn)文案圖的基本操作實(shí)驗(yàn)報(bào)告精彩文檔實(shí)用標(biāo)準(zhǔn)文案圖的基本操作實(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)建、深度遍歷、廣度遍歷操作的程序。問(wèn)題描述用數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)， 實(shí)現(xiàn)鄰接表的定義和操作。 該程序包括圖的鄰接表的結(jié)點(diǎn)類型定義以及對(duì)圖操作的具體的函數(shù)定義 （包括：建立圖的鄰接表、 深度優(yōu)先遍歷圖、廣度優(yōu)先遍歷圖） 。問(wèn)題分析該

2、實(shí)驗(yàn)是基于 C 語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)知識(shí)基礎(chǔ)的對(duì)圖的基本操作的檢驗(yàn)， 無(wú)需設(shè)計(jì)復(fù)雜的算法，程序語(yǔ)句也相對(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)建操作中依次輸入 7,7 作為頂點(diǎn)數(shù)和邊數(shù)，以（ 0,1 ）（0,2 ）（ 1,3 ）（ 1,5

3、 ）（ 3,4 ）（3,6 ）（4,5 ）作為各頂點(diǎn)信息生成一個(gè)鄰接表。精彩文檔實(shí)用標(biāo)準(zhǔn)文案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)初始條件：無(wú)操作結(jié)果：初始化圖Void DFSTraverse( ALGraph *G )初始條件：圖 Graph 已存在操作結(jié)果：按深度優(yōu)先遍歷圖的鄰接表Void BFSTraverse( ALGraph *G )初始條件：圖 Graph 已存在操作結(jié)果：按廣度優(yōu)先遍歷圖的鄰接表

4、2）本程序包含 7 個(gè)函數(shù)：主函數(shù) main() 建立一個(gè)圖的鄰接表函數(shù) CreateGraphAL () 深度優(yōu)先遍歷圖 DFS () 廣度優(yōu)先遍歷 BFS()函數(shù)說(shuō)明#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、/ 邊表結(jié)點(diǎn)int adjvex;/ 鄰接點(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 structAdjList adjlist;/ 鄰接表精彩文檔實(shí)用標(biāo)準(zhǔn)文案int n,e;/ 圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)ALGraph;void Creat

6、eGraphAL (ALGraph *G)int i,j,k;EdgeNode * 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->a

7、djlisti.vertex); /讀入頂點(diǎn)信息G->adjlisti.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)ss->adjvex=j;/鄰接點(diǎn)序號(hào)為js->next=G->adjlisti.firstedge; /將新邊表結(jié)點(diǎn)s 插入

8、到頂點(diǎn)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ā)點(diǎn)對(duì)鄰接表表示的圖 G進(jìn)行深度優(yōu)先搜索 EdgeNode *p;printf("visit vertex:%cn",G->adjlisti.vertex); /訪問(wèn)頂點(diǎn) vivisitedi=TRUE;/ 標(biāo)記

9、vi 已訪問(wèn)p=G->adjlisti.firstedge;/取 vi 邊表的頭指針while(p)/ 依次搜索vi 的鄰接點(diǎn) vj ，這里 j=p->adjvexif (!visitedp->adjvex)/ 若 vi 尚未被訪問(wèn)DFS(G,p->adjvex);/ 則以 Vj 為出發(fā)點(diǎn)向縱深搜索精彩文檔實(shí)用標(biāo)準(zhǔ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(!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;精彩文檔實(shí)用標(biāo)準(zhǔn)文案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 為源點(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);/ 訪問(wèn)源點(diǎn)vkvisitedk=TRUE;EnQueue(&Q,k);/vk已訪問(wèn)，將其人隊(duì)。 （實(shí)際

13、上是將其序號(hào)人隊(duì)）while(!QueueEmpty(&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 未訪問(wèn)過(guò)printf("visit vertex:%cn",G->adjlistp->adjvex.vertex);/ 訪問(wèn) vjvisitedp->adjvex=TRUE;EnQueue(&a

14、mp;Q,p->adjvex);/ 訪問(wèn)過(guò)的vj 人隊(duì)p=p->next;/ 找 vi 的下一鄰接點(diǎn)精彩文檔實(shí)用標(biāo)準(zhǔ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)

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

16、鄰接表以后，得到的廣度優(yōu)先遍歷和自己在草稿紙上演算得到的序列不符。調(diào)試：1. 仔細(xì)檢查程序后，發(fā)現(xiàn)是因?yàn)閯?chuàng)建鄰接表的方法是頭插法；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)行正確！使用說(shuō)明精彩文檔實(shí)用標(biāo)準(zhǔn)文案建立鄰接表深度優(yōu)先遍歷廣度優(yōu)先遍歷心得體會(huì)數(shù)據(jù)結(jié)構(gòu)顧名思義講求的是一種存儲(chǔ)結(jié)構(gòu)， 一路走來(lái)先后學(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ù)雜， 其操作過(guò)程也較難進(jìn)行掌握。 僅僅是創(chuàng)建圖的存儲(chǔ)結(jié)構(gòu)便分為矩陣、 臨接鏈表、 十字鏈表等， 對(duì)于每一種存儲(chǔ)結(jié)構(gòu)又分為有向與無(wú)向之分。 然而，深度優(yōu)先和廣度優(yōu)先是兩種算法， 其算法思想并不依賴與元素的存儲(chǔ)方式，也就