1、实现图地遍历算法某实验报告材料实现图的遍历算法1 需求分析对于下图G，编写一个程序输出从顶点0开始的深度优先遍历序列（非递归算法）和广度优先遍历序列（非递归算法）。2 系统设计1用到的抽象数据类型的定义图的抽象数据类型定义：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集数据关系R： R=VR VR=|v,wV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息基本操作P：CreatGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图GDestroyGraph(&G)初始条件：图G存在操作结果：销毁
2、图GInsertVex(&G,v)初始条件：图G存在，v和图中顶点有相同特征操作结果：在图G中增添新顶点vInsertArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点操作结果：在G中增添弧，若G是无向的则还增添对称弧DFSTraverse(G,Visit()初始条件：图G存在，Visit是顶点的应用函数操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败BFSTraverse(G,Visit()初始条件：图G存在，Visit是顶点的应用函数操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数Visit一
3、次且仅一次。一旦Visit()失败，则操作失败ADT Graph栈的抽象数据类型定义：ADT Stack数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n 约定an端为栈顶，ai端为栈底基本操作：InitStack(&S)操作结果：构造一个空栈SDestroyStack(&S)初始条件：栈S已存在操作结果：将S清为空栈StackEmpty(S)初始条件：栈S已存在操作结果：若栈S为空栈，则返回TRUE，否则FALSEPush(&S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作
4、结果：删除S的栈顶元素，并用e返回其值StackTraverse(S,visit()初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()，一旦visit()失败，则操作失效ADT Stack队列的抽象数据类型定义：ADT Queue数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：Rl=|ai-1,aiD,i=2,n 约定其中ai端为队列头，an端为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列QDestroyQueue(&Q)初始条件：队列Q已存在操作结果：队列Q被销毁，不再存在QueueEmpty(Q)初始条
5、件：队列Q已存在操作结果：若Q为空队列，则返回TRUE，否则FALSEEnQueue(&Q,e)初始条件：队列Q已存在操作结果：插入元素e为Q的新的队尾元素DeQueue(&Q,&e)初始条件：Q为非空队列操作结果：删除Q的队头元素，并用e返回其值ADT Queue2主程序的流程：调用CreateDN函数创建图的邻接表G；调用PrintDN函数输出邻接表G；调用DFSTraverse函数深度优先遍历图；调用BFSTraverse函数广度优先遍历图3函数关系调用图： 主程序3调试分析（1）书上给出了图的广度优先非递归遍历算法，主要是要实现里面的FirstAdjVex(G,u)和NextAdjVe
6、x(G,u,w)函数。我刚开始编写的这两个函数分别为：int FirstAdjVex(ALGraph G,int u)return LocateVex(G,G.verticesu.firstarc-adjvex);int NextAdjVex(ALGraph G,int u,int w)ArcNode *p=G.verticesu.firstarc;while(LocateVex(G,p-adjvex)!=w)p=p-nextarc;p=p-nextarc;if(!p)return -1;return LocateVex(G,p-adjvex);对于书上给出的BFSTraverse函数这样没有
7、问题。但当我仿照BFSTraverse函数编出了DFSTraverse函数后就有问题了。经过分析我把以上两个函数稍作了改动：int FirstAdjVex(ALGraph G,int u)if(!G.verticesu.firstarc)return -1;return LocateVex(G,G.verticesu.firstarc-adjvex);int NextAdjVex(ALGraph G,int u,int w)ArcNode *p=G.verticesu.firstarc;while(p&LocateVex(G,p-adjvex)!=w)p=p-nextarc;if(!p)ret
8、urn FirstAdjVex(G,u);p=p-nextarc;if(!p)return -1;return LocateVex(G,p-adjvex);（2）算法的时间复杂度分析：遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图的边数或有向图的弧数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。4测试结果用需求分析中的测试数据输入：输出：5、用户手册（1）输入顶
9、点数和弧数；（2）输入顶点内容；（3）输入弧，弧尾/弧头/权值（4）回车输出深度优先遍历序列和广度优先遍历序列6、附录源程序：#include #include #define MAX_VERTEX_NUM 20#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define TRUE 1#define OK 1#define FALSE 0#define ERROR 0#define OVERFLOW -2typedef int InfoType;typedef int VertexType;typedef int Status;type
10、def int QElemType;typedef int SElemType;typedef enumDG,DN,UDG,UDNGraphKind;/有向图,有向网,无向图,无向网bool visitedMAX_VERTEX_NUM;typedef struct ArcNodeint adjvex;/该弧所指向的顶点在数组中的下标struct ArcNode *nextarc;InfoType *info;/该弧相关信息的指针ArcNode;typedef struct VNodeVertexType data;/顶点信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针V
11、Node,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志ALGraph;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue
12、;int LocateVex(ALGraph G,VertexType v)/返回数组下标值int i;for(i=0;iMAX_VERTEX_NUM;+i)if(G.verticesi.data=v)return i;return -1;void CreateDN(ALGraph &G)/采用邻接表存储表示,构造有向图G(G.kind=DN)int i,j,k;ArcNode *p;VertexType v1,v2;G.kind=DN;printf(输入顶点数:);scanf(%d,&G.vexnum);printf(输入弧数:);scanf(%d,&G.arcnum);printf(输入顶
13、点:n);for(i=0;iG.vexnum;+i)/构造表头向量scanf(%d,&G.verticesi.data);G.verticesi.firstarc=NULL;/初始化指针for(k=0;kadjvex=j;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;scanf(%d,&p-info);/forStatus Push(SqStack &S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STA
14、CKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Statu
15、s Pop(SqStack &S,SElemType &e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;Status GetTop(SqStack S,SElemType &e)if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;return FALSE;Status InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(s
16、izeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;return OK;Status EnQueue(LinkQueue &Q,QElemType e)QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;Status DeQueue(LinkQueue &Q,QElemType &e)if(Q.front=Q.rear)return ERROR;Que
17、uePtr p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;Status QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return TRUE;return FALSE;int FirstAdjVex(ALGraph G,int u)if(!G.verticesu.firstarc)return -1;return LocateVex(G,G.verticesu.firstarc-adjvex);int NextAdjVex(AL
18、Graph G,int u,int w)ArcNode *p=G.verticesu.firstarc;while(p&LocateVex(G,p-adjvex)!=w)p=p-nextarc;if(!p)return FirstAdjVex(G,u);p=p-nextarc;if(!p)return -1;return LocateVex(G,p-adjvex);void Visit(ALGraph G,int v)printf(%2d,G.verticesv.data);void DFSTraverse(ALGraph G)/按深度优先非递归遍历图G,使用辅助栈S和访问标志数组visite
19、dint v,w;SqStack S;for(v=0;vG.vexnum;v+)visitedv=FALSE;InitStack(S);for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visitedw)Visit(G,w); visitedw=TRUE;Push(S,w);GetTop(S,v);/if/forPop(S,v);GetTop(S,v);/while/ifprintf(n); void BFSTraverse(ALGraph G)/按广度优先非递归遍历图G,使用辅助队列Q和访问标志数组visitedint v,u,w;LinkQueue Q;for(v=0;
20、vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);for(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)/w为u的尚未访问的邻接顶点visitedw=TRUE;Visit(G,w);EnQueue(Q,w);/if/while/ifprintf(n);void PrintDN(ALGraph G)int i;ArcNode *p;printf(顶点:n);for(i=0;iG.vexnum;+i)printf(%2d,G.verticesi.data);printf(n弧:n);for(i=0;iadjvex,p-info);p=p-nextarc;printf(n);/if /forvoid main()ALGraph G;CreateDN(G);PrintDN(G);printf(深度优先遍历:);DFSTraverse(G);printf(广度优先遍历:);BFSTraverse(G);
