数据结构图的遍历实验报告

时间：2024.4.21

题目：图的遍历的实现

完成日期：20##.12.22

一、需求分析

1.本演示程序中，输入的数据类型均为整型数据，不允许输入字符等其他数据类型，且需要按照提示内容进行输入，成对的关系数据必须在所建立的图中已经存在对应的结点。

2.演示程序以用户和计算机的对话方式执行，在计算机终端上显示的提示信息的说明下，按照要求输入数据，运算结果在其后显示。

3.本程序实现分别基于邻接矩阵和邻接表存储结构的有、无向图，有、无向网的建立和遍历。遍历分DFS和BFS两种算法，并分别以递归和非递归形式实现。

4.测试数据：

（1）无向图结点数 4 弧数 3 结点：1 2 3 4 结点关系：1 2；1 3；2 4

（2）有向图结点数 6 弧数 6 结点：1 2 3 4 5 6 结点关系：1 2；1 3；2 4；3 5；3 6；2 5

二、概要设计

为实现上述程序功能，图的存储结构分为邻接矩阵和邻接表两种。遍历过程中借助了栈和队列的存储结构。

1.邻接矩阵存储结构的图定义：

ADT mgraph{

数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。

数据关系 R:

R=｛VR｝

VR={ | v,w ? V且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 }

基本操作 P：

locatevex(G, mes)；

初始条件：图G存在，mes和G中顶点有相同的特征。

操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。

createudn( & G)；

初始条件：图G 存在。

操作结果：创建无向图。

createdn( & G)；

初始条件：图G 存在。

操作结果：创建有向图。

createudg( & G)；

初始条件：图G 存在。

操作结果：创建无向网。

createdg(& G)；

初始条件：图G 存在。

操作结果：创建有向网。

DFS(G,v)；

初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。

操作结果：深度优先搜索遍历图G，访问顶点时使用函数visit.

BFS(G,v)；

初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。

操作结果：广度优先搜索遍历图G，访问顶点时使用函数visit.

visit( a)；

初始条件：a为图中的某个顶点值。

操作结果：访问顶点a，本程序中作用结果为输出顶点值。

｝ADT mgraph

2.邻接表存储结构的图定义：

ADT algraph{

数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。

数据关系 R:

R=｛VR｝

VR={ | v,w ? V且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 }

基本操作 P：

locatevex(G, mes)；

初始条件：图G存在，mes和G中顶点有相同的特征。

操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。

createudn( & G)；

初始条件：图G 存在。

操作结果：创建无向图。

createdn( & G)；

初始条件：图G 存在。

操作结果：创建有向图。

createudg( & G)；

初始条件：图G 存在。

操作结果：创建无向网。

createdg(& G)；

初始条件：图G 存在。

操作结果：创建有向网。

DFS(G,v)；

初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。

操作结果：深度优先搜索遍历图G，访问顶点时使用函数visit.

BFS(G,v)；

初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。

操作结果：广度优先搜索遍历图G，访问顶点时使用函数visit.

visit( a)；

初始条件：a为图中的某个顶点值。

操作结果：访问顶点a，本程序中作用结果为输出顶点值。

｝ADT algraph

3.主程序流程：

定义并创建图

status creatgraph(mgraph & G)

{

cout＜＜"请选择构造的图的类型：（ 1:有向图，2:有向网，3:无向图，4:无向网）"

＜

int kind;

scanf("%d",& kind);

switch (kind)//通过选择确定创建哪一种图；

{

case 1: return createdg(G);

case 2: return createdn(G);

case 3:return createudg(G);

case 4: return createudn(G);

default: return error;

}

然后采用DFS或BFS进行遍历（访问结果为输出顶点值）。

4.函数的调用关系图：

其中，当DFS使用递归算法时相关的栈操作不使用，当BFS使用递归算法时相关的队列操作仍有部分使用。

四、调试分析

1.采用邻接表结构创建图时，由于没有正确进行弧元素的跟进插入，导致图创建不成功。

2.没有采用多文件结构，导致在快要完成时发现函数定义的位置不尽合理，后续添加功能时难度增大。

3.本程序主要为实现遍历算法思想，对实用性考虑偏少，但考虑到了多种数据类型情况下的分别实现，函数拆分较详细，算法可靠性强。

4.算法的时空分析

1）由于对顶点元素的存储均采用了线性结构，所以在创建图和遍历时多依赖于该线性存储的大小。当结点个数为n,弧条数为e时， createdg createdn createudg createudn的算法时间复杂度都为O(n²+e*n),其中对邻接矩阵的初始化耗费了O(n²）的时间。

2）当用二维数组表示邻接矩阵作为图的存储结构时，查找每个顶点的邻接点所需时间为O(n²），而以邻接表为存储结构时为O(e）。以邻接表为存储结构时，深度优先搜索遍历图（DFS）的时间复杂度为O(n+e)。

3）广度优先搜索遍历图（BFS）的时间复杂度和深度优先搜索遍历（DFS）相同。

5.对链表的操作需要很重要的一个量来定位链表和定位操作的位置，指针的作用不可替代。多种数据结构的联合使用在程序中非常重要，多种存储结构的程序实现原理上相同，但具体的操作技巧有很大差别。

五、用户使用说明

1.本程序运行环境建议为window xp.

2.打开程序工程，并运行其中可执行文件，终端对话框会出现文字提示，请严格按照文字提示进行输入操作。

3.数据之间的分隔可用空格或回车键执行。

4.如下图是某无向图的创建并进行DFS的结果：

六、测试结果

DFS:

七、附录

邻接矩阵结构创建图：

#include

typedef int vertextype;

typedef int infotype;

typedef int status;

typedef int selemtype;

#define error 0

#define ok 1

#define INFINTY INT_MAX //最大值∞

#define MAX_VERTEX_NUM 20 //最大定点个数

#define FALSE 0

#define TRUE 1

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

#define overflow -2

using namespace std;

//弧定义

typedef struct arccell

{int adj;

// infotype *info;

}arccell,adjmatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

//图定义

typedef struct

{

vertextype vexs[MAX_VERTEX_NUM];//顶点

adjmatrix arcs;// 弧矩阵

int vexnum,arcnum;

}mgraph;

int locatevex(mgraph G,vertextype mes)

{

for(int i=0;i

if(mes==G.vexs[i])

return i;

return 0;

}//定位函数

//创建无向网

status createudn(mgraph & G)

{

cout＜＜"请输入无向网的顶点数，弧数："＜

scanf("%d%d",&G.vexnum,&G.arcnum);

cout＜＜"请输入各顶点的值："＜

for(int i=0;i

for(int j=0;j

G.arcs[i][j].adj=0;

cout＜＜"请输入成对的关系顶点数值以及其权值：（形如：11 22 1）"＜

for(int k=0;k

{vertextype v1,v2;

int w;

scanf("%d%d%d", &v1,&v2,&w);

int i=locatevex(G,v1);int j=locatevex(G,v2);

G.arcs[i][j].adj=w;

G.arcs[j][i]=G.arcs[i][j];

}

return ok;

}

//创建有向网

status createdn(mgraph & G)

{

cout＜＜"请输入有向网的顶点数，弧数："＜

scanf("%d%d",&G.vexnum,&G.arcnum);

cout＜＜"请输入各顶点的值："＜

for(int i=0;i

for(int j=0;j

G.arcs[i][j].adj=0;

cout＜＜"请输入成对的关系顶点数值以及其权值：（形如：11 22 1）"＜

for(int k=0;k

{

vertextype v1,v2;

int w;

scanf("%d%d%d", &v1,&v2,&w);

int i=locatevex(G,v1);int j=locatevex(G,v2);

G.arcs[i][j].adj=w;

}

return ok;

}

//创建无向图

status createudg(mgraph & G)

{

cout＜＜"请输入无向图的顶点数，弧数："＜

scanf("%d%d",&G.vexnum,&G.arcnum);

cout＜＜"请输入各顶点的值："＜

for(int i=0;i

for(int j=0;j

G.arcs[i][j].adj=0;

cout＜＜"请输入成对的关系顶点数值：（形如：11 22 ）"＜

for(int k=0;k

{

vertextype v1,v2;

scanf("%d%d", &v1,&v2);

int i=locatevex(G,v1);int j=locatevex(G,v2);

G.arcs[i][j].adj=1;

G.arcs[j][i]=G.arcs[i][j];

}

return ok;

}

//创建有向图

status createdg(mgraph & G)

{

cout＜＜"请输入有向图的顶点数，弧数："＜

scanf("%d%d",&G.vexnum,&G.arcnum);

cout＜＜"请输入各顶点的值："＜

for(int i=0;i

for(int j=0;j

G.arcs[i][j].adj=0;

cout＜＜"请输入成对的关系顶点数值：（形如：11 22 ）"＜

for(int k=0;k

{

vertextype v1,v2;

scanf("%d%d", &v1,&v2);

int i=locatevex(G,v1);int j=locatevex(G,v2);

G.arcs[i][j].adj=1;

}

return ok;

}

邻接矩阵的DFS非递归算法：

void visit(vertextype a)

{printf("--%d-",a);}

void DFS(mgraph G,int v)

{

int visitp[MAX_VERTEX_NUM];

sqstack S;

if(initstack(S)==1);

for(int i=0;i

visitp[i]=FALSE;

//首先访问第一个顶点

visit(G.vexs[v]);

visitp[v]=TRUE;

push(S, G.vexs[v]);

while (S.top!=S.base)//若栈不为空，则继续从栈顶元素进行遍历

{

int k=0,m=0,num=0,j=0 ,temp=0;

gettop(S,k);

m=locatevex(G,k);

//得到栈顶元素，并在图中定位

for(j=0;j

if((G.arcs[m][j].adj)!=0 && visitp[j]==FALSE)

num+=1;

if(num==0) //如果与栈顶元素相关联的顶点都被访问过，则删除栈顶元素

pop(S,temp);

//如果与栈顶元素相关联的顶点还有未被访问的，

//则将与其相关联的顶点全部访问

else

for(int w=0;w

if(G.arcs[m][w].adj !=0 && visitp[w]==FALSE)

{

visit(G.vexs[w]);//执行visit操作

visitp[w]=TRUE;//访问标志置真

push(S,G.vexs[w]);//刚访问的顶点入栈

break;

}

destroystack(S);

}

邻接矩阵的DFS递归算法：

int visitp[MAX_VERTEX_NUM];//全局变量，

//注意在main函数中都赋初值FALSE

void visit(vertextype a)

{printf("--%d-",a);}

void DFS(mgraph G,int v)

{

visit(G.vexs[v]);

visitp[v]=TRUE;

for(int j=0;j

if((G.arcs[v][j].adj)!=0 && visitp[j]==FALSE)

DFS(G,j);

}

邻接矩阵存储结构的BFS非递归算法：

void visit(vertextype a)

{printf("--%d-",a);}

void BFS(mgraph G,int v)

{

int visitp[MAX_VERTEX_NUM];

linkqueue Q;

if(initqueue(Q)==1)

for(int i=0;i

visitp[i]=FALSE;

else exit(1);

//首先访问第一个顶点

visit(G.vexs[v]);

visitp[v]=TRUE;

enqueue(Q,G.vexs[v]);

while (Q.front!=Q.rear)

{

int k=0,m=0,num=0,temp=0,j=0;

gethead(Q,k);

m=locatevex(G,k);//得到队首元素并定位

for(j=0;j

if((G.arcs[m][j].adj)!=0 && visitp[j]==FALSE)

num+=1;

if(num==0)

dequeue(Q,temp);//如果此顶点的后继均访问过，则从队列中删除

else

{

for(int w=0;w

if(G.arcs[m][w].adj !=0 && visitp[w]==FALSE)

{visit(G.vexs[w]);//执行visit操作

visitp[w]=TRUE;//访问标志置真

enqueue(Q,G.vexs[w]);}

}

destroyqueue(Q);

}

邻接矩阵存储结构的BFS递归算法：

void BFS(mgraph G,int v)

{

linkqueue Q;

initqueue(Q);

if(visitp[v]==FALSE)

{

visit(G.vexs[v]);

visitp[v]=TRUE;

}

int j;

int e;

int address;

for(j=0;j

if((G.arcs[v][j].adj)!=0 && visitp[j]==FALSE)

{

visit(G.vexs[j]);

visitp[j]=TRUE;

enqueue(Q,G.vexs[j]);

}

while (Q.front!=Q.rear)

{

dequeue(Q,e);

address=locatevex(G,e);

BFS(G,address);

}

destroyqueue(Q);

}

int main()

{

mgraph G;

creatgraph(G);

int i;

for(i=0;i

visitp[i]=FALSE;

BFS(G,0);

return 0;

}

邻接表存储结构的图的创建：

#include

typedef int vertextype;

typedef int infotype;

typedef int status;

typedef int selemtype;

#define FALSE 0

#define TRUE 1

#define error 0

#define ok 1

#define MAX_VERTEX_NUM 20 //最大顶点个数

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

#define overflow -2

using namespace std;

typedef struct arcnode{

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

int adj;//权值

struct arcnode *nextrarc; //指向下一条弧的指针

infotype *info;

}arcnode;

//顶点结点定义

typedef struct vnode{

vertextype data; //顶点数据

arcnode *firsttarc;//指向第一条依附该顶点的弧的指针

}vnode,adjlist[MAX_VERTEX_NUM];

//图定义

typedef struct{

adjlist vertices;//顶点数组

int vexnum,arcnum;//顶点数目，弧数目

int kind; //图的种类标志，以数字代表

}algraph;

int locatevex(algraph G,vertextype mes){

for(int i=0;i

if(mes==G.vertices[i].data)

return i;

return -1;

}

//创建无向网

status createudn(algraph &G){

cout＜＜"请输入无向网的顶点数，弧数："＜

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

cout＜＜"请输入各顶点的值："＜

for(int i=0;i

scanf("%d",&G.vertices[i].data); //输入并构造顶点

for(int i=0;i

G.vertices[i].firsttarc=NULL;//初始化指针firsttarc

cout＜＜"请输入成对的关系顶点数值以及其权值：（形如：11 22 1）"＜

for(int k=0;k

{ vertextype v1,v2;

int w;//权值

scanf("%d%d%d", &v1,&v2,&w); getchar();

int i=locatevex(G,v1);

int j=locatevex(G,v2);//定位

arcnode * a;

a=(arcnode *)malloc(sizeof (arcnode));//为加入的弧结点申请空间

if (a==NULL)

exit(1);

( * a).adjvex=j;(* a).adj=w;(* a).nextrarc=NULL;(* a).info=NULL;

if(G.vertices[i].firsttarc==NULL)

G.vertices[i].firsttarc=a;//当此弧是顶点i的第一条弧时

else//当此弧不是顶点i的第一条弧时

{a-＞nextrarc=G.vertices[i].firsttarc-＞nextrarc;

G.vertices[i].firsttarc=a;}

//处理另一条对称的顶点j

if(G.vertices[j].firsttarc==NULL)

G.vertices[j].firsttarc=a;//当此弧是顶点j的第一条弧时

else//当此弧不是顶点j的第一条弧时

{a-＞nextrarc=G.vertices[j].firsttarc-＞nextrarc;

G.vertices[j].firsttarc=a;}

}

return ok;

}

//有向网

status createdn(algraph &G)

{

cout＜＜"请输入有向网的顶点数，弧数："＜

scanf("%d%d",&G.vexnum,&G.arcnum);

cout＜＜"请输入各顶点的值："＜

for(int i=0;i

scanf("%d",&G.vertices[i].data); //构造顶点

for(int i=0;i

G.vertices[i].firsttarc=NULL;//初始化指针firsttarc

cout＜＜"请输入成对的关系顶点数值以及其权值：（形如：11 22 1）"＜

for(int k=0;k

{ vertextype v1,v2;

int w;

scanf("%d%d%d", &v1,&v2,&w);getchar();

int i=locatevex(G,v1);

int j=locatevex(G,v2);

arcnode * a;

a=(arcnode *)malloc(sizeof (arcnode));

if (a==NULL)

exit(1);

( * a).adjvex=j;(* a).adj=w;(* a).nextrarc=NULL; (* a).info=NULL;

if(G.vertices[i].firsttarc==NULL)

G.vertices[i].firsttarc=a;//当此弧是顶点i的第一条弧时

else//当此弧不是顶点i的第一条弧时连接到第一条弧位置，将原来的弧接到后面

{a-＞nextrarc=G.vertices[i].firsttarc-＞nextrarc;

G.vertices[i].firsttarc=a;}

}

return ok;

}

//无向图

status createudg(algraph &G)

{

cout＜＜"请输入无向图的顶点数，弧数："＜

scanf("%d %d",&G.vexnum,&G.arcnum);getchar();

cout＜＜"请输入各顶点的值："＜

for(int i=0;i

{scanf("%d",&G.vertices[i].data);}//顶点赋值

getchar();

for(int i=0;i

G.vertices[i].firsttarc=NULL;//初始化指针firsttarc

cout＜＜"请输入成对的关系顶点数值：（形如：11 22 ）"＜

for(int k=0;k

{ vertextype v1,v2;

scanf("%d%d", &v1,&v2);getchar();

int i=locatevex(G,v1);

int j=locatevex(G,v2);

arcnode * a;

a=(arcnode *)malloc(sizeof (arcnode));//为加入的弧结点申请空间

if (a==NULL)

exit(1);

( * a).adjvex=j;(* a).adj=1; (* a).nextrarc=NULL; (* a).info=NULL;

if(G.vertices[i].firsttarc==NULL)//当此弧是顶点i的第一条弧时{

G.vertices[i].firsttarc=a;//cout＜＜"attach to firsttarc"＜

else//当此弧不是顶点i的第一条弧时

{a-＞nextrarc=G.vertices[i].firsttarc;

G.vertices[i].firsttarc=a; //cout＜＜"attach successfully!"＜

}

//处理对称的另一个顶点

if(G.vertices[j].firsttarc==NULL)//当此弧是顶点j的第一条弧时{

G.vertices[j].firsttarc=a;//cout＜＜"attach to firsttarc"＜

else//当此弧不是顶点j的第一条弧时

{a-＞nextrarc=G.vertices[j].firsttarc;

G.vertices[j].firsttarc=a; //cout＜＜"attach successfully!"＜

}

}return ok;

}

status createdg(algraph &G)

{

cout＜＜"请输入无向图的顶点数，弧数："＜

scanf("%d %d",&G.vexnum,&G.arcnum);getchar();

cout＜＜"请输入各顶点的值："＜

for(int i=0;i

{scanf("%d",&G.vertices[i].data);}//顶点赋值

getchar();

for(int i=0;i

G.vertices[i].firsttarc=NULL;//初始化指针firsttarc

cout＜＜"请输入成对的关系顶点数值：（形如：11 22 ）"＜

for(int k=0;k

{ vertextype v1,v2;

scanf("%d%d", &v1,&v2);getchar();

int i=locatevex(G,v1);

int j=locatevex(G,v2);

arcnode * a;

a=(arcnode *)malloc(sizeof (arcnode));//为加入的弧结点申请空间

if (a==NULL)

exit(1);

( * a).adjvex=j;(* a).adj=1; (* a).nextrarc=NULL; (* a).info=NULL;

if(G.vertices[i].firsttarc==NULL)//当此弧是顶点i的第一条弧时{

G.vertices[i].firsttarc=a;//cout＜＜"attach to firsttarc"＜

else//当此弧不是顶点i的第一条弧时

{a-＞nextrarc=G.vertices[i].firsttarc;

G.vertices[i].firsttarc=a; //cout＜＜"attach successfully!"＜

}

}return ok;

}

邻接表存储结构的额DFS非递归算法：

//visit函数

void visit(vertextype a)

{printf("--%d-",a);}

//DFS

void DFS(algraph G,int v){

int visitp[MAX_VERTEX_NUM];//访问标记数组，

sqstack S;

initstack(S);//建立存储访问过结点的栈

for(int i=0;i

visitp[i]=FALSE;//将各顶点访问标记均赋值为FALSE

visit(G.vertices[v].data);

visitp[v]=TRUE;

push(S,G.vertices[v].data);//访问并入栈第一个顶点

while(S.base!=S.top)//当栈不为空时进行遍历

{

arcnode * p;

int num=0,temp=0,k=0,m=0;

gettop(S,k);//得到栈顶元素

m=locatevex(G,k);//定位栈顶元素在图中的坐标

for(p=G.vertices[m].firsttarc;p!=NULL;p=p-＞nextrarc)

{if(visitp[(* p).adjvex]==FALSE) num+=1;}

//cout＜＜"there are"＜

if(num==0)//如果此顶点的后继顶点都被访问过，则从栈中删除此顶点

{ pop(S,temp);cout＜＜"no point left"＜

else

{for(p=G.vertices[m].firsttarc;p!=NULL;p=p-＞nextrarc)

if(visitp[(* p).adjvex]==FALSE)

{ visit( G.vertices[(* p).adjvex].data);

visitp[(* p).adjvex]=TRUE;

push(S,G.vertices[(* p).adjvex].data);

break;//因为是深度优先，所以遇到可访问顶点并访问后跳出for循环

}

}destroystack(S);//销毁辅助栈

}

邻接表存储结构的DFS递归算法：

int visitp[MAX_VERTEX_NUM];//全局变量，

//注意在main函数中都赋初值FALSE

void visit(vertextype a)

{printf("--%d-",a);}

void DFS(algraph G,int v)

{

visit(G.vertices[v].data);

visitp[v]=TRUE;

for( arcnode * p=G.vertices[v].firsttarc;p!=NULL;p=p-＞nextrarc)

if(visitp[p-＞adjvex]==FALSE)DFS(G,p-＞adjvex);

}

int main()

{algraph G;

createudg(G);

for(int i=0;i

visitp[i]=FALSE;

DFS(G,0);

return 0;

}

邻接表存储结构的BFS非递归算法：

void visit(vertextype a)

{printf("--%d-",a);}

void BFS(algraph G,int v)

{

int visitp[MAX_VERTEX_NUM];

linkqueue Q;

if(initqueue(Q)==1)

for(int i=0;i

visitp[i]=FALSE;

else exit(1);

//首先访问第一个顶点

visit(G.vertices[v].data);

visitp[v]=TRUE;

enqueue(Q,G.vertices[v].data);

while (Q.front!=Q.rear)

{

int k=0,m=0,num=0,temp=0;

gethead(Q,k);

m=locatevex(G,k);//得到队首元素并定位

for(arcnode * j=G.vertices[m].firsttarc;j!=NULL;j=j-＞nextrarc)

if(visitp[(* j).adjvex]==FALSE)

num+=1;

if(num==0)

dequeue(Q,temp);//如果此顶点的后继均访问过，则从队列中删除

else

{

for(arcnode * p=G.vertices[m].firsttarc;p!=NULL;p=p-＞nextrarc)

if(visitp[(* p).adjvex]==FALSE)

{visit( G.vertices[(* p).adjvex].data);//执行visit操作

visitp[(* p).adjvex]=TRUE;//访问标志置真

enqueue(Q,G.vertices[(* p).adjvex].data);

}

destroyqueue(Q);

}

int main()

{

algraph G;

createudg(G);

BFS(G,0);

return 0;

}

//邻接表存储结构的BFS递归算法

void visit(vertextype a)

{printf("--%d-",a);}

int visitp[MAX_VERTEX_NUM];

void BFS(algraph G,int v)

{ linkqueue Q;

initqueue(Q);

if(visitp[v]==FALSE)

{

visit(G.vertices[v].data);

visitp[v]=TRUE;

}//访问标记，

int e;

int address;

arcnode * p;

for(p=G.vertices[v].firsttarc;p!=NULL;p=p-＞nextrarc)

if(visitp[(* p).adjvex]==FALSE)

{

visit( G.vertices[(* p).adjvex].data);

visitp[(* p).adjvex]=TRUE;

enqueue(Q,G.vertices[(* p).adjvex].data);

}//访问该与结点有关系的全部结点

while (Q.front!=Q.rear)

{

dequeue(Q,e);

address=locatevex(G,e);

BFS(G,address);//递归调用BFS

}

destroyqueue(Q);

}

int main()

{

algraph G;

createudg(G);

int i;

for(i=0;i

visitp[i]=FALSE;

BFS(G,0);

return 0;

}

辅助队列的实现：

#include

typedef int vertextype;

typedef int infotype;

typedef int status;

typedef int qelemtype;

#define error 0

#define ok 1

#define INFINTY INT_MAX //最大值∞

#define MAX_VERTEX_NUM 20 //最大定点个数

#define overflow -2

#define FALSE 0

#define TRUE 1

using namespace std;

typedef struct qnode{

qelemtype data;

struct qnode *next;

}qnode,* queueptr;

typedef struct {

queueptr front;//队头指针

queueptr rear;//队尾指针

}linkqueue;

status initqueue(linkqueue &Q);

status gethead(linkqueue Q,qelemtype &e);

status enqueue(linkqueue &Q,qelemtype e);

status dequeue(linkqueue &Q,qelemtype &e);

status destroyqueue(linkqueue &Q);

status initqueue(linkqueue &Q)

{

Q.front=Q.rear=(queueptr)malloc(sizeof(qnode));

if(!Q.front)exit(overflow);

Q.front-＞next=NULL;

return ok;

}

status gethead(linkqueue Q,qelemtype &e)

{

if(Q.front==Q.rear)

return error;

e=Q.front-＞next-＞data;

return ok;

}

status enqueue(linkqueue &Q,qelemtype e)

{

queueptr p;

p=(queueptr)malloc(sizeof (qnode));

if(!p) exit(overflow);

p-＞data=e;p-＞next=NULL;

Q.rear-＞next=p;

Q.rear=p;

return ok;

}

status dequeue(linkqueue & Q,qelemtype &e)

{

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

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 ok;

}

status destroyqueue(linkqueue &Q)

{

while(Q.front)

{ Q.rear=Q.front-＞next;

free(Q.front);

Q.front=Q.rear;

}

return ok;

}

辅助栈的实现：

#include

typedef int vertextype;

typedef int infotype;

typedef int status;

typedef int selemtype;

#define FALSE 0

#define TRUE 1

#define error 0

#define ok 1

#define MAX_VERTEX_NUM 20 //最大定点个数

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

#define overflow -2

using namespace std;

typedef struct {

selemtype *base;

selemtype *top;

int stacksize;

}sqstack;//栈结构

status initstack(sqstack &S);//构造一个空栈S;

status gettop(sqstack S,selemtype &e);//得到栈顶元素；

status push(sqstack &S,selemtype e);//将元素压入栈；

status pop(sqstack &S,selemtype &e);//删除栈顶元素；

status destroystack(sqstack &S);//销毁栈

status initstack(sqstack &S){

S.base= (selemtype *)malloc(STACK_INIT_SIZE*sizeof (selemtype));

if(!S.base) exit(overflow);

S.top =S.base;

S.stacksize = STACK_INIT_SIZE;

return ok;

}//initstack

status gettop(sqstack S,selemtype &e){

if(S.top == S.base) return error;

e= *(S.top-1);

//cout＜＜"得到栈顶元素："＜

return ok;

}//gettop

status push(sqstack &S,selemtype e){

if(S.top -S.base＞=S.stacksize)

{S.base =(selemtype *)realloc(S.base,(S.stacksize+ STACKINCREMENT)*sizeof(selemtype));

if(!S.base)exit(overflow);

S.top = S.base + S.stacksize;

S.stacksize += STACKINCREMENT;

}

*S.top ++ =e;

//cout＜＜"Push "＜

return ok;

}//push

status pop(sqstack &S,selemtype &e){

if(S.top ==S.base)return error;

e=*--S.top;

// cout＜＜"Pop"＜

return ok;

}//pop

status destroystack(sqstack &S){

S.top=S.base;free(S.base);return ok;

}

更多相关推荐：

图的遍历实验报告: 数据结构实验报告计科101冯康20xx00814128实验五图的基本操作一实验目的1使学生可以巩固所学的有关图的基本知识2熟练掌握图的存储结构3熟练掌握图的两种遍历算法二实验内容问题描述对给定图实现图的深度优先...
数据结构实验报告-图的遍历: 数据结构验报告实验图的遍历一实验目的1理解并掌握图的逻辑结构和物理结构邻接矩阵邻接表2掌握图的构造方法3掌握图的邻接矩阵邻接表存储方式下基本操作的实现算法4掌握图的深度优先遍历和广度优先原理二实验内容1输入顶点...
图的遍历实验报告(数据结构): 电子信息工程学系实验报告适用于计算机课程课程名称数据结构实验项目名称图的遍历操作实验时间班级计应102姓名学号实验目的掌握有向图和无向图的概念掌握邻接矩阵和邻接链表建立图的存储结构掌握DFS及BFS对图的遍历操...
数据结构课程实验(图的存储与遍历): 实验五图的存储与遍历1实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示以及在此两种常用存储方式下深度优先遍历dfs和广度优先遍历BFS操作的实现2实验预备知识1图的存储结构邻接矩阵表示法和邻接表表...
C++图的创建与遍历实验报告: 实验五图的遍历及其应用实现一实验目的1熟悉图常用的存储结构2掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现3会用图的遍历解决简单的实际问题二需求分析很多问题都是建立在图的遍历的基础上实现的所以必须...
实现图的遍历算法实验报告: 实现图的遍历算法1需求分析对于下图G编写一个程序输出从顶点0开始的深度优先遍历序列非递归算法和广度优先遍历序列非递归算法2系统设计1用到的抽象数据类型的定义图的抽象数据类型定义ADTGraph数据对象VV是具有...
C++图的创建与遍历实验报告: 数据结构集中上机试验报告学院计算机科学与技术专业计算机科学与技术学号00000000班级6姓名题目图的创建与遍历一需求分析很多问题都是建立在图的遍历的基础上实现的所以必须有一个程序能够实现将图进行广度和深度遍历...

图的遍历操作实验报告: 图的遍历操作实验报告实验三图的遍历操作一目的掌握有向图和无向图的概念掌握邻接矩阵和邻接链表建立图的存储结构掌握DFS及BFS对图的遍历操作了解图结构在人工智能工程等领域的广泛应用二要求采用邻接矩阵和邻接链表作为...
图的遍历实验报告: 课程实验报告课程名称实验项目名称专业班级姓名学号完成时间月实验5图的遍历问题一背景网络蜘蛛即WebSpider是一个很形象的名字把互联网比喻成一个蜘蛛网那么Spider就是在网上爬来爬去的蜘蛛网络蜘蛛是通过网页...
图的遍历实验报告: 实验四图的遍历题目图及其应用图的遍历班级姓名学号完成日期一需求分析1问题描述很多涉及图上操作的算法都是以图的遍历操作为基础的试写一个程序演示在连通的无向图上访问全部结点的操作2基本要求以邻接表为存储结构实现连通...
数据结构图的遍历实验报告: 辽宁工程技术大学上机实验报告
数据结构图的遍历实验报告: 实验项目名称图的遍历一实验目的应用所学的知识分析问题解决问题学会用建立图并对其进行遍历提高实际编程能力及程序调试能力二实验内容问题描述建立有向图并用深度优先搜索和广度优先搜素输入图中节点的个数和边的个数能够打印...

热门关注