1、數據結構實驗報告實驗四圖的應用一、實驗題目：圖的應用一一xx優先/xx優先搜索遍歷二、實驗內容：很多涉及圖上操作的算法都是以圖的遍歷操作為根底的.試編寫一個算法,實現圖的深度優先和廣度優先搜索遍歷操作.要求：以鄰接矩陣或鄰接表為存儲結構,以用戶指定的頂點為起始點,實現連通無向圖的深度優先及廣度優先搜索遍歷,并輸出遍歷的結點序列.注：學號為奇數的同學使用鄰接矩陣存儲結構實現,學號為偶數的同學使用鄰接矩陣實現提示：首先,根據用戶輸入的頂點總數和邊數,構造無向圖,然后以用戶輸入的頂點為起始點,進行深度優先、廣度優先搜索遍歷,并輸出遍歷的結果.三、程序源代碼：#include#include#defi

2、neMAX_VERTEX_NUM20#defineOVERFLOW-1intvisited80;typedefstructArcNodeintadjvex;/該弧所指向的頂點的位置structArcNode*nextarc;/指向下一條弧的指針ArcNode;typedefstructVNodeintdata;/頂點信息ArcNode*firstarc;/指向第一條依附該頂點的弧的指針VNode,AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;ALGraph;typedefstructQNodeintdata;structQNode*nex

3、t;QNode,*QuePtr;typedefstructQuePtrfront;/隊頭指針QuePtrrear;/隊尾指針LinkQue;voidInitQue(LinkQue&q)voidEnQue(LinkQue&q,inte)intDeQue(LinkQue&q)inte;假設隊列不空,那么刪除q的隊頭元素,用e返回其值,并返回OK;否那么返回ERROR構造一個空隊列qq.front=q.rear=(QuePtr)malloc(sizeof(QNode);if(!q.front)exit(OVERFLOW);q.front-next=NULL;/插入元素e為q的

4、新的隊尾元素QuePtrp;p=(QuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存儲分酉已失敗p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;if(q.front=q.rear)returnfalse;QuePtrp;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;free(p);returne;boolQueEmpty(LinkQue&q)假設隊列q為空隊列,貝U返回TRUE否貝U返回FLASEin

5、tLocateVex(ALGraphG,intv)用鄰接表構造無向圖voidCreateDG(ALGraph&G)inti,j,k;printf(輸入圖的頂點數和弧度：n);if(q.front=q.rear)returntrue;elsereturnfalse;inti;for(i=0;iG.vexnum;i+)if(G.verticesi.data=v)returni;printf(輸入頂點信息：n);for(i=0;iadjvex=j;s-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=s;structArcNode*t;t=(

6、ArcNode*)malloc(sizeof(ArcNode);t-adjvex=i;t-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=t;voidDFSAL(ALGraphG,intv0)visitedv0=1;printf(%5d,G.verticesv0.data);structArcNode*p;/深度優先搜索遍歷voidDFSTraverse(ALGraphG)/xx優先搜索遍歷voidBFSTraverse(ALGraphG,LinkQueq)intu,w;structArcNode*p;for(u=0;uG.vexnum;u+

7、)visitedu=0;/訪問標志數組初始化InitQue(q);for(u=0;unextarc)w=p-adjvex;if(!visitedw)DFSAL(G,w);intv0;for(v0=0;v0G.vexnum;v0+)visitedv0=0;/訪問標志數組初始化/直到圖中所有頂點都被訪問到為止for(v0=0;v0adjvex;if(!visitedw)/ifp=p-nextarc;visitedw=1;printf(%5d,G.verticesw.data);EnQue(q,w);/while/while/BFSTraverseintmain()ALGraphG;LinkQueq;CreateDG(G);printf(n