图的深度广度遍历(算法与数据结构课程设计)(12页).doc
-图的深度广度遍历(算法与数据结构课程设计)-第 12 页图的操作一、问题描述 图是一种较线性表和树更为复杂的数据结构。在图形结构中，节点间的关系可以是任意的，图中任意两个数据元素之间都可以相关。由此，图的应用极为广泛。现在邻接矩阵和邻接表的存储结构下，完成图的深度、广度遍历。二、基本要求 1、选择合适的存储结构完成图的建立； 2、建立图的邻接矩阵，能按矩阵方式输出图，并在此基础上，完成图的深度和广度遍历，输出遍历序列； 3、建立图的邻接表，并在此基础上，完成图的深度和广度遍历，输出遍历序列；三、测试数据四、算法思想1、邻接矩阵 顶点向量的存储。用两个数组分别存储数据（定点）的信息和数据元素之间的关系（边或弧）的信息。2、邻接表 邻接表是图的一种链式存储结构。在邻接表中，对图中每个定点建立一个单链表，第i个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成，其中邻接点域（adjvex）指示与定点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的节点；数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个头节点。在表头节点中，除了设有链域（firstarc）指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域（data）。3、图的深度遍历 深度优先搜索遍历类似于树的先根遍历，是树的先跟遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发， 访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，甚至图中所有和v相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。4、图的广度遍历 广度优先遍历类似于树的按层次遍历过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先与“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。五、模块划分一、基于邻接矩阵的深广度遍历 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(MGraph 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 (LinkQueue 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, int 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_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 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 /*最大顶点个数*/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).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) 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; /*以下为图的操作*/*图的类型定义*/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;i<G.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).vexnum,&(*G).arcnum); printf("Input %d vexs:",(*G).vexnum); for(i=0;i<(*G).vexnum;i+) /*输入顶点向量*/ scanf("%s",(*G).vexsi); printf("vexs listn"); for(i=0;i<G->vexnum;i+) /*输出顶点向量*/ puts(G->vexsi); for(i=0;i<(*G).vexnum;i+) /*邻接矩阵初始化*/ for(j=0;j<(*G).vexnum;j+)(*G).arcsij.adj=0; printf("nInput %d arcs(vi vj):n",(*G).arcnum); for(k=0;k<(*G).arcnum;k+) /*输入无权图的边*/ scanf("%s%s",v1,v2); i=LocateVex(*G,v1); j=LocateVex(*G,v2); (*G).arcsij.adj=1; (*G).arcsji=(*G).arcsij;/*按邻接矩阵方式输出无向图*/void PrintGraph(MGraph G) int i,j; printf("nMGraph:n"); for(i=0; i<G.vexnum; i+) printf("%10s",G.vexsi); for(j=0; j<G.vexnum; j+) printf("%4d",G.arcsij.adj); printf("n");/* 查找第1个邻接点 */int FirstAdjVex(MGraph G,int v) int j,p=-1; for(j=0;j<G.vexnum;j+) if (G.arcsvj.adj=1) p=j; break; return p;/* 查找下一个邻接点 */int NextAdjVex(MGraph G,int v,int w) int j,p=-1; for(j=w+1;j<G.vexnum;j+)csvj.adj=1) p=j; break; return p;/*深度遍历*/Boolean visitedMAX_VERTEX_NUM; /* 设置全局的访问标志数组 */void Dfs(MGraph G, int v) int w; visitedv=TRUE; printf("%s",G.vexsv); for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w) if(!visitedw) Dfs(G,w);void DfsTraverse(MGraph G) int v; for (v=0; v<G.vexnum; v+) visitedv=FALSE; for(v=0; v<G.vexnum; v+) if (!visitedv) Dfs(G,v);/* 广度遍历 */void BfsTraverse(MGraph G) int v,u,w; LinkQueue Q; for(v=0; v<G.vexnum; v+) visitedv=FALSE; InitQueue(&Q); for(v=0; v<G.vexnum; v+) if (!visitedv) visitedv=TRUE; printf("%s",G.vexsv); EnQueue(&Q,v); while(!QueueEmpty(Q) DeQueue(&Q,&u); for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w) if (!visitedw) visitedw=TRUE; printf("%s",G.vexsw); EnQueue(&Q,w);/*主函数*/main() int w; MGraph G; CreateGraph(&G); PrintGraph(G); printf("nDfs:"); DfsTraverse(G); /* 深度遍历 */ printf("nBfs:"); BfsTraverse(G); /* 广度遍历 */二：基于邻接表的图的深度、广度遍历#include "stdlib.h"#include "stdio.h"#include "string.h"#define MAXVER 21#define N 100typedef char TElemType10;/*循环队列的操作*/*队列的类型定义*/typedef int ElemType;typedef structElemType *base;int front,rear;SqQueue;/*初始化队列*/void InitQueue(SqQueue *Q) Q->base=(ElemType *)malloc(N*sizeof(ElemType); Q->front=Q->rear=0; /*判断队列是否为空*/int QueueEmpty(SqQueue Q)if(Q.front=Q.rear) return 1; else return 0;/*入队列*/int EnQueue(SqQueue *Q,ElemType e)if(Q->rear+1)%N=Q->front) return 0;Q->baseQ->rear=e;Q->rear=(Q->rear+1)%N;return 1;/*出队列*/int DeQueue(SqQueue *Q,ElemType *e)if(Q->rear=Q->front) return 0;*e=Q->baseQ->front;Q->front=(Q->front+1)%N;return 1;/*图的操作*/*图的类型定义*/typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct TElemType data; ArcNode *firstarc;VNode,AdjListMAXVER;typedef struct AdjList vertices; int vexnum,arcnum; ALGraph;/*建立无向图的邻接矩阵*/void createALGraph(ALGraph *G) int i, s, d; ArcNode *p,*q; printf("nInput MG vexnum,arcnum:"); scanf("%d,%d",&(*G).vexnum,&(*G).arcnum); for(i=1;i<=G->vexnum;i+) printf("n输入第%d个顶点信息：",i); scanf("%s",G->verticesi.data); G->verticesi.firstarc=NULL; /输入第i个结点值并初始化第i个单链表为空 for(i=1; i<=G->arcnum; i+) printf("n输入第%d条边的始点和终点：",i); scanf("%d,%d",&s,&d); p=(ArcNode*)malloc(sizeof(ArcNode); p->adjvex=d; p->nextarc=G->verticess.firstarc; G->verticess.firstarc=p; /将新建的以d为信息的表结点p插入s单链表的头结点后 q=(ArcNode*)malloc(sizeof(ArcNode); q->adjvex=s; q->nextarc=G->verticesd.firstarc; G->verticesd.firstarc=q; /将新建的以s为信息的表结点q插入d单链表的头结点后/*深度遍历*/int visitedMAXVER;/定义全局数组遍历visitedvoid dfs(ALGraph G, int v)/被遍历的图G采用邻接表作为存储结构，v为出发顶点编号ArcNode *p;printf("%s",G.verticesv.data); visitedv=1; p=G.verticesv.firstarc; while(p!=NULL) if(visitedp->adjvex=0) dfs(G,p->adjvex); /若p所指表结点对应的邻接顶点未访问则递归地从该顶点出发调用dfs p=p->nextarc;void dfsTraverse(ALGraph G) int v; /遍历图之前初始化各未访问的顶点 for(v=1; v<=G.vexnum; v+) visitedv=0; /从各个未被访问过的顶点开始进行深度遍历 for(v=1;v<=G.vexnum;v+) if(visitedv=0) dfs(G,v);/*广度遍历*/void BFS(ALGraph G, int v)/从顶点编号v出发，广度遍历邻接表存储的图G SqQueue Q; ArcNode *p; InitQueue(&Q); printf("%s",G. verticesv.data); visitedv=1; EnQueue(&Q,v); while(!QueueEmpty(Q) v=DeQueue(&Q,&v); p=G.verticesv.firstarc; while(p!=NULL) if(visitedp->adjvex=0) v=p->adjvex; printf("%s",G.verticesv.data); visitedv=1; EnQueue(&Q,v); p=p->nextarc;void BFSTraverse(ALGraph G) int v; /遍历G以前，初始化visited数组为0 for(v=1;v<=G.vexnum;v+) visitedv=0; for(v=1;v<=G.vexnum;v+) if(visitedv=0) BFS(G,v);void main() ALGraph G; createALGraph(&G); printf("深度遍历结果为：n"); dfsTraverse(G); printf("n广度遍历结果为：n"); BFSTraverse(G); system("pause"); 八、测试情况程序的测试结果如下：1、基于邻接矩阵的图的深度、广度遍历结果正确2、基于邻接表的图的深度、广度遍历结果正确九、参考文献 1、严蔚敏，数据结构 C语言，清华大学出版社。 2、谭浩强，c语言程序设计，清华大学出版社。小结 图的遍历是有关于图的算法中最常见、最典型的算法。与树的遍历相类似，图的遍历是从图中任意一个顶点出发，访问遍图中所有的顶点，且使每个顶点仅被访问一次。图的遍历算法是求解图的连通性、拓扑排序、和求关键路径等算法的基础。由于图本身结构的复杂性，因而使得图的遍历要比树的遍历复杂得多。首先，图中所有顶点没有主次之分，因此也就没有一个 “自然”的起始点；其次，图中任意顶点均有可能与其它顶点相邻，在沿着某一路径依次搜索访问顶点时完全有可能又回到该顶点上；此外，图中某一顶点可能与多个顶点相邻，当访问过该结点后，如何选择下一个要访问的顶点，就成为一个决策问题。鉴于图的遍历的复杂性，遍历算法的设计就必须考虑图的结构特征。图的遍历算法通常有两条遍历路径：深度优先遍历和广度优先遍历。通过学习了图的深度遍历和广度遍历，我们对邻接表和邻接矩阵进行深度遍历和广度遍历。图的深度遍历类似于树的先根遍历，广度遍历类似于树的层次遍历。在实际中，由于在图中各个结点的度数各个不同，最大度数和最小度数可能相差很多，如果按度数最大的顶点设计结点结构，就会浪费很多存储单元，反之，若按每个顶点自己的度数设计不同的结点结构，又会给操作带来不便。在实际应用中不宜采用这种结构，而应该根据具体的图和需要进行的操作，设计恰当的结点结构和表结构，这时我们就用邻接表来处理，邻接表是图的一种链式存储结构。在邻接表中，对图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以vi为尾的弧）。图遍历的过程实质上是对每个顶点查找其邻接点的过程，是通过边或弧找邻接点的过程在邻接表中，对图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以vi为尾的弧）。邻接表中每一个表结点有两个域，其一为邻接点域adjvex，用以存放与顶点vi 相邻接的顶点vj的序号j，其二为指针域next，用来将邻接表的所有结点链在一起。如果要表示边上的权值，那么就要再增设一个数据域。另外，为每个顶点vi的邻接表设置一个具有两个域的表头结点：一个域是顶点信息域vertex，另一个则是指针域(指向邻接表)link，它是vi的邻接表的头指针。为了便于随机访问任一顶点的邻接表，需要把这n个表头指针用一个一维数组存储起来，其中第i个分量存储vi邻接表的表头指针邻接表中每一个表结点有两个域，其一为邻接点域adjvex，用以存放与顶点vi 相邻接的顶点vj的序号j，其二为指针域next，用来将邻接表的所有结点链在一起。如果要表示边上的权值，那么就要再增设一个数据域。另外，为每个顶点vi的邻接表设置一个具有两个域的表头结点：一个域是顶点信息域vertex，另一个则是指针域(指向邻接表)link，它是vi的邻接表的头指针。为了便于随机访问任一顶点的邻接表，需要把这n个表头指针用一个一维数组存储起来，其中第i个分量存储vi邻接表的表头指针。，一个图的邻接表不是唯一的，因为在每个顶点的邻接表中，各边结点的链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。，一个图的邻接表不是唯一的，因为在每个顶点的邻接表中，各边结点的链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。广度遍历图的时间复杂度和深度遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。这两种遍历既适用于无向图，也适用于有向图。但无论何种算法都是建立在邻接表存储结构之上所展开的。经过这次的程序设计让我们对邻接表和邻接矩阵有了更深度的了解，更对深度遍历和广度遍历的应用有了确切的明白，在以后的编程中也知道如何正确的运用。
