用邻接表遍历图实验报告.docx

用邻接表遍历图实验报告.docx

《用邻接表遍历图实验报告.docx》由会员分享，可在线阅读，更多相关《用邻接表遍历图实验报告.docx（11页珍藏版）》请在冰点文库上搜索。

用邻接表遍历图实验报告

《数据结构（C++版）》

实验报告

班级1405

学号*********

姓名徐妍

题目用邻接表遍历图

指导教师王江涛

计算机科学与技术学院

2015

年

12

月

12

日

实验题目：

用邻接表遍历图

一、实验目的：

1.掌握图的逻辑结构

2.掌握图的邻接表存储结构

3.验证图的邻接表存储及其深度和广度优先遍历操作的实现

二、实验内容：

1.建立一个有向图的邻接表存储结构

2.对建立的有向图，进行深度优先遍历

3.对建立的有向图，进行广度优先遍历

三、设计与编码

1.本实验用到的理论知识

1　边表结点与顶点表结点的建立（类似单链表中的结点）；

2　队列的特点：

只能在一端插入，另一端删除；

2.算法设计

关键算法与分析

1　边表结点与顶点表结点的建立

2　建立一个有n个顶点e条边的有向图

3　有向图的深度优先遍历

4　有向图的广度优先遍历

5　求某个顶点的度

四、运行与测试

正确的运行结果

五、总结与心得

运用邻接表来实现有向图的深度和广度优先遍历，在建立邻接表的时候，我发现运用结点能够更好地表示点与点之间的关系，在邻接表中，我们运用了顶点表结点和边表结点。

无论是以前学习的单链表，双链表，树，二叉树，里面的点都是运用结点来实现数据之间的关系

六、附录（程序完整代码）

ALGraph.h

#ifndefALGraph_H//定义头文件

#defineALGraph_H

constintMaxSize=10;//图的最大顶点数

structArcNode//定义边表结点

{

intadjvex;//存放该顶点的邻接结点在顶点表中的下标

ArcNode*next;//该顶点的其他邻接结点（边表结构）-指向边表中的下一个结点

};

template

structVertexNode//定义顶点表结点

{

DataTypevertex;//存放顶点信息

ArcNode*firstedge;//存放顶点的第一个邻接结点（边表结构）

};

template

classALGraph

{

public:

ALGraph（DataTypea[],intn,inte）;//构造函数，建立一个有n个顶点e条边的图

~ALGraph（）;//析构函数，释放邻接表中各边表结点的存储空间

voidDFSTraverse（intv）;//深度优先遍历图

voidBFSTraverse（intv）;//广度优先遍历图

intDu（intx）;//求第x个顶点的度

private:

VertexNodeadjlist[MaxSize];//存放顶点表的数组

intvertexNum,arcNum;//图的顶点数和边数

};

#endif

ALGraph.cpp

#include

usingnamespacestd;

#include"ALGraph.h"//引入头文件

template

ALGraph:

:

ALGraph（DataTypea[],intn,inte）

{

ArcNode*s;

inti,j,k;

vertexNum=n;arcNum=e;

for（i=0;i

{

adjlist[i].vertex=a[i];

adjlist[i].firstedge=NULL;

}

for（k=0;k

{

cout<<"请输入边的两个顶点的序号：

";

cin>>i>>j;//输入边所依附的两个顶点的编号

s=newArcNode;s->adjvex=j;//生成一个边表结点s

s->next=adjlist[i].firstedge;//将结点s插入到第i个边表的表头

adjlist[i].firstedge=s;

}

}

template

ALGraph:

:

~ALGraph（）

{

ArcNode*p;

for（inti=0;i

{

p=adjlist[i].firstedge;

while（p!

=NULL）//循环删除

{

adjlist[i].firstedge=p->next;

deletep;//释放结点空间

p=adjlist[i].firstedge;

}

}

}

template

voidALGraph:

:

DFSTraverse（intv）

{

ArcNode*p;

intj;

cout<

visited[v]=1;

p=adjlist[v].firstedge;//工作指针p指向顶点v的边表

while（p!

=NULL）//依次搜索顶点v的邻接点j

{

j=p->adjvex;

if（visited[j]==0）

DFSTraverse（j）;

p=p->next;

}

}

template

voidALGraph:

:

BFSTraverse（intv）

{

intfront=-1,rear=-1;//初始化队列,假设队列采用顺序存储且不会发生溢出

intQ[MaxSize];

ArcNode*p;

cout<

while（front!

=rear）//当队列非空时

{

v=Q[++front];

p=adjlist[v].firstedge;//工作指针p指向顶点v的边表

while（p!

=NULL）

{

intj=p->adjvex;

if（visited[j]==0）

{

cout<

}

p=p->next;

}

}

}

template

intALGraph:

:

Du（intx）//求第x个顶点的度

{

intcount=0;

ArcNode*p;

p=adjlist[x].firstedge;

while（p!

=NULL）

{

count++;

p=p->next;

}

returncount;

}

ALGraphmain.cpp

#include

usingnamespacestd;

#include"ALGraph.cpp"

intvisited[MaxSize]={0};

voidmain（）

{

charch[]={'A','B','C','D','E'};

inti;

ALGraphALG（ch,5,6）;

for（i=0;i

visited[i]=0;

cout<<"深度优先遍历序列是：

";

ALG.DFSTraverse（0）;

cout<

for（i=0;i

visited[i]=0;

cout<<"广度优先遍历序列是：

";

ALG.BFSTraverse（0）;

cout<

cout<<"请输入你想要知道度的顶点的序号"<

intx;

cin>>x;

cout<<"第"<

}