数据结构课程设计报告--图遍历的演示

合肥学院

计算机科学与技术系

课程设计报告

XX 学年第 二 学期

课学学专指

业导

班教生

姓

程 数据结构与算法

图遍历的演示

名 号 级 师

课程设计名称

XXXX 年 6 月

图遍历的演示

一、问题分析和任务定义

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。将每个结点看做一个地名，如合肥。然后任选国内的城市，起点未合肥，忽略城市间的里程。

设图的结点20-30个，每个结点用一个编号表示(如果一个图有n个结点，则它们的编号分别为1，2，…，n)。通过输入图的全部边(存于数据文件中，从文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

二、数据结构的选择和概要设计

城市与城市之间的关系使没有方向的，无向图采用邻近多重表来实现，主要要表示无向图中的各个结点和边，在多重表中边是采用两个结点来表示的。

在邻接表中Edgenode表示邻接表中的结点类型，其中含有访问标记mark，一条边所依附的两个结点的序号ivex和jvex，以及分别指向依附于ivex和jvex的顶点边的链域ilink和jlink。

其中，邻接表中的表头结点用Vexnode表示，包含了顶点信息data和指向第一个边结点的firstedge。

用AMLGraph表示整个无向图，包含了图的顶点vexnum和边数edgenum。

结点坐标信息：

struct loc //结点坐标信息 {

int v; //结点序号 int x; //x坐标 int y; //y坐标 };

边结点数据结构：

struct Edgenode //边结点 {

int mark;//标志域，指示该边是否被访问过(0:没有1:有) int ivex,jvex;//该边关联的两个顶点的位置

Edgenode *ilink,*jlink;//分别指向关联这两个顶点的下一条边 };

顶点结点：

struct Vexnode //顶点结点 {

int data; //顶点名称,用数字表示城市

Edgenode *firstedge;//指向第一条关联该结点的边

};

AMLGraph类：

AMLGraph - *adjmulist：Vexnode - vexnum：int - edgenum：int - maxnum：int + AMLGraph(num1:int,num2:int) + ~AMLGraph() + Locate_Vex(v:int):int + AML_Init():void + Judge_Edge(v1:int,v2:int):bool + DFS_Traverse():void + DFS(v:int):void + BFS_Traverse():void + BFS(v:int):void + Mark_Unvisited():void + Display():void 图-1 AMLGraph类UML图

三、详细设计和编码

程序主体部分主要包括两大部分，一是遍历算法部分；另一部分是对演示图的处理。遍历算法部分主要包括了，邻接多重表构造的无向图的初始化、深度遍历和广度遍历；对演示图的处理包括了，结点坐标信息的初始化和绘图，运用了graphics.h库中的绘图函数。

1、深度遍历

函数名称： void DFS(int v)

函数功能：实现一张无向图从一个指定结点的深度搜索遍历，并输出结点序号函数参数： int v 开始的结点 具体代码：

void DFS(int v) //深度优先搜索遍历(递归)

{

Edgenode *p;

visited[v]=1; //标志v已被访问 cout<

p=adjmulist[v].firstedge;//取v边表的头指针，使P指向firstedge while(p!=NULL) //依次搜索v的邻接点 {

if(p->ivex==i) {

if(visited[p->jvex]==0) //邻近点未被访问过 {

dline(l[v].x,l[v].y,l[p->jvex].x,l[p->jvex].y); DFS(p->jvex); //递归调用 }

p=p->ilink; } else {

if(visited[p->ivex]==0) {

dline(l[v].x,l[v].y,l[p->ivex].x,l[p->ivex].y); DFS(p->ivex); //递归调用 }

p=p->jlink; } } }

2、广度遍历

函数名称：void BFS(int v) 函数功能：实现一张无向图从一个指定结点的广度度搜索遍历，并输出结点序号； 函数参数： int v开始的结点，返回参数为void 具体代码：

void BFS(int v)//广度优先搜索遍历 {

int i,vi;

int Queue[MAX_VERTEX_NUM],front=0,rear=0; //建立队列数组 Edgenode *p;

for(i=0;i

visited[v]=1; //开始结点标记为已访问 cout<

rear=(rear+1)%MAX_VERTEX_NUM; //取模初始化队列 Queue[rear]=v; //入队

while(front!=rear)//队头和队尾计数器不相等，即当队列非空 {

front=(front+1)%MAX_VERTEX_NUM; //出队 vi=Queue[front];//vi即表头数据元素值

p=adjmulist[vi].firstedge;//p指向表头节点所指的邻接点 while(p!=NULL)//当表头指针所指的邻接点不为空 {

if(p->ivex==vi) {

if(visited[p->jvex]==0)//边节点内元素未被访问则访问 节点内元素，并对其标记已访问 {

visited[p->jvex]=1; cout<jvex<<\

dline(l[vi].x,l[vi].y,l[p->jvex].x,l[p->jvex].y); //绘制路径

rear=(rear+1)%MAX_VERTEX_NUM;//队列的尾指针计数 器加一，即后移一位 Queue[rear]=p->jvex; }

p=p->ilink;//边节点内元素已被访问，指向下一邻接点

}

}

}

} else {

if(visited[p->ivex]==0) {

visited[p->ivex]=1; cout<ivex<<\

dline(l[vi].x,l[vi].y,l[p->ivex].x,l[p->ivex].y); //绘制路径

rear=(rear+1)%MAX_VERTEX_NUM; Queue[rear]=p->ivex; }

p=p->jlink; }

3、图的创建和初始化

函数名称：void AML_Init()

函数功能：创建一张固定结点和边数的无向图，边与结点的关系是从文件中读取 函数参数：形参为空，返回也为void 具体代码：

void AML_Init()

{

ifstream icin;

icin.open(\ int i,j,k;

int edge[30][2];//二维数组来存储边的关系,30条边和ivex，jvex边集 的两结点

for(i=0;i>edge[i][j];

for(i=0;i

adjmulist[i].data=i+1;

adjmulist[i].firstedge=NULL; }

for(k=0;k

Edgenode *e=new Edgenode; //申请边结点空间 e->ivex=edge[k][0];

e->jvex=edge[k][1];//读入2个顶点的值

e->ilink=adjmulist[e->ivex].firstedge;//将头结点的firstedge 指针赋给新结点的ilink

adjmulist[e->ivex].firstedge=e;//将头结点的指针指向新结点 e->jlink=adjmulist[e->jvex].firstedge;//将新结点的jlink指针 指向其jvex结点所依附的结点

adjmulist[e->jvex].firstedge=e; }

init_location(); //初始化所有结点的坐标信息 }

本文来源：https://www.bwwdw.com/article/45xx.html