《图的深度广度遍历算法与数据结构课程设计》由会员分享，可在线阅读，更多相关《图的深度广度遍历算法与数据结构课程设计（15页珍藏版）》请在金锄头文库上搜索。
1、图的操作一、问题描述 图是一种较线性表和树更为复杂的数据结构。在图形结构中，节点间的关系可以是任意的，图中任意两个数据元素之间都可以相关。由此，图的应用极为广泛。现在邻接矩阵和邻接表的存储结构下，完成图的深度、广度遍历。二、基本要求 1、选择合适的存储结构完成图的建立； 2、建立图的邻接矩阵，能按矩阵方式输出图，并在此基础上，完成图的深度和广度遍历，输出遍历序列； 3、建立图的邻接表，并在此基础上，完成图的深度和广度遍历，输出遍历序列；三、测试数据四、算法思想1、邻接矩阵 顶点向量的存储。用两个数组分别存储数据（定点）的信息和数据元素之间的关系（边或弧）的信息。2、邻接表 邻接表是图的一种链式
2、存储结构。在邻接表中，对图中每个定点建立一个单链表，第i个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成，其中邻接点域（adjvex）指示与定点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的节点；数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个头节点。在表头节点中，除了设有链域（firstarc）指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域（data）。3、图的深度遍历 深度优先搜索遍历类似于树的先根遍历，是树的先跟遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发， 访问此顶点
3、，然后依次从v的未被访问的邻接点出发深度优先遍历图，甚至图中所有和v相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。4、图的广度遍历 广度优先遍历类似于树的按层次遍历过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先与“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到
4、为止。五、模块划分一、基于邻接矩阵的深广度遍历 1Status InitQueue(LinkQueue *Q)根据已知Q初始化队列2Status QueueEmpty (LinkQueue Q)判断队列是否为空3Status EnQueue(LinkQueue *Q, QElemType e)将e压入队尾4Status DeQueue(LinkQueue *Q, QElemType *e)取队头元素e5int LocateVex(MGraph G,VertexType v)定位定点v6void CreateGraph(MGraph *G)建立无向图的邻接矩阵7void PrintGraph(M
5、Graph G)输出邻接矩阵的无向图8int FirstAdjVex(MGraph G,int v)第一个邻接点的定位9int NextAdjVex(MGraph G,int v,int w)查找下一个邻接点10void Dfs(MGraph G, int v)实现图的一次遍历11void DfsTraverse(MGraph G)实现图的深度遍历12void BfsTraverse(MGraph G)实现图的广度遍历13Main主函数 二、基于邻接表实现图的深广度遍历1Status InitQueue(LinkQueue *Q)根据已知Q初始化队列2Status QueueEmpty (Li
6、nkQueue Q)判断队列是否为空3Status EnQueue(LinkQueue *Q, QElemType e)将e压入队尾4Status DeQueue(LinkQueue *Q, QElemType *e)取队头元素e5void createALGraph(ALGraph *G)建立无向图的邻接矩阵6void PrintGraph(MGraph G)输出邻接矩阵的无向图7int FirstAdjVex(MGraph G,int v)第一个邻接点的定位8int NextAdjVex(MGraph G,int v,int w)查找下一个邻接点9void Dfs(MGraph G, in
7、t v)实现图的一次深度遍历10void DfsTraverse(MGraph G)实现图的深度遍历11void BFS(ALGraph G, int v)实现图的一次广度遍历12void BfsTraverse(MGraph G)实现图的广度遍历13Void Main主函数 六、数据结构/(ADT)1、基于邻接矩阵的图的类型定义typedef struct ArcCell VRType adj; /*图中有1/0表示是否有边，网中表示边上的权值*/ /* InfoType *info; 与边相关的信息*/ ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_
8、NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum,arcnum; /*图中当前顶点数和边数*/ MGraph;2、基于邻接表的图的类型定义typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; /*表节点*/ typedef struct TElemType data; ArcNode *firstarc;VNode,AdjListMAXVER; /*表节点*/typedef
9、 struct AdjList vertices; int vexnum,arcnum; /*图中当前顶点数和边数*/ ALGraph;七、源程序一、基于邻接矩阵的图的深度、广度遍历#include stdlib.h#include stdio.h#include string.h#define TRUE 1#define FALSE 0#define OVERFLOW -2#define OK 1#define ERROR 0typedef int Status;#define INFINITY INT_MAX /*最大值“无穷”*/#define MAX_VERTEX_NUM 20 /*最
10、大顶点个数*/typedef int Boolean;typedef char VertexType20;typedef int VRType;/*以下为队列的操作*/*队列的类型定义*/typedef int QElemType;typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear; LinkQueue;/*初始化队列*/Status InitQueue(LinkQueue *Q) (*Q).front=(*Q
11、).rear=(QueuePtr)malloc(sizeof(QNode);if(!(*Q).front) exit(OVERFLOW); (*Q).front-next=NULL; return OK; /*判断队列是否为空*/Status QueueEmpty (LinkQueue Q) if (Q.front=Q.rear) return TRUE; else return FALSE; /*入队列*/Status EnQueue(LinkQueue *Q, QElemType e) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if (!p
12、) exit(OVERFLOW); p-data=e; p-next=NULL; (*Q).rear-next=p; (*Q).rear=p; return OK; /*出队列*/Status DeQueue(LinkQueue *Q, QElemType *e) QueuePtr p; if (*Q).front=(*Q).rear) return ERROR; p=(*Q).front-next; *e=p-data; (*Q).front-next=p-next; if (*Q).rear=p) (*Q).rear=(*Q).front; free(p); return OK; /*以下
13、为图的操作*/*图的类型定义*/typedef struct ArcCell VRType adj; /*图中有1/0表示是否有边，网中表示边上的权值*/ /* InfoType *info; 与边相关的信息*/ ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum,arcnum; /*图中当前顶点数和边数*/ MGraph;/* 顶点在顶点向量中的定位*/int LocateVex(MGraph G,VertexType v) int i; for(i=0;iG.vexnum;i+) if (strcmp(v,G.vexsi)=0) break; return i;/*建立无向图的邻接矩阵*/void CreateGraph(MGraph *G) int i,j,k; VertexType v1,v2; printf(nInput MG vexnum,arcnum:); scanf(%d,%d,&(*G).ve
