圖遍歷的演示

1、 約瑟夫環(huán)實(shí)驗(yàn)報(bào)告1 需求分析1、以鄰接多重表為存儲結(jié)構(gòu)；2、實(shí)現(xiàn)連通和非連通的無向圖的深度優(yōu)先和廣度優(yōu)先遍歷；3、要求利用棧實(shí)現(xiàn)無向圖的深度優(yōu)先遍歷；4、以用戶指定的結(jié)點(diǎn)為起點(diǎn),分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和生成樹的邊集；5、用凹入表打印生成樹；6、求出從一個結(jié)點(diǎn)到另外一個結(jié)點(diǎn)，但不經(jīng)過另外一個指定結(jié)點(diǎn)的所有簡單路徑；2 概要設(shè)計(jì) 1. 設(shè)定圖的抽象數(shù)據(jù)類型2. 棧的抽象數(shù)據(jù)類型定義3. 隊(duì)列的抽象數(shù)據(jù)類型定義3 詳細(xì)設(shè)計(jì)程序設(shè)計(jì)如下：#include<stdio.h> #include <stdlib.h>#include<conio.h>

2、#define MAXQUEUE 70 /* 佇列的最大容量 */struct node /* 圖形頂點(diǎn)結(jié)構(gòu)宣告 */ int vertex; /* 頂點(diǎn)資料 */ struct node *nextnode; /* 指下一頂點(diǎn)的指標(biāo) */;typedef struct node *graph; /* 圖形的結(jié)構(gòu)新型態(tài) */struct node head61; /* 圖形頂點(diǎn)結(jié)構(gòu)數(shù)組 */int visited61; /* 遍歷記錄數(shù)組 */int queueMAXQUEUE; /* 佇列的數(shù)組宣告 */int front = -1; /* 佇列的前端 */int rear = -1; /*

