图的深度广度优先遍历操作代码.doc

一、实验目的1掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构；2遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍历算法，复习栈和队列的应用；3掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。二、实验内容实验内容1*图的遍历问题描述许多涉及图上操作的算法都是以图的遍历为基础的。写一个程序，演示在连通无向图上遍历全部顶点。基本要求建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列。实现提示设图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有N个顶点，则它们的编号分别为1，2，N）。通过输入图的全部边输入一个图，每条边是两个顶点编号对，可以对边依附顶点编号的输入顺序作出限制（例如从小到大）。编程思路 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意无向是对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，深度遍历算法采用递归调用，其中最主要的是NextAdjVex(Graph G, int v, int w) ；FirstAdjVex（）函数的书写，依次递归下去，广度遍历用队列的辅助。程序代码 头文件：#include#include#define MAX_VERTEX_NUM 30#define MAX_QUEUE_NUMBER 30#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define TRUE 1#define FALSE 0typedef int Status;typedef int InfoType;typedef int Status;/* 定义弧的结构*/typedef struct ArcNode int adjvex; /*该边所指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条边的指针*/ InfoType info; /*该弧相关信息的指针*/ArcNode; /*定义顶点的结构*/typedef struct VNode char data40; /*顶点信息*/ ArcNode *firstarc; /*指向第一条依附该顶点的弧的指针*/VNode,AdjListMAX_VERTEX_NUM;/*定义图的结构*/typedef struct AdjList vertices; int vexnum,arcnum; /*图的当前顶点数和弧数*/ int kind; /*图的类型标志*/Graph;/*定义队列的结构*/typedef structint *elem;int front, rear;Queue;/*功能选择*/void MenuSelect(int w);/*顶点定位*/int LocateVex(Graph G,char *name);/*创建无向图*/void CreateGraph(Graph &G);/*求第一个顶点*/int FirstAdjVex(Graph G, int v);/*求下一个顶点*/int NextAdjVex(Graph G, int v, int w);/*深度递归*/void DFS(Graph G, int v) ;/*深度遍历*/void DFSTravel(Graph G,int v);/*广度遍历*/void BFSTraverse(Graph G,char *name);/*初始化队列*/Status InitQueue(Queue &Q);/*判空*/Status EmptyQueue(Queue Q);/*进队*/Status EnQueue(Queue &Q, int e);/*出队*/Status DeQueue(Queue &Q, int &e);实现文件：#include #includemalloc.h#include tuhead.h#include stdlib.h#include string.hbool visitedMAX_VERTEX_NUM;/* 顶点定位 */int LocateVex(Graph G,char *name)int i;for(i=1;i=G.vexnum;i+) /从1号位置开始存储if(strcmp(name,G.verticesi.data)=0) /相等则找到，返回位序return i;return -1;/* 创建无向图 */void CreateGraph(Graph &G)ArcNode *p;char name110,name210;int i,j,k;printf( 请输入顶点数,按回车键结束：);scanf(%d,&G.vexnum); printf( 请输入弧数,按回车键结束：);scanf(%d,&G.arcnum);printf( 请依次输入顶点名（用空格分开且字符小于10）,按回车键结束：n); printf( );for(i=1;i=G.vexnum;i+) /从1号位置开始存储 scanf(%s,G.verticesi.data); /从一号位置开始初始化G.verticesi.firstarc=NULL; printf(nnnn); printf( 输入小提示n); printf( &1 为避免输入遗漏，最好从选择任意一点，输入所有相邻边n); printf( &2 输入边时格式(用空格分开，即格式为顶点（空格）顶点（空格)）n); printf( 输入小提示nnnn);for(k=0;kadjvex=j; /插入到邻接表中，注意此处为逆向插入到单链表中 p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p; /无向图，注意是对称插入结点 p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=i; p-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=p; /* 求第一个顶点 */ int FirstAdjVex(Graph G, int v) ArcNode *p; if(v=1 & vnextarc=NULL) return 0; else return (p-nextarc-adjvex); /返回第一个顶点字符 return -1; /* 求下一个顶点 */int NextAdjVex(Graph G, int v, int w) /在图G中寻找第v个顶点的相对于w的下一个邻接顶点 ArcNode *p; if(v=1 & v=1 & wadjvex!=w) p=p-nextarc; /在顶点v的弧链中找到顶点w if(p-nextarc!=NULL) return 0; /若已是最后一个顶点，返回0 else return(p-nextarc-adjvex); /返回下一个邻接顶点的序号 return -1;/* 深度递归 */void DFS(Graph G, int v) int w; ArcNode *p; visitedv=1; printf(%s ,G.verticesv.data); /访问第v个顶点 p=G.verticesv.firstarc; /p为依附顶点的第一条边 while (p!=NULL) w=p-adjvex; if(visitedw=0) DFS(G,w); p=p-nextarc; /下移指针 /* 深度遍历 */void DFSTravel(Graph G,int v)for(int i=1;iadjvex; if(visitedw=0) DFS(G,w); p=p-nextarc; /* 初始化队列 */ Status InitQueue(Queue &Q)Q.elem = new intMAX_QUEUE_NUMBER;Q.front = Q.rear = 0; return OK；Status EmptyQueue(Queue Q)if(Q.front=Q.rear)return 0;else return 1;/* 进队列 */Status EnQueue(Queue &Q, int e)if(Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)Q.elemQ.rear = e;else;Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER; return OK； /* 出队列 */Status DeQueue(Queue &Q, int &e)if(Q.rear != Q.front)e = Q.elemQ.front;else ;Q.front = (Q.front+1)%MAX_QUEUE_NUMBER; return OK；/* 广度遍历 */void BFSTraverse(Graph G,char *name)ArcNode *p;int v,w,u,k=0; Queue Q;int visited20;for(v=1;vadjvex; /p边的下一个顶点if(visitedw=0)printf(%s ,G.verticesw.data);visitedw=1;EnQueue(Q,w);p=p-nextarc; /下移指针 主文件：#include #includemalloc.h#include tuhead.h#include stdlib.h#include string.h/* 界面控制 */void main() printf(n# 图的遍历 #n); printf(n $n); printf(n); printf( 1 - 图的创建n); printf( 2 - 图的深度优先遍历n); printf( 3 - 图的广度优先遍历n); printf( 0 - 退出n);printf(n$n); printf(n); printf(请输入选择的操作代码（0-3）按回车键结束n); MenuSelect(1);/* 功能选择 */ void MenuSelect(int w) int select,done; int v; Graph G; char name10; while (done) printf(input the operating code : ); scanf(%d,&select); switch(select) case 1: printf(根据要求创建图:n ); CreateGraph(G); break; case 2: printf(请输入深度优先遍历开始点的名：); scanf(%s,name); v=LocateVex(G,name); /将输入字符找到在顶点数组name