数据结构 实验报告
实验四 图的应用
一、 实验题目：
图的应用——深度优先／广度优先搜索遍历 二、 实验内容：
很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。
要求：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。（注：学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接矩阵实现）
提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。
三、程序源代码：
#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
实验四-图的应用——深度优先／广度优先搜索遍历
