图的遍历问题

1、图的遍历问题一 需求分析1. 本程序读入一个图，需要做的是遍历图给出遍历的路径，要求用两种方法，广度优先遍历和深度优先遍历。2. 一个图以邻接矩阵的形式由用户通过键盘输入，对非法输入不做处理，即假设输入都是合法的。3. 在dos界面输出运算结果。4. 测试数据输入输入八个顶点输入顶点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

2、b d h e c f g深度优先遍历： a b c d e f g h二概要设计   算法的基本思想把图以邻接矩阵的形式储存，再根据广度优先遍历和深度优先遍历遍历的特点分别定义不同的函数求解程序的流程程序由三个模块组成（1）输入模块：输入一个顶点数（顶点个数不大于30）和弧数，输入顶点和输入弧。（2）调用循环模块：先把图一邻接矩阵的形式存放，在利用递归求出图的深度和广度优先遍历（3）输出模块：屏幕上显示出结果。伪代码实现：1、深度优先遍历 伪代码：1.访问顶点v；visitedv=1；2.w=顶点v的第一个邻接点；3.while（w存在） if（w未被访问）从顶点w出发递

3、归执行该算法； w=顶点v的下一个邻接点；2、广度优先遍历 伪代码：1.初始化队列Q；2.访问顶点v；visitv=1；顶点v入队列Q；3. while（队列Q非空） v=队列Q的对头元素出队；w=顶点v的第一个邻接点；while（w存在） 如果w未访问，则访问顶点w；visitedw=1；顶点w入队列Q；w=顶点v的下一个邻接点。三详细设计#include"stdio.h"#include"stdlib.h"typedef struct ArcNode/弧结点结构int adjvex;struct ArcNode *next;ArcNode;typed

4、ef struct VNode/顶点结点结构int data;char name;int info;ArcNode *firstarc;VNode,AdjList30;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/队列结构Q

5、ueuePtr 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);

6、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;i<Net.vexnum;i+)N=0;printf("广度优先遍历:");BFS(Net);printf("n"

7、);void CreatGraph(ALGraph &Net)/创建一个邻接表Netint i;char e1,e2;int x1,x2,a20;ArcNode *p,*q;printf("请输入顶点数和弧数:");scanf("%d %d",&Net.vexnum,&Net.arcnum);printf("n请输入%d个顶点:n",Net.vexnum);getchar();for(i=0;i<Net.vexnum;i+)/初始化邻接表N=0;Net.verticesi

8、.data=i;Net.verticesi.firstarc=NULL;for(i=0;i<Net.vexnum;i+)/输入邻接表的顶点名printf("输入顶点%d:",i);scanf("%c",&N);getchar();printf("n请输入%d个弧:n",Net.arcnum);for(i=0;i<Net.arcnum;i+)/输入邻接表的弧结点部分printf("输入弧%d:",i);scanf("%c %c %d",&

9、;e1,&e2,&ai);getchar();Search(Net,x1,e1);/查找输入顶点名在图中的位置Search(Net,x2,e2);p=(ArcNode *)malloc(sizeof(ArcNode);if(Net.verticesx1.firstarc=NULL)/顶点无邻接弧,将弧结点直接接在顶点后Net.verticesx1.firstarc=p;p->adjvex=x2;p->next=NULL;else/顶点已有邻接弧,接在邻接弧后q=Net.verticesx1.firstarc;while(q->next)/找到当前顶点的最后一条

10、邻接弧q=q->next;q->next=p;p->adjvex=x2;p->next=NULL;bool Search(ALGraph &Net,int &x,char e)/查找输入弧名字e在邻接表Net中的顶点序号xint i;for(i=0;i<Net.vexnum;i+)if(N=e)x=Net.verticesi.data;return true;return false;void DFS(ALGraph &Net)/深度遍历图Stack s;ArcNode *p;int x=0,count=0

11、;InitStack(s);printf("%c ",N);/访问第一个顶点push(0,s);N=1;while(s.length!=0)if(Net.verticesx.firstarc=NULL)/一条路走完,退回一步,准备寻找其他路pop(s);if(s.length!=0)x=Gettop(s);elsebreak;else/路未走完,若下一条弧指向的结点已访问则退回一步,未访问则入栈继续访问p=Net.verticesx.firstarc;while(Net.verticesp->adjv

12、=1)if(p->next=NULL)pop(s);x=Gettop(s);break;elsep=p->next;if(Net.verticesp->=0)printf("%c ",Net.verticesp->);push(p->adjvex,s);x=p->adjvex;Net.verticesp->=1;count+;if(count=Net.vexnum-1)/所有的结点均被访问过break;void InitStack(Stack &

13、s)/初始化栈ss.base=(int *)malloc(30*sizeof(int);if(!s.base)printf("栈分配失败!n");exit(0);s.top=s.base;s.length=0;void push(int data,Stack &s)/将data堆入s栈顶*s.top+=data;s.length+;void pop(Stack &s)/删除栈s的顶元素if(s.top=s.base)printf("栈空!无法出栈!n");exit(0);s.top-;s.length-;int Gettop(Stack

14、&s)/返回s栈顶的值return *(s.top-1);void BFS(ALGraph &Net)/广度遍历图Queue Q;ArcNode *p;int x=0,y;InitQueue(Q);EnQueue(0,Q);/访问第一个结点N=1;while(Q.rear!=Q.front)/当队列不空时,遍历未结束p=Net.verticesx.firstarc;while(p!=NULL)/如果第一个顶点有邻接弧则将其所有邻接弧加入队列if(Net.verticesp->=0)EnQueue(p->adjv

15、ex,Q);Net.verticesp->=1;p=p->next;DeQueue(y,Q);/队头出队列并显示printf("%c ",N);if(Q.rear!=Q.front)/如果队列不空则取队头元素,准备遍历下一个结点x=GetQop(Q);elsebreak;void InitQueue(Queue &Q)/初始化队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)printf("队列分配失败!n"

16、);exit(0);Q.front->next=NULL;void EnQueue(int e,Queue &Q)/将元素e作为队列Q的队头QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)printf("队列分配失败!n");exit(0);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;void DeQueue(int &y,Queue &Q)/队列Q的队头出队列,并将其值赋给yQueuePtr p;if(Q.front=Q.r

17、ear)printf("队列为空!无法出队列!n");exit(0);p=Q.front->next;y=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;free(p);int GetQop(Queue &Q)/返回队列Q的队头值return Q.front->next->data; 输入和输出地格式本程序可以解决图的遍历问题，请输入输入一个顶点数和弧数，输入顶点和输入弧/提示等待输入输出/提示 广度优先遍历： 深度优先遍历：五测试结果六、用户使用说明1.本程序的运行环境为dos操作系统2.运用本程序时提示输入输入一个顶点数和弧数，输入顶点和输入弧本程序可以解决图的遍历问题，七实验心得通过本次实验我清楚的了解了图的两种遍历方法。这两种遍历方法都用到了不同的结构来进行运算。如深度优先遍历用到了栈，广度优先遍历则用到了队列。所以在C语言中都要对两者的运算进行定义。通过对图的结构的了解我也较为深刻的了解了图，线性表