《图的两种遍历.doc》由会员分享，可在线阅读，更多相关《图的两种遍历.doc（9页珍藏版）》请在三一文库上搜索。
1、 实验名称实验要求算法分析测试调节代码附录名称： 图的遍历要求：对给定图，实现图的深度优先遍历和广度优先遍历。基本要求以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。算法分析：/*图的深度优先遍历的基本思想就是:首相要创建图；创建一个无向的邻接表图（即链式）因此，就要对链表的结点进行定义（即图的邻接域和链域）建好之后就是进行深度优先遍历（采用的是递归的思想）在遍历的过程中定义一个数组，用于标记是否访问过。总之，大概的思路就是这些！*/#include#include#define Max_VertexNum 100typed
2、ef enumFALSE,TRUE Boolean;Boolean visitedMax_VertexNum;/访问标志向量/*邻接表结点*/typedef struct nodeint adjvex; /*邻接点域*/struct node *next;/*链域*/EdgeNode;/*顶点结点*/typedef struct vnodeint vertex; /顶点域EdgeNode *firstedge; /边头指针VertexNode;typedef VertexNode AdjlistMax_VertexNum;/定义一个邻接表的数组,用于存放顶点的信息/*图的定义*/typedef
3、 struct ALGraphAdjlist adjlist;int n,e;/图的顶点和边Graph;/*创建一个无向图*/void CreateGraph(Graph *G)int i,j,k;EdgeNode *s;printf(请输入图的顶点数和边数: );scanf(%d %d,&G-n,&G-e);/*对顶点数组进行初始化*/for(i=1;in;i+)printf(请输入顶点的信息: );printf(n);scanf(%d,&G-adjlisti.vertex);G-adjlisti.firstedge=NULL;for(k=0;ke;k+)printf(请输入边(vi,vj)
4、的顶点对序号: );printf(n);scanf(%d%d,&i,&j);s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=j;s-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s;s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=i;s-next=G-adjlistj.firstedge;G-adjlistj.firstedge=s;/*深度优先遍历*/void DFS(Graph *G,int i)EdgeNode *p;printf(您所访问的顶点为: %
5、d,G-adjlisti.vertex); /访问顶点printf(n);visitedi=TRUE; /标志已经访问过的p=G-adjlisti.firstedge;while(p)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-next; elsep=p-next;/对图进行深度优先遍历入口void DFSTravel(Graph *G)int i;for(i=1;in;i+)visitedi=FALSE;for(i=1;in;i+) if(!visitedi)DFS(G,i);void PrintAdjlist(Graph *G)int i;EdgeNod
6、e *p;for(i=1;in;i+)printf(%d:%d,i,G-adjlisti.vertex);for(p=G-adjlisti.firstedge;p;p=p-next)printf(%d,p-adjvex);printf(n);void main(void)Graph G;CreateGraph(&G);PrintAdjlist(&G);DFSTravel(&G);/*广度优先遍历*/#include#include#define Max_VertexNum 100typedef enumFALSE,TRUE Boolean;Boolean visitedMax_VertexNu
7、m;/访问标志向量/*队列的链式存储结构*/typedef struct qnodeint data;struct qnode *next;Qnode;typedef struct queueQnode *front; /头指针Qnode *rear; /尾指针Queue;/*表结点*/typedef struct nodeint adjvex;struct node *next;EdgeNode;/*顶点结点*/typedef struct vnodeint vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode AdjlistMax
8、_VertexNum;/定义一个邻接表的数组/*图的定义*/typedef struct ALGraphAdjlist adjlist;int n,e;/图的顶点和边Graph;/*创建一个无向图*/void CreateGraph(Graph *G)int i,j,k;EdgeNode *s;printf(请输入图的顶点数和边数: );scanf(%d %d,&G-n,&G-e);/*对顶点数组进行初始化*/for(i=1;in;i+)printf(请输入顶点的信息: );printf(n);scanf(%d,&G-adjlisti.vertex);G-adjlisti.firstedge=
9、NULL;for(k=0;ke;k+)printf(请输入边(vi,vj)的顶点对序号: );printf(n);scanf(%d%d,&i,&j);s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=j;s-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s;s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=i;s-next=G-adjlistj.firstedge;G-adjlistj.firstedge=s;/*初始化队列*/void InitQueue(Que
10、ue *q)q-front=q-rear=NULL;/*队列判空*/int EmpQueue(Queue *q)return(q-front=NULL&q-rear=NULL);/*出队列*/int DeQueue(Queue *q)Qnode *p;int data;if(EmpQueue(q)printf(队列为空!); /下溢exit(1);p=q-front; /保存q-front=q-front-next; /删除data=p-data; /取出队列元素/*如果原队列中只有一个结点，删除后，队列为空。此时头指针已经为空*/if(q-rear=p)q-rear=NULL;free(p)
11、;return data;/*顶点入队列*/void EnQueue(Queue *q,int a)Qnode *p;p=(Qnode*)malloc(sizeof(Qnode);p-data=a;p-next=NULL;if(EmpQueue(q)q-front=q-rear=p;elseq-rear-next=p;q-rear=p; /p此时变为队尾/*广度优先遍历*/void BFS(Graph *G,int k)int i;Queue Q; /定义一个队列EdgeNode *p;InitQueue(&Q); /初始化队列printf(您访问的顶点为: %d,G-adjlistk.ver
12、tex);visitedk=TRUE;EnQueue(&Q,k);while(!EmpQueue(&Q)i=DeQueue(&Q);p=G-adjlisti.firstedge;/依次搜索vi的邻接点vjwhile(p)if(!visitedp-adjvex)printf(您访问的顶点为: %d,G-adjlistp-adjvex.vertex);visitedp-adjvex=TRUE;EnQueue(&Q,p-adjvex);p=p-next;void BFSTravel(Graph *G)int i;for(i=1;in;i+)visitedi=FALSE;for(i=1;in;i+)if(!visitedi)BFS(G,i);/*输出构造的无向图*/void PrintAdjlist(Graph *G)int i;EdgeNode *p;for(i=1;in;i+)printf(%d:%d,i,G-adjlisti.vertex);for(p=G-adjlisti.firstedge;p;p=p-next)printf(%d,p-adjvex);printf(n);/void main()Graph G;CreateGraph(&G);PrintAdjlist(&G);BFSTravel(&G);