北信_實驗四_圖的遍歷

《北信_實驗四_圖的遍歷》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、實驗報告課程名稱數(shù)據(jù)結構實驗項目圖的深度和廣度遍歷實驗儀器PC系別：計算機科學與技術班級學號：計科0902/2009011136姓名：高鋒日期：2011.05.20成績：指導老師：張仰森一、目的和要求：1、熟練掌握圖的定義、性質(zhì)和存儲結構；2、熟練掌握圖的兩種遍歷和線索化以及遍歷算法的各種描述形式；3、學會編寫實現(xiàn)圖的各種操作的算法。二、實驗題目：圖的建立與遍歷：掌握建立圖的方法，實現(xiàn)深度和廣度遍歷算法。三、源程序（深度和廣度）#include#include#defineTRUE1#defi

2、neFALSE0#defineINFINITY32767#defineMAX_VEX20//最大頂點個數(shù)bool*visited;//訪問標志數(shù)組//圖的鄰接矩陣存儲結構typedefstruct{char*vexs;//頂點向量intarcs[MAX_VEX][MAX_VEX];//鄰接矩陣intvexnum,arcnum;//圖的當前頂點數(shù)和弧數(shù)}Graph;//隊列操作函數(shù)typedefstructQnode{int*front;int*rear;}qnode;//初始化隊列函數(shù)voidInitQueue(qnode&q){q

3、.front=q.rear=(int*)malloc(sizeof(int)*50);if(!q.front)exit(0);}//加入隊列voidEnQueue(qnode&q,intt){*q.rear=t;q.rear++;}//退出隊列intDeQueue(qnode&q){return*q.front++;//先返回再加//return*q.front;//q.front++;極端愚蠢的錯誤}//判斷隊列是否為空intQueueEmpty(qnode&q){if(q.rear==q.front)returnTRUE;els

4、ereturnFALSE;}//圖G中查找元素c的位置intLocate(GraphG,charc){for(inti=0;i

5、*)malloc(G.vexnum*sizeof(char));//分配頂點數(shù)目printf("輸入%d個頂點.",G.vexnum);for(i=0;i

6、.arcnum);for(i=0;i=0&&k

7、++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}//圖G中頂點i的第j個鄰接頂點的下一個鄰接頂點intNextVex(GraphG,inti,intj){if(i>=0&&i=0&&j

8、執(zhí)行DFS時,k為-1for(i=0;i