图遍历的演示课程设计报告.doc

图遍历的演示课程设计报告.doc

《图遍历的演示课程设计报告.doc》由会员分享，可在线阅读，更多相关《图遍历的演示课程设计报告.doc（13页珍藏版）》请在冰点文库上搜索。

合肥学院

计算机科学与技术系

课程设计报告

2011～2012学年第二学期

课程

数据结构与算法

课程设计名称

图遍历的演示

学生姓名

汪青松

学号

1004031010

专业班级

网络工程1班

指导教师

吕刚、陈圣兵

2011年6月

图遍历的演示

一、问题分析和任务定义

很多涉及图上操作的算法都是以图的遍历操作为基础的。

试写一个程序，演示在连通的无向图上访问全部结点的操作。

将每个结点看做一个地名，如合肥。

然后任选国内的城市，起点未合肥，忽略城市间的里程。

设图的结点20-30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1，2，…，n）。

通过输入图的全部边（存于数据文件中，从文件读写）输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。

注意，生成树的边是有向边，端点顺序不能颠倒。

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

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

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

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

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

结点坐标信息：

structloc//结点坐标信息

{

intv;//结点序号

intx;//x坐标

inty;//y坐标

};

边结点数据结构：

structEdgenode //边结点

{

intmark;//标志域，指示该边是否被访问过（0:

没有1:

有）

intivex,jvex;//该边关联的两个顶点的位置

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

};

顶点结点：

structVexnode //顶点结点

