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

《图的深度广度优先遍历操作代码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、实验目的1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构；2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍历算法，复习栈和队列的应用；3．掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。二、实验内容实验内容1**图的遍历[问题描述]许多涉及图上操作的算法都是以图的遍历为基础的。写一个程序，演示在连通无向图上遍历全部顶点。[基本要求]建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列。[实现提示]设

2、图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有N个顶点，则它们的编号分别为1，2，…，N）。通过输入图的全部边输入一个图，每条边是两个顶点编号对，可以对边依附顶点编号的输入顺序作出限制（例如从小到大）。[编程思路]首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意无向是对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(GraphG,char*name)，以便后来的遍历操作，深度遍历算法采用递归调用，其中最主要的是NextAdjVex(GraphG,intv,intw)；FirstAdjVex（）函数的书

3、写，依次递归下去，广度遍历用队列的辅助。[程序代码]头文件：#include#include#defineMAX_VERTEX_NUM30#defineMAX_QUEUE_NUMBER30#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineTRUE1#defineFALSE0typedefintStatus;typedefintInfoType;typedefintStatus;/*定义弧的结构*/typedefstruct

4、ArcNode{intadjvex;/*该边所指向的顶点的位置*/structArcNode*nextarc;/*指向下一条边的指针*/InfoTypeinfo;/*该弧相关信息的指针*/}ArcNode;/*定义顶点的结构*/typedefstructVNode{chardata[40];/*顶点信息*/ArcNode*firstarc;/*指向第一条依附该顶点的弧的指针*/}VNode,AdjList[MAX_VERTEX_NUM];/*定义图的结构*/typedefstruct{AdjListvertices;intvexnum,ar

5、cnum;/*图的当前顶点数和弧数*/intkind;/*图的类型标志*/}Graph;/*定义队列的结构*/typedefstruct{int*elem;intfront,rear;}Queue;/*功能选择*/voidMenuSelect(intw);/*顶点定位*/intLocateVex(GraphG,char*name);/*创建无向图*/voidCreateGraph(Graph&G);/*求第一个顶点*/intFirstAdjVex(GraphG,intv);/*求下一个顶点*/intNextAdjVex(GraphG,int

6、v,intw);/*深度递归*/voidDFS(GraphG,intv);/*深度遍历*/voidDFSTravel(GraphG,intv);/*广度遍历*/voidBFSTraverse(GraphG,char*name);/*初始化队列*/StatusInitQueue(Queue&Q);/*判空*/StatusEmptyQueue(QueueQ);/*进队*/StatusEnQueue(Queue&Q,inte);/*出队*/StatusDeQueue(Queue&Q,int&e);实现文件：#include#in

7、clude"malloc.h"#include"tuhead.h"#include"stdlib.h"#include"string.h"boolvisited[MAX_VERTEX_NUM];/************************************************************顶点定位************************************************************/intLocateVex(GraphG,char*name){inti;for(i=1;i<=G.v

8、exnum;i++)//从1号位置开始存储if(strcmp(name,G.vertices[i].data)==0)//相等则找到，返回位序returni;return-1;}