3、 佇列的后端 */* - */* 建立圖形 */* - */void creategraph(int *node,int num) graph newnode; /* 新頂點(diǎn)指標(biāo) */ graph ptr; int from; /* 邊線的起點(diǎn) */ int to; /* 邊線的終點(diǎn) */ int i; for ( i = 0; i < num; i+ ) /* 讀取邊線的回路 */ from = nodei*2; /* 邊線的起點(diǎn) */ to = nodei*2+1; /* 邊線的終點(diǎn) */ /* 建立新頂點(diǎn)記憶體 */ newnode = ( graph ) malloc(sizeo

4、f(struct node); newnode->vertex = to; /* 建立頂點(diǎn)內(nèi)容 */ newnode->nextnode = NULL; /* 設(shè)定指標(biāo)初值 */ ptr = &(headfrom); /* 頂點(diǎn)位置 */ while ( ptr->nextnode != NULL ) /* 遍歷至鏈表尾 */ ptr = ptr->nextnode; /* 下一個頂點(diǎn) */ ptr->nextnode = newnode; /* 插入結(jié)尾 */ /* - */* 佇列資料的存入 */* - */int enqueue(int value)

5、 if ( rear >= MAXQUEUE ) /* 檢查佇列是否全滿 */ return -1; /* 無法存入 */ rear+; /* 后端指標(biāo)往前移 */ queuerear = value; /* 存入佇列 */* - */* 佇列資料的取出 */* - */int dequeue() if ( front = rear ) /* 檢查佇列是否是空 */ return -1; /* 無法取出 */ front+; /* 前端指標(biāo)往前移 */ return queuefront; /* 佇列取出 */* - */* 圖形的廣度優(yōu)先搜尋法 */* - */void bfs(int

6、 current) graph ptr; /* 處理第一個頂點(diǎn) */ enqueue(current); /* 將頂點(diǎn)存入佇列 */ visitedcurrent = 1; /* 記錄已遍歷過 */ printf("%d ",current); /* 印出遍歷頂點(diǎn)值 */ while ( front != rear ) /* 佇列是否是空的 */ current = dequeue(); /* 將頂點(diǎn)從佇列取出 */ ptr = headcurrent.nextnode; /* 頂點(diǎn)位置 */ while ( ptr != NULL ) /* 遍歷至鏈表尾 */ if (

7、visitedptr->vertex = 0 ) /* 如過沒遍歷過 */ enqueue(ptr->vertex); /* 遞回遍歷呼叫 */ visitedptr->vertex = 1; /* 記錄已遍歷過 */ /* 印出遍歷頂點(diǎn)值 */ printf("%d ",ptr->vertex); ptr = ptr->nextnode; /* 下一個頂點(diǎn) */ /* - */* 圖形的深度優(yōu)先搜尋法 */* - */void dfs(int current) graph ptr; visitedcurrent = 1; /* 記錄已遍歷過

8、*/ printf("%d ",current); /* 印出遍歷頂點(diǎn)值 */ ptr = headcurrent.nextnode; /* 頂點(diǎn)位置 */ while ( ptr != NULL ) /* 遍歷至鏈表尾 */ if ( visitedptr->vertex = 0 ) /* 如過沒遍歷過 */ dfs(ptr->vertex); /* 遞回遍歷呼叫 */ ptr = ptr->nextnode; /* 下一個頂點(diǎn) */ /* - */* 主程式: 建立圖形后,將遍歷內(nèi)容印出. */* - */int main()/clrscr();whi

9、le(1) char c,a; graph ptr; int i; int node 60 2 = 1, 10, 10, 1, /* 邊線數(shù)組 */ 2, 10, 10, 2, 2, 3, 3, 2, 3, 4, 4, 3, 3, 12, 12, 3, 4, 13, 13, 4, 4, 5, 5, 4, 5, 6, 6, 5, 5, 7, 7, 5, 7, 8, 8, 7, 9, 10, 10, 9, 10, 11, 11, 10, 11, 14, 14, 11, 11, 12, 12, 11, 12, 15, 15, 12, 12, 13, 13, 12, 13, 16, 16, 13, 1

10、4, 17, 17, 14, 14, 18, 18, 14, 15, 19, 19, 15, 16, 20, 20, 16, 17, 18, 18, 17, 18, 23, 23, 18, 18, 19, 19, 18, 19, 23, 23, 19, 19, 24, 24, 19, 19, 20, 20, 19, 20, 21, 21, 20, 22, 23, 23, 22, 24, 25, 25,24 ;/clrscr();printf("nnn");printf(" 圖 的 深 度 遍 歷 和 廣 度 遍 歷? Y/N?n");c=getch();

11、if(c!='y'&&'Y')exit(0); /clrscr();printf("nn");printf("以 下 為 各 城 市 的 代 碼:nn"); printf("1:烏魯木齊; 2:呼和浩特; 3:北京; 4:天津; 5:沈陽; n"); printf("6:大連; 7:長春; 8:哈爾濱; 9:西寧; 10:蘭州;n"); printf("11:西安; 12:鄭州; 13:徐州; 14:成都; 15:武漢; n"); printf(&

12、quot;16:上海; 17:昆明; 18:貴陽; 19:株州; 20:南昌;n"); printf("21:福州; 22:南寧; 23:柳州; 24:廣州; 25:深圳.n"); for (i=1;i<=25;i+ ) headi.vertex=i; /* 設(shè)定頂點(diǎn)值 */ headi.nextnode=NULL; /* 清除圖形指標(biāo) */ visitedi=0; /* 設(shè)定遍歷初值 */ creategraph(node,60); /* 建立圖形 */ printf("圖 形 的 鄰 接 鏈 表 內(nèi) 容:n"); for (i=1;i

13、<=25;i+) if(i%3=0)printf("n"); printf("頂點(diǎn)%d=>",headi.vertex); /* 頂點(diǎn)值 */ ptr=headi.nextnode; /* 頂點(diǎn)位置 */ while(ptr!=NULL) /* 遍歷至鏈表尾 */ printf("%d ",ptr->vertex); /* 印出頂點(diǎn)內(nèi)容 */ ptr=ptr->nextnode; /* 下一個頂點(diǎn) */ printf("nn");printf("請 選 擇 你 需 要 的 操 作n

14、");printf("1、圖形的廣度優(yōu)先遍歷請輸入:'g'或'G'n");printf("2、圖形的深度優(yōu)先遍歷請輸入:'s'或'S'n"); c=getch(); switch(c) case'g':case'G': printf("n請 你 輸 入 你 需 要 的 起 始 頂 點(diǎn):n"); scanf("%d",&i); /clrscr(); printf("nn"); prin

15、tf("以 下 為 各 城 市 的 代 碼:nn"); printf("1:烏魯木齊; 2:呼和浩特; 3:北京; 4:天津; 5:沈陽; n"); printf("6:大連; 7:長春; 8:哈爾濱; 9:西寧; 10:蘭州;n"); printf("11:西安; 12:鄭州; 13:徐州; 14:成都; 15:武漢; n"); printf("16:上海; 17:昆明; 18:貴陽; 19:株州; 20:南昌;n"); printf("21:福州; 22:南寧; 23:柳州; 24

16、:廣州; 25:深圳.n"); printf("圖 形 的 廣 度 優(yōu) 先 遍 歷 的 頂 點(diǎn) 內(nèi) 容:n"); bfs(i); /* 印出遍歷過程 */ printf("n"); /* 換行 */ break; case's':case'S': printf("n請 輸 入 你 需 要 的 起 始 頂 點(diǎn):n"); scanf("%d",&i); /clrscr(); printf("nn"); printf("以 下 為 各 城 市

17、 的 代 碼:nn"); printf("1:烏魯木齊; 2:呼和浩特; 3:北京; 4:天津; 5:沈陽; n"); printf("6:大連; 7:長春; 8:哈爾濱; 9:西寧; 10:蘭州;n"); printf("11:西安; 12:鄭州; 13:徐州; 14:成都; 15:武漢; n"); printf("16:上海; 17:昆明; 18:貴陽; 19:株州; 20:南昌;n"); printf("21:福州; 22:南寧; 23:柳州; 24:廣州; 25:深圳.n");

18、 printf("圖 形 的 深 度 優(yōu) 先 遍 歷 的 頂 點(diǎn) 內(nèi) 容:n"); dfs(i); /* 印出遍歷過程 */ printf("n"); /* 換行 */ break;printf("n請 問 你 是 否 要 繼 續(xù):y/n");a=getch();if(a!='y'&&'Y')exit(0);4 調(diào)試分析 1、本程序以鄰接多重表為存儲結(jié)構(gòu)。這個程序涉及到圖的生成和圖的深度以及廣度遍歷,文件的保存和讀取，還有棧和隊(duì)列的操作，另外還有森林的生成和打印，路徑的尋找。2、本程序不僅可以進(jìn)行連通無向圖的遍歷，還可以進(jìn)行非連通圖的遍歷。為了方便顯示和理解，現(xiàn)在暫且用一個大寫字母表示一個頂點(diǎn)。邊還可以附加信息，但為了方便操作，暫且不輸入信息。已經(jīng)先把圖的相關(guān)信息保存在了文本文檔里，所以要測試時直接從文件導(dǎo)入，可以減少用手輸入的麻煩，同時也可以減少輸入的錯誤。3、由于構(gòu)造圖時，后輸入的邊是插在先輸入的邊的前面。所以在輸入邊時，可以按字母從大到小的順序輸入。那么顯示圖的時候就可以按字母從小到大的順序顯示。4、程序