图遍历的演示

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

2、#define MAXQUEUE 70 /* 伫列的最大容量 */struct node /* 图形顶点结构宣告 */ int vertex; /* 顶点资料 */ struct node *nextnode; /* 指下一顶点的指标 */;typedef struct node *graph; /* 图形的结构新型态 */struct node head61; /* 图形顶点结构数组 */int visited61; /* 遍历记录数组 */int queueMAXQUEUE; /* 伫列的数组宣告 */int front = -1; /* 伫列的前端 */int rear = -1; /*

3、 伫列的后端 */* - */* 建立图形 */* - */void creategraph(int *node,int num) graph newnode; /* 新顶点指标 */ graph ptr; int from; /* 边线的起点 */ int to; /* 边线的终点 */ int i; for ( i = 0; i < num; i+ ) /* 读取边线的回路 */ from = nodei*2; /* 边线的起点 */ to = nodei*2+1; /* 边线的终点 */ /* 建立新顶点记忆体 */ newnode = ( graph ) malloc(sizeo

4、f(struct node); newnode->vertex = to; /* 建立顶点内容 */ newnode->nextnode = NULL; /* 设定指标初值 */ ptr = &(headfrom); /* 顶点位置 */ while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */ ptr = ptr->nextnode; /* 下一个顶点 */ ptr->nextnode = newnode; /* 插入结尾 */ /* - */* 伫列资料的存入 */* - */int enqueue(int value)

5、 if ( rear >= MAXQUEUE ) /* 检查伫列是否全满 */ return -1; /* 无法存入 */ rear+; /* 后端指标往前移 */ queuerear = value; /* 存入伫列 */* - */* 伫列资料的取出 */* - */int dequeue() if ( front = rear ) /* 检查伫列是否是空 */ return -1; /* 无法取出 */ front+; /* 前端指标往前移 */ return queuefront; /* 伫列取出 */* - */* 图形的广度优先搜寻法 */* - */void bfs(int

6、 current) graph ptr; /* 处理第一个顶点 */ enqueue(current); /* 将顶点存入伫列 */ visitedcurrent = 1; /* 记录已遍历过 */ printf("%d ",current); /* 印出遍历顶点值 */ while ( front != rear ) /* 伫列是否是空的 */ current = dequeue(); /* 将顶点从伫列取出 */ ptr = headcurrent.nextnode; /* 顶点位置 */ while ( ptr != NULL ) /* 遍历至链表尾 */ if (

7、visitedptr->vertex = 0 ) /* 如过没遍历过 */ enqueue(ptr->vertex); /* 递回遍历呼叫 */ visitedptr->vertex = 1; /* 记录已遍历过 */ /* 印出遍历顶点值 */ printf("%d ",ptr->vertex); ptr = ptr->nextnode; /* 下一个顶点 */ /* - */* 图形的深度优先搜寻法 */* - */void dfs(int current) graph ptr; visitedcurrent = 1; /* 记录已遍历过

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

9、le(1) 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, 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; /* 设定顶点值 */ headi.nextnode=NULL; /* 清除图形指标 */ visitedi=0; /* 设定遍历初值 */ creategraph(node,60); /* 建立图形 */ printf("图 形 的 邻 接 链 表 内 容:n"); for (i=1;i

13、<=25;i+) if(i%3=0)printf("n"); printf("顶点%d=>",headi.vertex); /* 顶点值 */ ptr=headi.nextnode; /* 顶点位置 */ while(ptr!=NULL) /* 遍历至链表尾 */ printf("%d ",ptr->vertex); /* 印出顶点内容 */ ptr=ptr->nextnode; /* 下一个顶点 */ printf("nn");printf("请 选 择 你 需 要 的 操 作n

14、");printf("1、图形的广度优先遍历请输入:'g'或'G'n");printf("2、图形的深度优先遍历请输入:'s'或'S'n"); c=getch(); switch(c) case'g':case'G': printf("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("图 形 的 广 度 优 先 遍 历 的 顶 点 内 容:n"); bfs(i); /* 印出遍历过程 */ printf("n"); /* 换行 */ break; case's':case'S': printf("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("图 形 的 深 度 优 先 遍 历 的 顶 点 内 容:n"); dfs(i); /* 印出遍历过程 */ printf("n"); /* 换行 */ break;printf("n请 问 你 是 否 要 继 续:y/n");a=getch();if(a!='y'&&'Y')exit(0);4 调试分析 1、本程序以邻接多重表为存储结构。这个程序涉及到图的生成和图的深度以及广度遍历,文件的保存和读取，还有栈和队列的操作，另外还有森林的生成和打印，路径的寻找。2、本程序不仅可以进行连通无向图的遍历，还可以进行非连通图的遍历。为了方便显示和理解，现在暂且用一个大写字母表示一个顶点。边还可以附加信息，但为了方便操作，暂且不输入信息。已经先把图的相关信息保存在了文本文档里，所以要测试时直接从文件导入，可以减少用手输入的麻烦，同时也可以减少输入的错误。3、由于构造图时，后输入的边是插在先输入的边的前面。所以在输入边时，可以按字母从大到小的顺序输入。那么显示图的时候就可以按字母从小到大的顺序显示。4、程序