图遍历的演示

1、 约瑟夫环实验报告1 需求分析1、以邻接多重表为存储结构；2、实现连通和非连通的无向图的深度优先和广度优先遍历；3、要求利用栈实现无向图的深度优先遍历；4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集；5、用凹入表打印生成树；6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径；2 概要设计1. 设定图的抽象数据类型2. 栈的抽象数据类型定义3. 队列的抽象数据类型定义3 详细设计程序设计如下：#include #include #include#define MAXQUEUE 70 /* 伫列的最大容量 */struct node /* 图形顶点

2、结构宣告 */ int vertex; /* 顶点资料 */ struct node *nextnode; /* 指下一顶点的指标 */;typedef struct node *graph; /* 图形的结构新型态 */struct node head61; /* 图形顶点结构数组 */int visited61; /* 遍历记录数组 */int queueMAXQUEUE; /* 伫列的数组宣告 */int front = -1; /* 伫列的前端 */int rear = -1; /* 伫列的后端 */* - */* 建立图形 */* - */void creategraph(int *

3、node,int num) graph newnode; /* 新顶点指标 */ graph ptr; int from; /* 边线的起点 */ int to; /* 边线的终点 */ int i; for ( i = 0; i vertex = to; /* 建立顶点内容 */ newnode-nextnode = NULL; /* 设定指标初值 */ ptr = &(headfrom); /* 顶点位置 */ while ( ptr-nextnode != NULL ) /* 遍历至链表尾 */ ptr = ptr-nextnode; /* 下一个顶点 */ ptr-nextnode =

4、 newnode; /* 插入结尾 */ /* - */* 伫列资料的存入 */* - */int enqueue(int value) if ( rear = MAXQUEUE ) /* 检查伫列是否全满 */ return -1; /* 无法存入 */ rear+; /* 后端指标往前移 */ queuerear = value; /* 存入伫列 */* - */* 伫列资料的取出 */* - */int dequeue() if ( front = rear ) /* 检查伫列是否是空 */ return -1; /* 无法取出 */ front+; /* 前端指标往前移 */ retu

5、rn queuefront; /* 伫列取出 */* - */* 图形的广度优先搜寻法 */* - */void bfs(int current) graph ptr; /* 处理第一个顶点 */ enqueue(current); /* 将顶点存入伫列 */ visitedcurrent = 1; /* 记录已遍历过 */ printf(%d ,current); /* 印出遍历顶点值 */ while ( front != rear ) /* 伫列是否是空的 */ current = dequeue(); /* 将顶点从伫列取出 */ ptr = headcurrent.nextnode;

6、 /* 顶点位置 */ while ( ptr != NULL ) /* 遍历至链表尾 */ if ( visitedptr-vertex = 0 ) /* 如过没遍历过 */ enqueue(ptr-vertex); /* 递回遍历呼叫 */ visitedptr-vertex = 1; /* 记录已遍历过 */ /* 印出遍历顶点值 */ printf(%d ,ptr-vertex); ptr = ptr-nextnode; /* 下一个顶点 */ /* - */* 图形的深度优先搜寻法 */* - */void dfs(int current) graph ptr; visitedcur

7、rent = 1; /* 记录已遍历过 */ printf(%d ,current); /* 印出遍历顶点值 */ ptr = headcurrent.nextnode; /* 顶点位置 */ while ( ptr != NULL ) /* 遍历至链表尾 */ if ( visitedptr-vertex = 0 ) /* 如过没遍历过 */ dfs(ptr-vertex); /* 递回遍历呼叫 */ ptr = ptr-nextnode; /* 下一个顶点 */ /* - */* 主程式: 建立图形后,将遍历内容印出. */* - */int main()/clrscr();while(1

8、) char c,a; graph ptr; int i; int node 60 2 = 1, 10, 10, 1, /* 边线数组 */ 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, 14, 1

9、7, 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();if(c!=y&Y)exit(0); /clrscr()

10、;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(16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;n); printf(21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.n); for (i=1;i=25;i+ ) headi.vertex=i;

11、/* 设定顶点值 */ headi.nextnode=NULL; /* 清除图形指标 */ visitedi=0; /* 设定遍历初值 */ creategraph(node,60); /* 建立图形 */ printf(图 形 的 邻 接 链 表 内 容:n); for (i=1;i,headi.vertex); /* 顶点值 */ ptr=headi.nextnode; /* 顶点位置 */ while(ptr!=NULL) /* 遍历至链表尾 */ printf(%d ,ptr-vertex); /* 印出顶点内容 */ ptr=ptr-nextnode; /* 下一个顶点 */ pri

12、ntf(nn);printf(请 选 择 你 需 要 的 操 作n);printf(1、图形的广度优先遍历请输入:g或Gn);printf(2、图形的深度优先遍历请输入:s或Sn); c=getch(); switch(c) caseg:caseG: printf(n请 你 输 入 你 需 要 的 起 始 顶 点:n); scanf(%d,&i); /clrscr(); printf(nn); printf(以 下 为 各 城 市 的 代 码:nn); printf(1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳; n); printf(6:大连; 7:长春; 8:哈尔滨;

13、9:西宁; 10:兰州;n); printf(11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉; n); printf(16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;n); printf(21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.n); printf(图 形 的 广 度 优 先 遍 历 的 顶 点 内 容:n); bfs(i); /* 印出遍历过程 */ printf(n); /* 换行 */ break; cases:caseS: printf(n请 输 入 你 需 要 的 起 始 顶 点:n); scanf(%d,&i);

14、/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(16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;n); printf(21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.n); printf(图 形 的 深 度 优 先 遍 历

15、 的 顶 点 内 容:n); dfs(i); /* 印出遍历过程 */ printf(n); /* 换行 */ break;printf(n请 问 你 是 否 要 继 续:y/n);a=getch();if(a!=y&Y)exit(0);4 调试分析 1、本程序以邻接多重表为存储结构。这个程序涉及到图的生成和图的深度以及广度遍历,文件的保存和读取，还有栈和队列的操作，另外还有森林的生成和打印，路径的寻找。2、本程序不仅可以进行连通无向图的遍历，还可以进行非连通图的遍历。为了方便显示和理解，现在暂且用一个大写字母表示一个顶点。边还可以附加信息，但为了方便操作，暂且不输入信息。已经先把图的相关信息保存在了文本文档里，所以要测试时直接从文件导入，可以减少用手输入的麻烦，同时也可以减少输入的错误。3、由于构造图时，后输入的边是插在先输入的边的前面。所以在输入边时，可以按字母从大到小的顺序输入。那么显示图的时候就可以按字母从小到大的顺序显示。4、程序定义了一个二倍顶点长的数组存放输入的边，以便程序可以把它保存到文件里。故耗费了一定的内存空间。5 用户手册1. 该程序在windows系统下运行2. 先输入任