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

华北水利水电学院 数据结构 实验报告

2012～2013学年 第 一 学期 2010级 计算机科学与技术 专业 班级： 201013432 学号： 201013432 姓名： 蔡启林

实验四 图的应用

一、 实验题目：

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

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

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

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

三、程序源代码： #include #define max 100 int visited[max]; typedef struct ArcNode {

int adjvex; struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode {

char data; ArcNode *firstarc;

}VNode,AdjList[max]; typedef struct {

AdjList vertices; int vexnum,arcnum;

第 1 页 共 8 页

}ALGraph;

typedef struct QNode { char data;

struct QNode *next;

}QNode,*QueuePtr; typedef struct

{ QueuePtr front;

QueuePtr rear;

}LinkQueue;

int InitQueue(LinkQueue &Q) { Q.front=Q.rear=new QNode; if(!Q.front)return 0; Q.front->next=NULL; return 1;

}

int QueueEmpty(LinkQueue &Q) { if(Q.front==Q.rear)

return 1;

else

return 0;

}

int EnQueue(LinkQueue &Q,char e) { QNode *p; p=new QNode;

if(!p)return 0;

第 2 页 共 8 页

}

p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return 1;

char DeQueue(LinkQueue &Q,int &e) { }

int LocateVex(ALGraph G,int v) {

int i; QNode *p;

if(Q.front==Q.rear)return 0; p=Q.front->next; e=p->data;

Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; delete(p); return 1;

for(i=0;v!=G.vertices[i].data&&i

void CreatGraph(ALGraph &G) {

int k,i,j;

if(i>=G.vexnum) return -1; return i;

ArcNode *p,*q;

cout<<\请输入顶点总数：\cin>>G.vexnum;

第 3 页 共 8 页

cout<<\请输入边数：\cin>> G.arcnum;

char v1,v2; }

int FirstAdjVex(ALGraph G,int v) { }

第 4 页 共 8 页

cout<<\输入顶点信息：\for(i=0;i

cout<<\请输入边的信息\for(k=0;k

cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); p=new ArcNode; q=new ArcNode; p->adjvex=j;

p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; q->adjvex=i;

q->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=q; cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL;

if(!G.vertices[v].firstarc) return 0; return G.vertices[v].firstarc->adjvex;

int NextAdjVex(ALGraph G,int v,int w) {

ArcNode *p;

p=G.vertices[v].firstarc;

while(p&&p->adjvex!=w) p=p->nextarc; if(!p->nextarc) return -1; else return p->nextarc->adjvex; }

void DFS(ALGraph G,int v) { int w; visited[v]=1;

cout<

void BFSTraverse(ALGraph G ) {

int v,w,u;LinkQueue Q; for(v=0;v

visited[v]=0;

for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))

if(!visited[w]) DFS(G,w);

InitQueue(Q);

for(v=0;v

if(!visited[v]) {

visited[v]=1;

cout<

第 5 页 共 8 页