图的遍历问题.doc

图的遍历问题 需求分析 本程序读入一个图，需要做的是遍历图给出遍历的路径，要求用两种方法，广度优先遍历和深度优先遍历。 一个图以邻接矩阵的形式由用户通过键盘输入，对非法输入不做处理，即假设输入都是合法的。 在dos界面输出运算结果。 测试数据 输入 输入八个顶点 输入顶点0：a 输入顶点1：b 输入顶点2：c 输入顶点3：d 输入顶点4：e 输入顶点5：f 输入顶点6：g 输入顶点7：h 输入九条弧 输入弧0：a b 1 输入弧1：b d 1 输入弧2：be 1 输入弧3：d h 1 输入弧4：e h 1 输入弧5：a c 1 输入弧6：c f 1 输入弧7：c g 1 输入弧8：f g 1 输出 广度优先遍历： a b d h e c f g 深度优先遍历： a b c d e f g h 二．概要设计 ?? 算法的基本思想 把图以邻接矩阵的形式储存，再根据广度优先遍历和深度优先遍历遍历的特点分别定义不同的函数求解 程序的流程 程序由三个模块组成 （1）输入模块：输入一个顶点数（顶点个数不大于30）和弧数，输入顶点和输入弧。 （2）调用循环模块：先把图一邻接矩阵的形式存放，在利用递归求出图的深度和广度优先遍历 （3）输出模块：屏幕上显示出结果。 伪代码实现： 1、深度优先遍历 伪代码：1.访问顶点v；visited[v]=1；2.w=顶点v的第一个邻接点；3.while（w存在） if（w未被访问）从顶点w出发递归执行该算法； w=顶点v的下一个邻接点； 2、广度优先遍历 伪代码：1.初始化队列Q；2.访问顶点v；visit[v]=1；顶点v入队列Q；3. while（队列Q非空） v=队列Q的对头元素出队；w=顶点v的第一个邻接点；while（w存在） 如果w未访问，则访问顶点w；visited[w]=1；顶点w入队列Q；w=顶点v的下一个邻接点。 三．详细设计 #includestdio.h #includestdlib.h typedef struct ArcNode {//弧结点结构 int adjvex; struct ArcNode *next; }ArcNode; typedef struct VNode {//顶点结点结构 int data; char name; int info; ArcNode *firstarc; }VNode,AdjList[30]; typedef struct {//邻接表结构 AdjList vertices; int vexnum,arcnum; }ALGraph; typedef struct Stack {//栈结构 int *top,*base; int length; }Stack; typedef struct QNode {//队列结点结构 int data; struct QNode *next; }QNode,*QueuePtr; typedef struct Queue {//队列结构 QueuePtr front,rear; }Queue; void CreatGraph(ALGraph Net); void DFS(ALGraph Net); bool Search(ALGraph Net,int x,char e); void InitStack(Stack s); void push(int data,Stack s); void pop(Stack s); int Gettop(Stack s); void BFS(ALGraph Net); void InitQueue(Queue Q); void EnQueue(int e,Queue Q); void DeQueue(int y,Queue Q); int GetQop(Queue Q); main() { ALGraph Net; int i; CreatGraph(Net); printf(深度优先遍历:); DFS(Net); printf(\n); for(i=0;iNet.vexnum;i++) Net.vertices[i].info=0; printf(广度优先遍历:); BFS(Net); printf(\n); } void CreatGraph(ALGraph Net) {//创建一个邻接表Net int i; char e1,e2; int x1,x2,a[20]; ArcNode *p,*q; printf(请输入顶点数和弧数:); scanf(%d %d,Net.vexnum,Net.arcnum); printf(\n请输入%d个顶点:\n,Net.vexnum); getc