数据结构 课程设计报告书 设 计 题 目 图遍历的演示 姓 名 专 业 班 级 学 号 指 导 教 师 成 绩 评 语
2014年6月20日
目 录
目 录 ............................................... 1 一、功能需求 ...................................... 2 （一）原始数据 .................................... 2 （二）系统功能 .................................... 2 三、程序总体设计 .................................. 2 （一）数据结构 .................................... 2 (二) 函数原形清单 ................................. 3 （三）程序总体框架 ................................ 4 （四）详细代码 .................................... 4 四、程序清单 ..................................... 15 五、总结 ......................................... 18
1
一、功能需求
以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列和相应生成树的边集。
二、系统功能和原始数据
（一）原始数据
设图的顶点不超过20个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为1,2，…，n）。通过输入图的全部边输入一个图，每条边为一对整数，可以对边的输入顺序作某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。
（二）系统功能
1.创建无向图 2.打印无向图 3.深度优先搜索 4.广度优先搜索
三、程序总体设计
（一）数据结构
typedef struct EBox {
int mark;//访问标记,1代表已访问，0代表未访问 int ivex,jvex;//该边依附的两个顶点的位置
struct EBox *ilink,*jlink;//分别指向依附这两个顶点的下一条边 //InfoType *info;//该边信息指针
}EBox;
typedef struct VexBox {
VertexType data;
EBox *firstedge;//指向第一条依附该顶点的边
}VexBox; typedef struct {
//---------------------------------------------------队列的定义
2
VexBox adjmulist[NUM];
int vexnum,edgenum;//无向图的当前顶点数和边数
}AMLGraph;