1、 目 录 1.需求分析 . 1 1.1 问题描述 . 1 1.2 系统功能 . 1 2.概要设计 . 2 2.1 流程图 . 2 2.2 结构体、函数及说明 . 3 3.详细设计 . 4 3.1 遍历函数设计 . 4 3.2 容错性方法设计 . 4 3.3 生成邻接表设计 . 5 3.4 邻接表遍历设计 . 6 4.程序源代码 . 7 5.调试分析和测试结果 16 5.1 调试分析 16 5.1 调试案例 16 5.3 测试过程、结果截图： 17 5.3.1 容错性测试： 17 5.3.2 无向图（案例一）测试： 20 5.3.3 有向图（案例二）测试： 22 6.课程设计总结 24 参考文献
2、 25 1 1.需求分析 1.1 问题描述 （1）对任意给定的图（顶点数和边数自定），建立它的邻接表并输出。 （2）然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空） 实现图的广度优先搜索遍历。 （3）画出搜索顺序示意图。 1.2 系统功能 （1）首先输入图的类型，有向或无向图（因为遍历与权值无关，所以没有涉及带权 图）。然后输入图的顶点数、边数和各条边，之后生成该图的邻接表并输出。 （2）再输入要遍历该图的起点，然后从所输入的点广度搜索该图的邻接表，并按遍 历顺序输出顶点内容。之后决定是否继续遍历该图或输入另一个需要遍历的图亦或是结束 程序。 2 2.概要设计 2.1 流
3、程图 是 否 否 是 图 2-1 流程图 开始 输入图的类 确定图的类型 输入有向图 输入无向图 广度优先遍历该图 输入从哪个顶点开始遍历该图 是否从其他顶点开始 重新遍历该图 结束 是否结束 3 2.2 结构体、函数及说明 typedef struct ArcNode/邻接表表结点 int adjvex;/该弧所指向的顶点位置 struct ArcNode *nextarc;/指向下一条弧的指针 /InfoType *info;/该弧相关信息指针 ArcNode; typedef struct VNode/邻接表头结点 VertexType data;/结点信息 ArcNode *first
4、arc;/指向第一条依附该结点的弧的指针 VNode,AdjListMAX_VERTEX_NUM; typedef struct/图 AdjList Vertices;/邻接表头结点数组 int vexnum,arcnum;/图的当前顶点数和弧数 int kind;/图的种类标志(有向图:0,无向图:1) ALGraph; void print(int v)/输出顶点信息 int FirstAdjVex(ALGraph G,int u)/在邻接表 G 中取第 u 个头结点 void NextAdjVex(ALGraph G,int u,int w)/ 在邻接表 G 中取第 u 个头结点之后的
5、结点 w 的下一结点 void BFSTraverse(ALGraph G,queue Q,bool visited,int m,int n,void (*Visit)(int)/使用辅助队列 Q 从邻接表结点 m 开始 n 结束广度遍历邻接表图 G 4 3.详细设计 3.1 遍历函数设计 void BFSTraverse(ALGraph G,queue Q,bool visited,int m,int n,void (*Visit)(int)/使用辅助队列 Q 从邻接表结点 m 开始 n 结束广度遍历邻接表图 G /按广度优先非递归遍历图 G。使用辅助队列 Q 和访问标志数组 visited
6、。 while(!Q.empty() Q.pop();/置空的辅助队列 Q for(int v=m;v= 0; w = NextAdjVex(G,u,w)/ 从以 u 为头结点的邻接表开始遍历到链表中的最后一个结点 if(!visitedw)/w 为 u 的尚未访问的邻接结点 visitedw=true; Visit(w);/访问 w Q.push(w);/w 入队列 /if /while /if /BFSTraverse*/ 3.2 容错性方法设计 coutnextarc= NULL;/设置 n2 之后的结 6 点为空 else/如果 n1 后已有结点 ArcNode *p = G.Verticesn1.firstarc;/新建结点指针 while(p-nextarc)!=NULL) p = p-nextarc;/将指针指向链表中最后一个结点 p-nextarc = new ArcNode;/在最后增加一个新结点 p-nextarc-adjve
