第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
邻接表或者邻接矩阵为存储结构实现连通无向图的深度优先和广度优先遍历.doc
以邻接表或者邻接矩阵为存储结构，实现连通无向图的深度优先和广
度优先遍历
姓名：
班级：
学号：
完成日期：
1.需求分析
程序设计任务： 设计一个程序，实现以邻接表或者邻接矩阵为存储结构，实现连通无向
图的深度优先和广度优先遍历。
基本要求：以邻接表或者邻接矩阵为存储结构，实现连通无向图的深度优先和广度优先遍
历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生
成树的边集。
测试数据：教科书 p168图7.13(a)。
2.概要设计
ADT Stack{
基本操作:
CreateGraph(ALGraph &G)
//操作结果:图 G 用邻接表表示,创建图；
DFS(ALGraph G,
int v)
//操作结果:深度优先搜索遍历图 G，从序号为 v 的顶点出发，对图 G 做一次深度优先
搜索遍历；
DFSB (ALGraph G,int v)
//操作结果:深度搜索的边集；
BFS(ALGraph G,int v)
//操作结果:广度搜索；
BFSB (ALGraph G,int v)
//操作结果:广度搜索的边集；
}ADT Stack
3.详细设计
定义的所有数据类型：
ArcNode 型；VNode 型；QNode 型；int 型；void 型；char 型。
主程序模块：
/*
图的遍历演示以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历.
以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集.
*/
/*
图的遍历演示以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历.
以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集.
*/
int visited[20];
int k,vi,vj;
//=======================================邻接表
#define MAX_N 20
typedef struct ArcNode //边结点
//后继链指针
//顶点结点
data;
//顶点数据
//邻接点的下标
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
int
ArcNode *firstarc; //边链头指针
}VNode, AdjList[MAX_N];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
//邻接表
//顶点数和边数
//================================图 G 用邻接表表示,创建图
void CreateGraph(ALGraph &G) {
// 图 G 用邻接表表示,创建图
cout<<"请输入顶点数和边数"<>G.vexnum>>G.arcnum;
cout<<"输入顶点序列"<>G.vertices[k].data; //输入顶点序列
G.vertices[k].firstarc=NULL;
}
cout<<"输入与各个顶点相邻的两个边"<>vi>>vj;
ArcNode *p=new ArcNode,*q=new ArcNode;
p->adjvex=vi;
q->adjvex=vj;
p->nextarc=NULL;
G.vertices[k].firstarc=p;
q->nextarc=NULL;
p->nextarc=q;
p=q;
} //end for
} //end CreateGraph
//=========================================深度优先搜索遍历图 G
void DFS(ALGraph G,
int v)
{
//从序号为 v 的顶点出发，对图 G 做一次深度优先搜索遍历
visited[v]=1;
// 打上访问标记
";
cout<nextarc) {
w=x->adjvex;
if(!visited[w])
DFS(G,w);
}
}
void DFSB (ALGraph G,int v)//深度搜索的边集
{
visited[v]=1;
ArcNode *y;
y=(ArcNode*)malloc(sizeof(ArcNode));
if(!y) exit(-1);
y=G.vertices[v].firstarc;
int u=G.vertices[v].data;
int w;
for(;y;y=y->nextarc) {
w=y->adjvex;
if(visited[w]==0){
cout<"<next=NULL;
}
void EnQueue (LinkQueue &Q,int e)//进队
{
QNode *p;
p=(QNode*)malloc(sizeof(QNode));
if(!p) exit(-1);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p; //free(p);
}
int DeQueue (LinkQueue &Q,int &e)//出队
{
if(Q.front==Q.rear)
QNode *p;
p=(QNode*)malloc(sizeof(QNode));
if(!p) exit(-1);
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return e;
}
int QueueEmpty (LinkQueue Q)//判断队列是否为空
{
return -1;
return 1;
if(Q.front==Q.rear)
return 0;
}
void BFS(ALGraph G,int v)//广度搜索
{
int u;
LinkQueue Q;
InitQueue(Q);
if(visited[v]==0) {
visited[v]=1;
cout<nextarc){
";
{
w=z->adjvex;
if(visited[w]==0){
visited[w]=1;
cout<nextarc){
w=r->adjvex;
if(visited[w]==0){
visited[w]=1;
cout<"<
//====================================
函数调用关系图：
主函数
CreateGraph
BFS
BFSB
DFS
DFSB
4.调试分析
（1）调试过程中遇到的问题：
1.创建图的时候出错；
2.深度和广度优先搜索；
3.第一次能运行但结果却是错误的；
4..深度和广度优先搜索的边集写的时候出错。
（2）算法的时空分析：
时间复杂度：O（n 2 ），n 为输入的结点个数 ；空间复杂度 O（visited[20]）；
（3）经验和体会：
遇到了一些问题，如创建图的时候出错；第一次能运行但结果却是错误的等等，后
来看书，有些 bug 实在调试不出来的时候会参考网上的一些代码，进行与自己带码的整合，
将算法完成。这次实现深度优先搜索与广度优先搜索算法的数据结构实验课时刚开始有些丈
二摸不着头脑，浪费了不少课上的时间，后来回去才慢慢深入，一点点了解这些内容，经历
过不少错误之后，终于算是完成了图的创建以及图的深度优先搜索（DFS）与广度优先搜索
（BFS）算法。到现在才真正明白原来专业课都不是很好学的，难度也是相当的大从这次数
据结构实验课我又学到了不少专业知识，悉了实现深度优先搜索与广度优先搜索算法等各种
算法。和上次试验一样，这次题目要把伪代码全部转换为标准 C++，转换过程中容易出错。
有时候代码中简练省略的函数不太会写，只得自己纠结良久。
5.用户使用说明
1.当看到屏幕上显示：“请输入顶点数和边数”的时候，输入顶点数和边数；
2.当看到屏幕上显示：“输入顶点序列”的时候，输入定点序列；
3.当看到屏幕上显示：“输入与各个顶点相邻的两个边”的时候，输入与各个顶点相邻
的两个边；
4.当看到屏幕上显示：“请输入结点数”的时候，输入顶点数；
5.屏幕上显示 “邻接表为：··· ”
6.当看到屏幕上显示：“请输入第一个要访问的结点序号”的时候，输入结点序号；
7.屏幕会输出广度优先搜索及其边集，深度优先搜索及其边集。
6.测试结果
7.附录
源程序：/*图的遍历演示以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历.
以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集.
*/#include
#include
#include
#include
usingnamespacestd;
intvisited[20];
intk,vi,vj;
//=======================================邻接表
#defineMAX_N20
typedefstructArcNode//边结点
{
intadjvex;
//邻接点的下标
structArcNode*nextarc;
}ArcNode;
//顶点结点
typedefstructVNode{
//后继链指针
data;
//邻接表
int
//顶点数据
ArcNode*firstarc; //边链头指针
}VNode,AdjList[MAX_N];
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;
}ALGraph;
//================================图G 用邻接表表示,创建
voidCreateGraph(ALGraph&G){
cin>>G.vexnum>>G.arcnum;
for(k=1;k<=G.vexnum;k++){
//顶点数和边数
// 图G 用邻接表表示,创建图
cout<<"请输入顶点数和边数"<>G.vertices[k].data;//输入顶点序列
G.vertices[k].firstarc=NULL;
}cout<<"输入与各个顶点相邻的两个边"<>vi>>vj;
ArcNode*p=newArcNode,*q=newArcNode;
p->adjvex=vi;
q->adjvex=vj;
p->nextarc=NULL;
G.vertices[k].firstarc=p;
q->nextarc=NULL;
p->nextarc=q;
p=q;
}//endfor
图
态指针;
//动
intv)
}//endCreateGraph
//=========================================深度优先
搜索遍历图GvoidDFS(ALGraphG,
//从序号为v 的顶点出发，对图G 做一次深度优先搜索遍历
visited[v]=1;
// 打上访问标记
";
cout<nextarc){
w=x->adjvex;
if(!visited[w])
DFS(G,w);
}
{
}
voidDFSB(ALGraphG,intv)//深度搜索的边集
{
visited[v]=1;
ArcNode*y;
y=(ArcNode*)malloc(sizeof(ArcNode));
if(!y)exit(-1);
y=G.vertices[v].firstarc;
intu=G.vertices[v].data;
intw;
for(;y;y=y->nextarc){
w=y->adjvex;
if(visited[w]==0){
cout<"<next=NULL;
}voidEnQueue(LinkQueue&Q,inte)//进队
{
QNode*p;
p=(QNode*)malloc(sizeof(QNode));
if(!p)exit(-1);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;//free(p);
}intDeQueue(LinkQueue&Q,int&e)//出队
{
if(Q.front==Q.rear)
QNode*p;
p=(QNode*)malloc(sizeof(QNode));
if(!p)exit(-1);
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
returne;
}intQueueEmpty(LinkQueueQ)//判断队列是否为空
{
if(Q.front==Q.rear)
return1;
return0;
}voidBFS(ALGraphG,intv)//广度搜索
{
intu;
return-1;
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
