文档库

最新最全的文档下载
当前位置:文档库 > 图的应用——深度优先遍历和广度优先遍历

图的应用——深度优先遍历和广度优先遍历

华北水利水电大学数据结构实验报告2013~2014学年第二学期2013级计算机科学与技术(专升本)专业班级:学号:姓名:

实验四图的应用

一、实验题目:

图的应用——深度优先/广度优先搜索遍历

二、实验内容:

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

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

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

三、程序源代码:

#include

#include

#include

#define MAX_VERTEX_NUM 20

typedef struct ArcCell {

int adj;

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {

char vexs[MAX_VERTEX_NUM];

AdjMatrix arcs;

int vexnum,arcnum;

}MGraph;

typedef struct Queue {

char* front;

char* rear;

}Queue;

bool visited[MAX_VERTEX_NUM]={false};

void InitQueue(Queue &Q) {//初始化队列

Q.front = Q.rear = (char *)malloc(MAX_VERTEX_NUM * sizeof(char));

if (!Q.front)

exit(0);

}

void EnQueue(Queue &Q,char v) {//入队列

*Q.rear = v;

Q.rear ++;

第 1 页共4 页

免费下载Word文档免费下载: 图的应用——深度优先遍历和广度优先遍历

(共4页)