图的遍历数据结构实验报告

1、山西大学计算机与信息技术学院实验报告姓 名学 号专业班级课程名称 数据结构实验日期2015/5/20成 绩指导教师批改日期实验名称 图遍历的演示一、实验目的： 1、问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。本次实验要求写一个程序，演示在连通的无向图上访问全部结点的操作； 2、基本要求：以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集； 3、测试数据：教科书图7.33（一个表示交通网的例图）。暂时忽略里程，起点为北京。 4、实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个

2、图有n个结点，则它们的编号分别为1,2，n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。二、实验内容:1、 概要设计（1）抽象数据类型图的定义如下：ADT Stack 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R： R=VRVR=(v,w)|v,wV,(v,w)表示v和w之间存在的路径基本操作P： CreateGraph（&G,V,VR） 初始条件：V是图的顶点集，VR是图中边的集合。 操作结果：按V和VR的定义构造图G。DestroyGraph(&G)初始条件：图G已存在

3、。操作结果：图G被销毁。 LocateVex（G,u）初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u,则返回该顶点在图中的位置；否则返回其他信息。 GetVex（G,v）初始条件：图G存在，v是G中某个顶点。操作结果：返回v的信息。 FirsrEdge（G,v）初始条件：图G存在，v是G中某个顶点。操作结果：返回依附于v的第一条边。若该顶点在G中没有邻接点，则返回“空”。 NextEdge（G，v，w）初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回依附于v的（相对于w的）下一条边。若不存在，则返回“空”。 InsertVex（&G,v）初

4、始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。DeleteVex（&G,v）初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的边。 InsertEdge（&G,v，w）初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添边（v,w）。DeleteEdge（&G,v，w）初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除边（v,w）。GetShortestPath（G，st，nd，&Path）初始条件：图G存在，st和nd是G中两个顶点。操作结果：若st和nd之间存在路径，则以Path返回两点

5、之间一条最短路径，否则返回其他信息。ADT Graph （2）本程序包含三个模块： 1）主程序模块 void main() 初始化； do 接受命令； 处理命令；while（“命令”！=“退出”）； 2）深度优先遍历void DFS(Graph *graph,int v) 3）广度优先遍历void BFS(Graph *graph,int u) 2、 详细设计#include "stdafx.h"#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAX 30typed

6、ef struct QNode int data; struct QNode *next;QNode;typedef struct QNode *rear; QNode *front;LinkQueue;void InitQueue(LinkQueue *Q) Q->front =Q->rear =(QNode *)malloc(sizeof(QNode); Q->front ->next =NULL;void EnQueue(LinkQueue *Q,int v) QNode *p; p=(QNode *)malloc(sizeof(QNode); p->dat

7、a =v; p->next =NULL; Q->rear ->next =p; Q->rear =p;void DeQueue(LinkQueue *Q,int *v) QNode *p; if(Q->front =Q->rear ) return; p=Q->front ->next ; *v=p->data ; Q->front ->next =p->next ; if(Q->rear =p) Q->rear =Q->front ; free(p);typedef struct EdgeNode in

8、t ivex,jvex; struct EdgeNode *ilink,*jlink;EdgeNode;typedef struct VexNode int markV; char info; int num; EdgeNode *firstedge;VexNode;typedef struct VexNode adjlistMAX; int vexnum,edgenum;Graph;void Initilized(Graph *graph) graph=(Graph *)malloc (sizeof(Graph); graph->vexnum =0; graph->edgenum

9、 =0;void CreateGraph(Graph *graph) EdgeNode *p,*q,*e; int i; printf("请输入连通无向图的顶点个数和边的条数：n"); scanf("%d %d",&graph->vexnum,&graph->edgenum); while(graph->vexnum>MAX|graph->edgenum >(graph->vexnum *(graph->vexnum -1)/2) printf("输入有误，请重新输入顶点数与边的条

10、数！n"); scanf("%d%d",&graph->vexnum ,&graph->edgenum ); for(i=1;i<=graph->vexnum;i+) printf("请输入第%d个顶点的信息：n",i); scanf("%s",&graph->adjlist ); graph->adjlist i.num =i; graph->adjlisti.firstedge=NULL; graph->adjlist i.markV

11、=0; for(i=1;i<=graph->edgenum;i+) p=(EdgeNode *)malloc(sizeof(EdgeNode); printf("请输入每条边依附的两个顶点(用顶点的编号表示)n"); scanf("%d %d",&p->ivex,&p->jvex); while(p->ivex =p->jvex|p->ivex<1|p->ivex >graph->vexnum |p->jvex <1|p->jvex >graph-&

12、gt;vexnum ) printf("输入的顶点有误，请重新输入!n"); scanf("%d%d",&p->ivex,&p->jvex); p->ilink =p->jlink =NULL; if(graph->adjlist p->ivex .firstedge=NULL ) graph->adjlist p->ivex .firstedge =p; else q=graph->adjlist p->ivex .firstedge ; while(q!=NULL) e=q;

13、 if(q->ivex =p->ivex ) q=q->ilink ; else q=q->jlink ; if(e->ivex =p->ivex ) e->ilink =p; else e->jlink =p; if(graph->adjlist p->jvex .firstedge=NULL ) graph->adjlist p->jvex .firstedge =p; else q=graph->adjlist p->jvex .firstedge ; while(q!=NULL) e=q; if(q-&

14、gt;ivex =p->ivex ) q=q->ilink ; else q=q->jlink ; if(e->ivex =p->ivex ) e->ilink =p; else e->jlink =p; void SetMark(Graph *graph) int i; for(i=1;i<=graph->vexnum ;i+) graph->adjlist i.markV =0;void DFS(Graph *graph,int v) EdgeNode *p; printf("%d ",v); graph-&g

15、t;adjlist v.markV =1; p=graph->adjlist v.firstedge ; while(p!=NULL) if(p->ivex =v) if(graph->adjlist p->jvex .markV =0) printf("<%d,%d>n",p->ivex ,p->jvex ); DFS(graph,p->jvex ); p=p->ilink ; else if(graph->adjlist p->ivex.markV =0) printf("<%d,%

16、d>n",p->jvex ,p->ivex ); DFS(graph,p->ivex ); p=p->jlink ; void BFS(Graph *graph,int u) LinkQueue Q; EdgeNode *p; InitQueue(&Q); printf("%d ",u); graph->adjlist u.markV =1; EnQueue(&Q,u); while(Q.front !=Q.rear ) DeQueue(&Q,&u); p=graph->adjlist u.

17、firstedge ; while( p!=NULL) if(p->ivex =u) if(graph->adjlist p->jvex .markV =0) EnQueue(&Q,p->jvex ); graph->adjlist p->jvex .markV =1; printf("<%d,%d>n",p->ivex ,p->jvex ); printf("%d ",p->jvex ); p=p->ilink ; else if(graph->adjlist p-&

18、gt;ivex .markV =0) EnQueue(&Q,p->ivex ); graph->adjlist p->ivex .markV =1; printf("<%d,%d>n",p->jvex ,p->ivex ); printf("%d ",p->ivex ); p=p->jlink ; void main() int u,v; Graph graph; char order; Initilized(&graph); CreateGraph(&graph); printf("输入命令（C/c：重新创建连通无向图T/t深度遍历广度遍历E/e：结束）：n"); scanf("%s",&order); while(order!='E'&&order!='e')