实验四-图的应用——深度优先／广度优先搜索遍历

数据结构 实验报告

实验四 图的应用

一、 实验题目：

图的应用——深度优先／广度优先搜索遍历 二、 实验内容：

很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。

要求：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。（注：学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接矩阵实现）

提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。

三、程序源代码：

#include #include

#define MAX_VERTEX_NUM 20 #define OVERFLOW -1 int visited[80]; typedef struct ArcNode{

int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧的指针

}ArcNode;

typedef struct VNode{

int data; //顶点信息

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

}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{

AdjList vertices;

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

}ALGraph;

第 1 页 共 7 页

typedef struct QNode{

int data;

struct QNode *next;

}QNode,*QueuePtr; typedef struct{

QueuePtr front;//队头指针 QueuePtr rear;//队尾指针

}LinkQueue;

void InitQueue(LinkQueue &q) { }

void EnQueue(LinkQueue &q,int e) { }

int DeQueue(LinkQueue &q) {

int e;

//若队列不空，则删除q的队头元素，用e返回其值，并返回OK;否则返回ERROR

第 2 页 共 7 页

//构造一个空队列q

q.front=q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!q.front) exit(OVERFLOW); q.front->next=NULL;

//插入元素e为q的新的队尾元素 QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW);//存储分配失败 p->data=e; p->next=NULL; q.rear->next=p; q.rear=p;

}

if(q.front==q.rear) return false; QueuePtr p; p=q.front->next; e=p->data;

q.front->next=p->next; if(q.rear==p) q.rear=q.front; free(p); return e;

bool QueueEmpty(LinkQueue &q)

{ //若队列q为空队列，则返回TRUE，否则返回FLASE }

int LocateVex(ALGraph G,int v) { }

//用邻接表构造无向图 void CreateDG(ALGraph &G) {

int i,j,k;

printf(\输入图的顶点数和弧度:\\n\scanf(\.arcnum);

第 3 页 共 7 页

if(q.front==q.rear) return true; else

return false;

int i;

for(i=0;i

if(G.vertices[i].data==v)

return i;

printf(\输入顶点信息:\\n\ for(i=0;i

}

printf(\输入邻接点:\\n\ for(k=0;k

scanf(\ i=LocateVex(G,v1); j=LocateVex(G,v2);

struct ArcNode *s;

s=(ArcNode *)malloc(sizeof(ArcNode)); s->adjvex=j;

s->nextarc=G.vertices[i].firstarc;

G.vertices[i].firstarc=s; struct ArcNode *t;

t=(ArcNode *)malloc(sizeof(ArcNode)); t->adjvex=i;

t->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=t;

}

}

void DFSAL(ALGraph G,int v0) {

visited[v0]=1;

第 4 页共 7 页

printf(\

struct ArcNode *p; }

//深度优先搜索遍历

void DFSTraverse(ALGraph G) { }

//广度优先搜索遍历

void BFSTraverse(ALGraph G,LinkQueue q) { int u,w;

struct ArcNode *p;

for(u=0;u

for(u=0;u

if(!visited[u]) {

printf(\.vertices[u].data);

第 5 页 共 7 页

int w;

for(p=G.vertices[v0].firstarc;p;p=p->nextarc) { }

w=p->adjvex; if(!visited[w])

DFSAL(G,w);

int v0;

for(v0=0;v0

if(!visited[v0])

DFSAL(G,v0); //对尚未访问的顶点调用DFSAL