{

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

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

图-1AMLGraph类UML图

三、详细设计和编码

程序主体部分主要包括两大部分，一是遍历算法部分；另一部分是对演示图的处理。

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

1、深度遍历

函数名称：

voidDFS（intv）

函数功能：

实现一张无向图从一个指定结点的深度搜索遍历，并输出结点序号函数参数：

intv开始的结点

具体代码：

voidDFS（intv） //深度优先搜索遍历（递归）

{

Edgenode*p;

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

cout<

inti=v;

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、广度遍历

函数名称：

voidBFS（intv）

函数功能：

实现一张无向图从一个指定结点的广度度搜索遍历，并输出结点序号；

函数参数：

intv开始的结点，返回参数为void

具体代码：

voidBFS（intv）//广度优先搜索遍历

{

inti,vi;

intQueue[MAX_VERTEX_NUM],front=0,rear=0;//建立队列数组

Edgenode*p;

for（i=0;i

visited[i]=0;

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

cout<

cout<<"\n";

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、图的创建和初始化

函数名称：

voidAML_Init（）

函数功能：

创建一张固定结点和边数的无向图，边与结点的关系是从文件中读取

函数参数：

形参为空，返回也为void

具体代码：

voidAML_Init（）

{

ifstreamicin;

icin.open（"d:

\wenjian2.txt"）;

inti,j,k;

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

for（i=0;i

for（j=0;j<2;j++）

icin>>edge[i][j];

for（i=0;i

{

adjmulist[i].data=i+1;

adjmulist[i].firstedge=NULL;

}

for（k=0;k

{

Edgenode*e=newEdgenode;//申请边结点空间

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（）;//初始化所有结点的坐标信息

}

4、初始化顶点坐标

函数名称：

voidinit_location（）

函数功能：

此函数为初始化顶点坐标，主要用来读取存储在文件中的各个顶点坐标信息

函数参数：

形参为空，返回值为空

具体代码：

voidinit_location（）//初始化结点的坐标信息

{

ifstreamicin;

l=newloc[20];

icin.open（"d:

\wenjian1.txt"）;

for（inti=1;i<=26;i++）

icin>>l[i].v>>l[i].x>>l[i].y;

}

四、上机调试过程

图-2具体的图关系图图-3存储顶点坐标信息文件

五、测试结果及其分析

图-4深度搜索遍历结果

图-5深度搜索遍历演示

图-6广度搜索遍历演示

图-7广度度搜索遍历演示

六、用户使用说明

本程序采用C++语言在Windows7+VC6.0环境下编写，主要功能是演示图的两种遍历过程；

程序所默认演示无向图包括26个结点和30条边，其中26个结点数字分别代表26个省会城市，30条边表示他们之间的关系，具体关系如演示图所示；

进入软件界面后，首先需要输入开始进行遍历的城市位置（即对应的结点数字），然后再进行选择进行图遍历的方式，本程序提供2种图遍历方式，深度优先遍历和广度优先遍历，选择遍历方式后，遍历结果将之间显示在屏幕上，左边数字为访问的结点，右边边集是访问时所经过的边。

在运行程序之前，请确保系统装有Easyx的graphicsk库。

七、参考文献

[1]王昆仑，李红.数据结构与算法.北京：

中国铁道出版社，2006年5月。

[2] 编程中国：

[3]Easyx：

八、附录

详细代码：

graph.h

#include

#include

#include

#include

//#include"image.h"

usingnamespacestd;

#defineMAX_VERTEX_NUM30//顶点最大个数

boolvisited[100];//顶点是否被访问标志

structloc//结点坐标信息

{

intv;//结点序号

intx;//x坐标

inty;//y坐标

};

//邻接多重表的存储

structEdgenode //边结点

{

intmark;//标志域，指示该边是否被访问过（0:

没有1:

有）

intivex,jvex;//该边关联的两个顶点的位置

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

};

structVexnode //顶点结点

{

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

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

};

classAMLGraph

{

private:

loc*l;//坐标信息指针

Vexnode*adjmulist;//顶点数组指针

intvexnum;//定点数目

intedgenum;//边数目

intmaxnum;//顶点数最大值

public:

//构造函数

AMLGraph（intnum1=26,intnum2=30）

{

adjmulist=newVexnode[num1];

vexnum=num1;edgenum=num2;

maxnum=MAX_VERTEX_NUM;

}

//析构函数

~AMLGraph（）

{

delete[]adjmulist;

}

//定位顶点在顶点数组中的位置

intLocate_Vex（intv）

{

for（inti=0;i

if（（adjmulist[i].data）==v）

returni;

return-1;

}

//构造无向图

voidAML_Init（）

{

ifstreamicin;

icin.open（"d:

\wenjian2.txt"）;

inti,j,k;

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

for（i=0;i

for（j=0;j<2;j++）

icin>>edge[i][j];

for（i=0;i

{

adjmulist[i].data=i+1;

adjmulist[i].firstedge=NULL;

}

for（k=0;k

{

Edgenode*e=newEdgenode;//申请边结点空间

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（）;//初始化所有结点的坐标信息

}

//深度优先遍历

voidDFS_Traverse（）

{

for（inti=0;i

visited[i]=false; //初始化所有顶点未被访问过

for（i=0;i

if（!

visited[i]） //如果未被访问过，进行访问DFS遍历

DFS（i）;

cout<

}

voidDFS（intv） //深度优先搜索遍历（递归）

{

Edgenode*p;

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

cout<

inti=v;

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;

}

}

}

//广度优先遍历

voidBFS_Traverse（）

{

for（inti=0;i

visited[i]=false;

for（i=0;i

if（!

visited[i]）

BFS（i）;

cout<

}

voidBFS（intv）//广度优先搜索遍历

{

inti,vi;

intQueue[MAX_VERTEX_NUM],front=0,rear=0;//建立队列数组

Edgenode*p;

for（i=0;i

visited[i]=0;

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

cout<

cout<<"\n";

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;

}

}

}

}

voiddline（intx1,inty1,intx2,inty2）//画线

{

setlinestyle（PS_DASH,NULL,3）;//设置线形为宽度3像素的虚线

line（x1,y1,x2,y2）;

}

voidinit_location（）//初始化结点的坐标信息

{

ifstreamicin;

l=newloc[20];

icin.open（"d:

\wenjian1.txt"）;

for（inti=1;i<=26;i++）

icin>>l[i].v>>l[i].x>>l[i].y;

}