文档库

最新最全的文档下载
当前位置:文档库 > 图遍历的演示

图遍历的演示

一、需求分析

1.以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以

用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生

成树的边集。

2.每个结点用一个编号表示(如果一个图有n个结点,则它们的编号分别

为1,2,…,n)。通过输入图的全部边输入一个图,每个边为一个数对,

可以对边的输入顺序作出某种限制。注意,生成树的边是有向边,端点

顺序不能颠倒。

3.(1) 建立无向图G的邻接表表示。按照用户输入顶点数,弧数. 各边(弧尾,

弧头)

(2) 输出图中边的表示。用(A,B)表示

(3) 实现无向图的深度优先搜索遍历。实现无向图的广度优先搜索遍历,

使用辅助队列q以存储已经被访问的路径长度为1,2,```的顶点,并且访问

标志数组visited,实现对图的遍历.

4.测试数据:输入图的顶点数和弧数:格式:顶点数,弧数;

输入图的顶点数和弧数:5,4

接着输入各边(弧尾,弧头):5,3

3,1

1,2

2,4

二、概要设计

1.抽象数据类型图的定义如下:

ADT{

数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。

数据关系R:

R={VR}

VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在路径}

基本操作P:

CreateGraph(&G,V,VR)

初始条件:V是图的顶点集,VR是图中边的集合。

操作结果:按V和VR的定义构造图G。

DestroyGraph(&G)

初始条件:图G存在。

操作结果:销毁图G。

LocateVex(G,u)

初始条件:图G存在,u和G中顶点有相同特征。

操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回

其他信息。

GetVex(G,v)

初始条件:图G存在,v是G中某个顶点。

操作结果:返回v的信息。

FirstEdge(G,v)

初始条件:图G存在,v是G中某个顶点。

操作结果:返回依附于v的第一条边,若该顶点在G中没有邻接点,

则返回“空”。

NextEdge(G,v,w)

初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点。

操作结果:返回依附于v的(相对于w的)下一条边。若不存在,则

返回“空”。

InsertVex(&G,v)

初始条件:图G存在,v和图中顶点有相同特征。

操作结果:在图G中增添新顶点v。

DeleteVex(&G,v)

初始条件:图G存在,v是G中某个顶点。

操作结果:删除G中顶点v及其相关的边。

2.主程序

void main( )

{

初始化;

用户输入信息:

接受用户输入的信息:

调用各个函数;

输出结果;

}

3.本程序共有五个模块

创建图的邻接表表示的模块→输出图中边的表示模块→深度优先搜索遍

历图的模块→广度优先搜索遍历图的模块→主程序模块

三、详细设计

#include

#include

#include

#include

#include

#define MAX_VERTEX_NUM 20 //图的最大顶点数

#define MAXQSIZE 30 //队列的最大容量

enum BOOL {False,True};

typedef struct ArcNode

{int adjvex; //该弧所指向的顶点的位置

struct ArcNode *nextarc; //指向下一条弧的指针

}ArcNode; //弧结点

typedef struct

{ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的弧的指针int vexnum,arcnum; //图的当前顶点和弧数

}Graph;

typedef struct //队列结构

{int elem[MAXQSIZE]; //数据域

int front; //队头指针

int rear; //队尾指针

}SqQueue;

BOOL visited[MAX_VERTEX_NUM]; //全局变量——访问标志数组

void CreateGraph(Graph &); //生成图的邻接表

void DFSTraverse(Graph); //深度优先搜索遍历图

void DFS(Graph,int);

void BFSTraverse(Graph); //广度优先搜索遍历图

void Initial(SqQueue &); //初始化一个队列

BOOL QueueEmpty(SqQueue); //判断队列是否空

BOOL EnQueue(SqQueue &,int); //将一个元素入队列

BOOL DeQueue(SqQueue &,int &); //将一个元素出队列

int FirstAdjVex(Graph,int); //求图中某一顶点的第一个邻接顶点

int NextAdjVex(Graph,int,int); //求某一顶点的下一个邻接顶点

void main()

{Graph G; //采用邻接表结构的图

char j='y';

//------------------编者信息----------------------------

printf("题目:编制一个“图遍历的演示”的程序.\n");

printf("班级:信息管理与信息系统01班.\n");

printf("姓名:徐丽\n");

printf("学号:201201050635\n");

printf("完成日期:2014.06.20\n");

//------------------------------------------------------

//------------------程序解说----------------------------

printf("\n本程序将演示生成一个图,并对它进行遍历.\n");

printf("输入图的顶点数和弧数:\n格式:顶点数,弧数;例如:5,4\n");

printf("接着输入各边(弧尾,弧头):\n例如:5,3\n 3,1\n 1,2\n 2,4\n");

printf("程序会生成一个图,并对它进行深度和广度遍历.\n");

printf("深度遍历:1->2->4->3->5\n广度遍历:1->2->3->4->5\n");

//------------------------------------------------------

while(j!='N'&&j!='n')

{

printf("\n请输入顶点数和弧数:");

scanf("%d,%d",&G.vexnum,&G.arcnum); //输入图的顶点数和弧数

CreateGraph(G); //生成邻接表结构的图

DFSTraverse(G); //深度优先搜索遍历图

BFSTraverse(G); //广度优先搜索遍历图

printf("图遍历完毕,继续进行吗?(Y/N)");

scanf(" %c",&j);

}

}

void CreateGraph(Graph &G)

{//构造邻接表结构的图G

int i;

int start,end;

ArcNode *s;

for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指针数组

for(i=1;i<=G.arcnum;i++)

{scanf("%d,%d",&start,&end); //输入弧的起点和终点

s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个弧结点

s->nextarc=G.AdjList[start]; //插入到邻接表中

s->adjvex=end;

G.AdjList[start]=s;

{s=(ArcNode *)malloc(sizeof(ArcNode));

s->nextarc=G.AdjList[end];

s->adjvex=start;

G.AdjList[end]=s;

}

}

}

void DFSTraverse(Graph G)

{//深度优先遍历图G

int i;

printf("深度优先遍历:");

for(i=1;i<=G.vexnum;i++) visited[i]=False; //访问标志数组初始化

for(i=1;i<=G.vexnum;i++)

if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS

printf("\b\b \n");

}

void DFS(Graph G,int i)

{//从第i个顶点出发递归地深度遍历图G

int w;

visited[i]=True; //访问第i个顶点

printf("%d->",i);

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

if(!visited[w]) DFS(G,w); //对尚未访问的邻接顶点w调用DFS

}

void BFSTraverse(Graph G)

{//按广度优先非递归的遍历图G,使用辅助队列Q和访问标志数组visited int i,u,w;

SqQueue Q;

printf("广度优先遍历:");

for(i=1;i<= G.vexnum;i++) visited[i]=False; //访问标志数组初始化

Initial(Q); //初始化队列

for(i=1;i<=G.vexnum;i++)

if(!visited[i])

{visited[i]=True; //访问顶点i

printf("%d->",i);

EnQueue(Q,i); //将序号i入队列

while(!QueueEmpty(Q)) //若队列不空,继续

{DeQueue(Q,u); //将队头元素出队列并置为u

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

if(!visited[w]) //对u的尚未访问的邻接顶点w进行访问并入队列{visited[w]=True;

printf("%d->",w);

EnQueue(Q,w);

}

}

}

printf("\b\b \n");

}

int FirstAdjVex(Graph G,int v)

{//在图G中寻找第v个顶点的第一个邻接顶点

if(!G.AdjList[v]) return 0;

else return(G.AdjList[v]->adjvex);

}

int NextAdjVex(Graph G,int v,int u)

{//在图G中寻找第v个顶点的相对于u的下一个邻接顶点

ArcNode *p;

p=G.AdjList[v];

while(p->adjvex!=u) p=p->nextarc; //在顶点v的弧链中找到顶点u if(p->nextarc==NULL) return 0; //若已是最后一个顶点,返回0 else return(p->nextarc->adjvex); //返回下一个邻接顶点的序号

}

void Initial(SqQueue &Q)

{//队列初始化

Q.front=Q.rear=0;

}

BOOL QueueEmpty(SqQueue Q)

{//判断队列是否已空,若空返回True,否则返回False

if(Q.front==Q.rear) return True;

else return False;

}

BOOL EnQueue(SqQueue &Q,int ch)

{//入队列,成功返回True,失败返回False

if((Q.rear+1)%MAXQSIZE==Q.front) return False;

Q.elem[Q.rear]=ch;

Q.rear=(Q.rear+1)%MAXQSIZE;

return True;

}

BOOL DeQueue(SqQueue &Q,int &ch)

{//出队列,成功返回True,并用ch返回该元素值,失败返回False

if(Q.front==Q.rear) return False;

ch=Q.elem[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

return True; //成功出队列,返回True

}

四、调试分析

2.当进行图中边的表示输出时, 目的要验证输入的边是否正确表示, 但

在程序中

是用指向顶点的指针表示, 结果只显示出各个顶点的顶点编号, 后来

调用邻接表

的数组的顶点数据表示, 正常输出.

3.进行有向图的广度优先搜索时, 开始只是简单定义一个数组和两个

头尾指针, 在进行

数组插入与删除时候只是移动一下头尾的指针,产生了错误, 后来改

用队列进行

操作, 虽然较复杂, 但还是得出了正确结果!

4.广度优先与深度优先搜索遍历图的时间复杂度相同.都是O(n+e), 两

者不同之处仅仅在于对顶点访问的顺序不同!

5.刚开始曾忽略了一些变量参数的标识“&”和语句结束时的“;”,

使调试程序时费时不少。今后要重视参数的变量和赋值属性的区分

和标识。

6.本程序没有明显的模块划分,所有的代码全都放在主函数之中,由

此导致主函数比较复杂混乱,又没有很多的注释,让人不大容易明

白,而且在调试的时候在对已经定义了的图的结构没有充分利用,

造成空间上的浪费。

五、用户手册

1.本程序的运行环境位DOS操作系统,执行文件为:图遍历的演示.cpp。

2.进入演示程序后所显示的用户界面:

图遍历的演示

3.接着按给出的例子的格式:

输入顶点数和弧数:

接着输入各边(弧尾,弧头):

程序会生成一个图,并对它进行深度和广度遍历。

六、测试结果

1.输入图的顶点数和弧数:(格式:顶点数,弧数)

请输入图的顶点数和弧数:5,4

接着输入各边(弧尾,弧头):5,3

3,1

1,2

2,4

2.便得结果:

深度遍历:1->2->4->3->5 >

广度遍历:1->2->3->4->5 >

图遍历完毕,继续进行吗?(Y\N)

图遍历的演示

3.输入Y则可以继续进行图的遍历,输入N则退出此系统。

七、附录

源程序文件清单:

图遍历的演示.exe //可执行文件。