实验 五 图的遍历及其应用实现

实验 五 图的遍历及其应用实现

一、实验目的

1．熟悉图常用的存储结构。

2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。 3．会用图的遍历解决简单的实际问题。

二、实验内容

从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数

1 2 5 3 4 相关常量及结构定义：

typedef int InfoType; typedef int QElemType; typedef char VertexType; #define MAX_VERTEX_NUM 20 #define MAXQSIZE 100 typedef struct ArcNode {

int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧的指针 InfoType *info; //该弧相关信息的指针 }ArcNode;

typedef struct VNode {

VertexType data; //顶点信息

struct ArcNode *firstarc; //指向第一条依附该顶点的弧的指

针

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct { AdjList vertices;

int vexnum, arcnum; //图的当前顶点和弧数

int kind; //图的种类标志 }ALGraph;

typedef struct Queue {

QElemType *base; int front; int rear; }Queue;

设计相关函数声明：

int LocateVex(ALGraph &G, char &v)

图的邻接表创建：void CreateGraph(ALGraph &G)

深度优先搜索：void DFS(ALGraph &G,int v,int *visited)

void DFSTraverse(ALGraph &G)

广度优先搜索：void BFSTraverse(ALGraph &G) 队列：int InitQueue(Queue &Q)

int EnQueue(Queue &Q,QElemType e) int DeQueue(Queue &Q,QElemType &e) int QueueEmpty(Queue &Q)

三、数据结构与核心算法的设计描述

1.定位

int LocateVex(ALGraph &G, char &v) {

int m;

for(m=0; m

if(G.vertices[m].data==v) return m; }

2.图的创建

void CreateGraph(ALGraph &G) {

int i=0,j=0,k;

cout<<\请输入顶点的数目边得数目 \ cin>>G.vexnum>>G.arcnum;

cout<<\请依次输入各顶点的值：\ for(i=0;i

cin>>G.vertices[i].data;

G.vertices[i].firstarc=NULL; }

char sv,tv;

cout<<\请依次输入各边的始点和终点：\ for (k=0; k

cout<<\请输入第\条边的始点：\ cin>>sv;

cout<<\请输入第\条边的终点：\ cin>>tv;

i=LocateVex(G, sv);

cout<<\请输入第\条边的始点的位置：\ j=LocateVex(G, tv);

cout<<\请输入第\条边的终点的位置：\ ArcNode *p;

p=(ArcNode *)malloc(sizeof(ArcNode)); if(!p) {

cout<<\ }

p->adjvex=j;

p->nextarc=G.vertices[i].firstarc; p->info=NULL;

G.vertices[i].firstarc=p;

if(G.vertices[i].firstarc==NULL) cout<<\ } }

2.深度优先搜索

void DFS(ALGraph &G,int v,int *visited) {

int w; char z;

visited[v]=1;

cout<

for(z=G.vertices[v].data;G.vertices[v].firstarc!=NULL; w=G.vertices[v].firstarc->adjvex,

G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc) if(visited[v]==0)

DFS(G,w,visited); }

void DFSTraverse(ALGraph &G) {

int v;

int visited[MAX_VERTEX_NUM]; for (v=0; v

for (v=0; v

DFS(G,v,visited); }

3.初始化队列

int InitQueue(Queue &Q) {

Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base) {

cout<

Q.front=Q.rear=0; return 1; }

4.入队