图遍历的演示_20098.doc

图 遍 历 的 演 示 设 计 学号:2003040140236 姓名:张耀振 班级:计算机科学技术02班 2005.07.14 图的遍历设计 很多涉及图上操作的算法都是以图的遍历操作为基础的.试写一个程序,演示在连通的无向图上访问全部结点的操作. 一.问题描述 1.基本要求: 以邻接多重点为存储结构,实现连通无向图的深度优先遍历和广度优先遍历.以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集. 2.测试数据: 教科书图7.33.暂时忽视里程,起点为北京. 二.概要设计 抽象数据类型图的定义如下: // ---------------------------------------- // 建立图形 // ---------------------------------------- void creategraph(int node[][2],int num); // ---------------------------------------- // 伫列资料的存入 // ---------------------------------------- int enqueue(int value); // ---------------------------------------- // 伫列资料的取出 // ---------------------------------------- int dequeue(); // ---------------------------------------- // 图形的广度优先搜寻法 // ---------------------------------------- void bfs(int current); // ---------------------------------------- // 图形的深度优先搜寻法 // ---------------------------------------- void dfs(int current); 三.详细设计 顶点,边和图类型 #define MAXQUEUE 70 // 伫列的最大容量 struct node // 图形顶点结构宣告 { int vertex; // 顶点资料 struct node *nextnode; // 指下一顶点的指标 }; typedef struct node *graph; // 图形的结构新型态 struct node head[61]; // 图形顶点结构数组 各函数的实现 // ---------------------------------------- // 建立图形 // ---------------------------------------- void creategraph(int node[][2],int num) { graph newnode; // 新顶点指标 graph ptr; int from; // 边线的起点 int to; // 边线的终点 int i; for ( i = 0; i num; i++ ) // 读取边线的回路 { from =node[i][0]; // 边线的起点 to = node[i][1]; // 边线的终点 //printf([