圖的深度廣度遍歷和最短路徑問題(迪杰斯特拉算法實(shí)現(xiàn)).doc

《圖的深度廣度遍歷和最短路徑問題(迪杰斯特拉算法實(shí)現(xiàn)).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)項(xiàng)目圖的深度廣度遍歷和最短路徑實(shí)驗(yàn)儀器計(jì)算機(jī)學(xué)生姓名徐申毅實(shí)驗(yàn)日期2013-6-7成績(jī)實(shí)驗(yàn)1一?、實(shí)驗(yàn)?zāi)康睦斫鈭D的深度和廣度遍歷，能利用迪杰斯特拉算法求出最短路徑二、?實(shí)驗(yàn)內(nèi)容編寫能求解圖的深度和廣度遍歷和最短路徑的程序三、實(shí)驗(yàn)課時(shí)4課時(shí)共23頁(yè)第22頁(yè)四、實(shí)驗(yàn)步驟（1）利用鄰接矩陣實(shí)現(xiàn)圖的存儲(chǔ)（2）利用棧實(shí)現(xiàn)圖的深度遍歷（3）利用隊(duì)列實(shí)現(xiàn)圖的廣度遍歷（4）用迪杰斯特拉算法求圖的最短路徑（5）編寫主函數(shù)（6）編譯，調(diào)試，運(yùn)行五、實(shí)驗(yàn)心得本次實(shí)驗(yàn)讓我學(xué)會(huì)了利用棧和隊(duì)列的數(shù)據(jù)結(jié)

2、構(gòu)實(shí)現(xiàn)圖的深度和廣度遍歷，能用迪杰斯特拉算法求出無向網(wǎng)的最短路徑。六、程序運(yùn)行結(jié)果截圖以及C程序源代碼#include#include#defineINFINITY65535#defineMAXVEXNUM20typedefstructArcCell{intadj;//int(VRType)是頂點(diǎn)關(guān)系類型。char*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAXVEXNUM][MAXVEXNUM];typedefstruct{共23頁(yè)

3、第22頁(yè)charvexs[MAXVEXNUM][4];AdjMatrixarcs;intvexnum,arcnum;}MGraph;#defineQUEUE_INIT_SIZE100#defineQUEUEINCREMENT10typedefintQElemType;typedefstruct{QElemType*elem;intfront;intrear;intqueuesize;intincrementsize;}SqQueue;共23頁(yè)第22頁(yè)#include#include<

4、stdlib.h>voidInitQueue_Sq(SqQueue*Q,intn){Q->elem=(QElemType*)malloc((QUEUE_INIT_SIZE+1)*sizeof(QElemType));Q->queuesize=n;Q->incrementsize=QUEUEINCREMENT;Q->front=Q->rear=0;}intQueueLength_Sq(SqQueueQ){return(Q.rear-Q.front+Q.queuesize)%Q.queuesize;}in

5、tDeQueue_Sq(SqQueue*Q,QElemType*e){if(Q->front==Q->rear)return0;*e=Q->elem[Q->front];共23頁(yè)第22頁(yè)Q->front=(Q->front+1)%Q->queuesize;return1;}voidincrementQueuesize(SqQueue*Q){QElemType*a;intk;a=(QElemType*)malloc((Q->queuesize+Q->incrementsize)*sizeof(QElem

6、Type));for(k=0;kqueuesize-1;k++)a[k]=Q->elem[(Q->front+k)%Q->queuesize];free(Q->elem);Q->elem=a;Q->front=0;Q->rear=Q->queuesize-1;Q->queuesize+=Q->incrementsize;}voidEnQueue_Sq(SqQueue*Q,QElemTypee)共23頁(yè)第22頁(yè){if((Q->rear+1)%Q->queuesize==Q->front)incr

7、ementQueuesize(Q);Q->elem[Q->rear]=e;Q->rear=(Q->rear+1)%Q->queuesize;}intGetQueue_Sq(SqQueueQ,QElemType*e){if(Q.front==Q.rear)return0;*e=Q.elem[Q.front];return1;}intQueueEmpty(SqQueueQ){if(Q.front==Q.rear)return1;共23頁(yè)第22頁(yè)elsereturn0;}intvisited[MAXVEXN

8、UM];intLocateVex(MGraph*G,charv[4]){inti=0;while(ivexnum){if(strcmp(G->vexs[i],v)==0)returni;i++;}printf("輸入的頂點(diǎn)不存在！");return0;}voidDFS(MGraph*G,inti)共23頁(yè)第22頁(yè){intj;printf("%7s",G->vexs[i]);visited[i]=1;for(j=0;jvexnum;j+