图的深度广度遍历算法与数据结构课程设计备课讲稿.docx
《图的深度广度遍历算法与数据结构课程设计备课讲稿.docx》由会员分享，可在线阅读，更多相关《图的深度广度遍历算法与数据结构课程设计备课讲稿.docx（21页珍藏版）》请在冰点文库上搜索。
图的深度广度遍历算法与数据结构课程设计备课讲稿
图的操作
一、问题描述
图是一种较线性表和树更为复杂的数据结构。
在图形结构中，节点间的关系可以是任意的，图中任意两个数据元素之间都可以相关。
由此，图的应用极为广泛。
现在邻接矩阵和邻接表的存储结构下，完成图的深度、广度遍历。
二、基本要求
1、选择合适的存储结构完成图的建立；
2、建立图的邻接矩阵，能按矩阵方式输出图，并在此基础上，完成图的深度和广度遍历，输出遍历序列；
3、建立图的邻接表，并在此基础上，完成图的深度和广度遍历，输出遍历序列；
三、测试数据
四、算法思想
1、邻接矩阵
顶点向量的存储。
用两个数组分别存储数据（定点）的信息和数据元素之间的关系（边或弧）的信息。
2、邻接表
邻接表是图的一种链式存储结构。
在邻接表中，对图中每个定点建立一个单链表，第i个单链表中的节点表示依附于定点vi的边。
每个节点由3个域组成，其中邻接点域（adjvex）指示与定点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的节点；数据域（info）存储和边或弧相关的信息，如权值等。
每个链表上附设一个头节点。
在表头节点中，除了设有链域（firstarc）指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域（data）。
3、图的深度遍历
深度优先搜索遍历类似于树的先根遍历，是树的先跟遍历的推广。
假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，甚至图中所有和v相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
4、图的广度遍历
广度优先遍历类似于树的按层次遍历过程。
假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先与“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
若此时图中尚有顶点未被访问，则另选图中一个曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
五、模块划分
一、基于邻接矩阵的深广度遍历
1．StatusInitQueue（LinkQueue*Q）
根据已知Q初始化队列
2．StatusQueueEmpty（LinkQueueQ）
判断队列是否为空
3．StatusEnQueue（LinkQueue*Q,QElemTypee）
将e压入队尾
4．StatusDeQueue（LinkQueue*Q,QElemType*e）
取队头元素e
5．intLocateVex（MGraphG,VertexTypev）
定位定点v
6．voidCreateGraph（MGraph*G）
建立无向图的邻接矩阵
7．voidPrintGraph（MGraphG）
输出邻接矩阵的无向图
8．intFirstAdjVex（MGraphG,intv）
第一个邻接点的定位
9．intNextAdjVex（MGraphG,intv,intw）
查找下一个邻接点
10．voidDfs（MGraphG,intv）
实现图的一次遍历
11．voidDfsTraverse（MGraphG）
实现图的深度遍历
12．voidBfsTraverse（MGraphG）
实现图的广度遍历
13．Main
主函数
二、基于邻接表实现图的深广度遍历
1．StatusInitQueue（LinkQueue*Q）
根据已知Q初始化队列
2．StatusQueueEmpty（LinkQueueQ）
判断队列是否为空
3．StatusEnQueue（LinkQueue*Q,QElemTypee）
将e压入队尾
4．StatusDeQueue（LinkQueue*Q,QElemType*e）
取队头元素e
5．voidcreateALGraph（ALGraph*G）
建立无向图的邻接矩阵
6．voidPrintGraph（MGraphG）
输出邻接矩阵的无向图
7．intFirstAdjVex（MGraphG,intv）
第一个邻接点的定位
8．intNextAdjVex（MGraphG,intv,intw）
查找下一个邻接点
9．voidDfs（MGraphG,intv）
实现图的一次深度遍历
10．voidDfsTraverse（MGraphG）
实现图的深度遍历
11．voidBFS（ALGraphG,intv）
实现图的一次广度遍历
12．voidBfsTraverse（MGraphG）
实现图的广度遍历
13．Void…………………………………Main
主函数
六、数据结构//（ADT）
1、基于邻接矩阵的图的类型定义
typedefstructArcCell
{VRTypeadj;/*图中有1/0表示是否有边，网中表示边上的权值*/
/*InfoType*info;与边相关的信息*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/
AdjMatrixarcs;/*邻接矩阵*/
intvexnum,arcnum;/*图中当前顶点数和边数*/
}MGraph;
2、基于邻接表的图的类型定义
typedefstructArcNode
{
intadjvex;
structArcNode*nextarc;
}ArcNode;/*表节点*/
typedefstruct
{
TElemTypedata;
ArcNode*firstarc;
}VNode,AdjList[MAXVER];/*表节点*/
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;/*图中当前顶点数和边数*/
}ALGraph;
七、源程序
一、基于邻接矩阵的图的深度、广度遍历
#include"stdlib.h"
#include"stdio.h"
#include"string.h"
#defineTRUE1
#defineFALSE0
#defineOVERFLOW-2
#defineOK1
#defineERROR0
typedefintStatus;
#defineINFINITYINT_MAX/*最大值“无穷”*/
#defineMAX_VERTEX_NUM20/*最大顶点个数*/
typedefintBoolean;
typedefcharVertexType[20];
typedefintVRType;
/**************以下为队列的操作************/
/****队列的类型定义****/
typedefintQElemType;
typedefstructQNode
{QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
/****初始化队列****/
StatusInitQueue（LinkQueue*Q）
{（*Q）.front=（*Q）.rear=（QueuePtr）malloc（sizeof（QNode））;
if（!
（*Q）.front）exit（OVERFLOW）;
（*Q）.front->next=NULL;
returnOK;}
/****判断队列是否为空****/
StatusQueueEmpty（LinkQueueQ）
{if（Q.front==Q.rear）
returnTRUE;
else
returnFALSE;}
/****入队列****/
StatusEnQueue（LinkQueue*Q,QElemTypee）
{QueuePtrp;
p=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）exit（OVERFLOW）;
p->data=e;p->next=NULL;
（*Q）.rear->next=p;
（*Q）.rear=p;
returnOK;}
/****出队列****/
StatusDeQueue（LinkQueue*Q,QElemType*e）
{QueuePtrp;
if（（*Q）.front==（*Q）.rear）returnERROR;
p=（*Q）.front->next;
*e=p->data;
（*Q）.front->next=p->next;
if（（*Q）.rear==p）（*Q）.rear=（*Q）.front;
free（p）;
returnOK;}
/**************以下为图的操作************/
/*图的类型定义*/
typedefstructArcCell
{VRTypeadj;/*图中有1/0表示是否有边，网中表示边上的权值*/
/*InfoType*info;与边相关的信息*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/
AdjMatrixarcs;/*邻接矩阵*/
intvexnum,arcnum;/*图中当前顶点数和边数*/
}MGraph;
/*顶点在顶点向量中的定位*/
intLocateVex（MGraphG,VertexTypev）
{inti;
for（i=0;iif（strcmp（v,G.vexs[i]）==0）break;
returni;
}
/*建立无向图的邻接矩阵*/
voidCreateGraph（MGraph*G）
{inti,j,k;VertexTypev1,v2;
printf（"\nInputMGvexnum,arcnum:
"）;
scanf（"%d,%d",&（*G）.vexnum,&（*G）.arcnum）;
printf（"Input%dvexs:
",（*G）.vexnum）;
for（i=0;i<（*G）.vexnum;i++）/*输入顶点向量*/
{scanf（"%s",（*G）.vexs[i]）;}
printf（"vexslist\n"）;
for（i=0;ivexnum;i++）/*输出顶点向量*/
puts（G->vexs[i]）;
for（i=0;i<（*G）.vexnum;i++）/*邻接矩阵初始化*/
for（j=0;j<（*G）.vexnum;j++）
（*G）.arcs[i][j].adj=0;
printf（"\nInput%darcs（vivj）:
\n",（*G）.arcnum）;
for（k=0;k<（*G）.arcnum;k++）/*输入无权图的边*/
{scanf（"%s%s",v1,v2）;
i=LocateVex（*G,v1）;j=LocateVex（*G,v2）;
（*G）.arcs[i][j].adj=1;
（*G）.arcs[j][i]=（*G）.arcs[i][j];
}
}
/*按邻接矩阵方式输出无向图*/
voidPrintGraph（MGraphG）
{inti,j;
printf（"\nMGraph:
\n"）;
for（i=0;i{printf（"%10s",G.vexs[i]）;
for（j=0;jprintf（"%4d",G.arcs[i][j].adj）;
printf（"\n"）;
}
}
/*查找第1个邻接点*/
intFirstAdjVex（MGraphG,intv）
{intj,p=-1;
for（j=0;jif（G.arcs[v][j].adj==1）{p=j;break;}
returnp;
}
/*查找下一个邻接点*/
intNextAdjVex（MGraphG,intv,intw）
{intj,p=-1;
for（j=w+1;jif（G.arcs[v][j].adj==1）{p=j;break;}
returnp;
}
/*深度遍历*/
Booleanvisited[MAX_VERTEX_NUM];/*设置全局的访问标志数组*/
voidDfs（MGraphG,intv）
{intw;
visited[v]=TRUE;
printf（"%s",G.vexs[v]）;
for（w=FirstAdjVex（G,v）;w>=0;w=NextAdjVex（G,v,w））
if（!
visited[w]）Dfs（G,w）;
}
voidDfsTraverse（MGraphG）
{intv;
for（v=0;vvisited[v]=FALSE;
for（v=0;vif（!
visited[v]）Dfs（G,v）;
}
/*广度遍历*/
voidBfsTraverse（MGraphG）
{intv,u,w;LinkQueueQ;
for（v=0;vInitQueue（&Q）;
for（v=0;vif（!
visited[v]）
{visited[v]=TRUE;
printf（"%s",G.vexs[v]）;
EnQueue（&Q,v）;
while（!
QueueEmpty（Q））
{DeQueue（&Q,&u）;
for（w=FirstAdjVex（G,u）;w>=0;w=NextAdjVex（G,u,w））
if（!
visited[w]）
{visited[w]=TRUE;
printf（"%s",G.vexs[w]）;
EnQueue（&Q,w）;
}
}
}
}
/*主函数*/
main（）
{intw;
MGraphG;
CreateGraph（&G）;
PrintGraph（G）;
printf（"\nDfs:
"）;DfsTraverse（G）;/*深度遍历*/
printf（"\nBfs:
"）;BfsTraverse（G）;/*广度遍历*/
}
二：
基于邻接表的图的深度、广度遍历
#include"stdlib.h"
#include"stdio.h"
#include"string.h"
#defineMAXVER21
#defineN100
typedefcharTElemType[10];
/*循环队列的操作*/
/****队列的类型定义****/
typedefintElemType;
typedefstruct
{
ElemType*base;
intfront,rear;
}SqQueue;
/****初始化队列****/
voidInitQueue（SqQueue*Q）
{Q->base=（ElemType*）malloc（N*sizeof（ElemType））;
Q->front=Q->rear=0;}
/****判断队列是否为空****/
intQueueEmpty（SqQueueQ）
{if（Q.front==Q.rear）
return1;
else
return0;}
/****入队列****/
intEnQueue（SqQueue*Q,ElemTypee）
{if（（Q->rear+1）%N==Q->front）
return0;
Q->base[Q->rear]=e;
Q->rear=（Q->rear+1）%N;
return1;}
/****出队列****/
intDeQueue（SqQueue*Q,ElemType*e）
{if（Q->rear==Q->front）
return0;
*e=Q->base[Q->front];
Q->front=（Q->front+1）%N;
return1;}
/*图的操作*/
/*图的类型定义*/
typedefstructArcNode
{
intadjvex;
structArcNode*nextarc;
}ArcNode;
typedefstruct
{
TElemTypedata;
ArcNode*firstarc;
}VNode,AdjList[MAXVER];
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;
}ALGraph;
/*建立无向图的邻接矩阵*/
voidcreateALGraph（ALGraph*G）
{
inti,s,d;
ArcNode*p,*q;
printf（"\nInputMGvexnum,arcnum:
"）;
scanf（"%d,%d",&（*G）.vexnum,&（*G）.arcnum）;
for（i=1;i<=G->vexnum;i++）
{
printf（"\n输入第%d个顶点信息：
",i）;
scanf（"%s",G->vertices[i].data）;
G->vertices[i].firstarc=NULL;
}//输入第i个结点值并初始化第i个单链表为空
for（i=1;i<=G->arcnum;i++）
{
printf（"\n输入第%d条边的始点和终点：
",i）;
scanf（"%d,%d",&s,&d）;
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=d;
p->nextarc=G->vertices[s].firstarc;
G->vertices[s].firstarc=p;
//将新建的以d为信息的表结点p插入s单链表的头结点后
q=（ArcNode*）malloc（sizeof（ArcNode））;
q->adjvex=s;
q->nextarc=G->vertices[d].firstarc;
G->vertices[d].firstarc=q;
//将新建的以s为信息的表结点q插入d单链表的头结点后
}
}
/*深度遍历*/
intvisited[MAXVER];//定义全局数组遍历visited
voiddfs（ALGraphG,intv）//被遍历的图G采用邻接表作为存储结构，v为出发顶点编号
{
ArcNode*p;
printf（"%s",G.vertices[v].data）;
visited[v]=1;
p=G.vertices[v].firstarc;
while（p!
=NULL）
{
if（visited[p->adjvex]==0）dfs（G,p->adjvex）;
//若p所指表结点对应的邻接顶点未访问则递归地从该顶点出发调用dfs
p=p->nextarc;
}
}
voiddfsTraverse（ALGraphG）
{
intv;
//遍历图之前初始化各未访问的顶点
for（v=1;v<=G.vexnum;v++）
visited[v]=0;
//从各个未被访问过的顶点开始进行深度遍历
for（v=1;v<=G.vexnum;v++）
if（visited[v]==0）dfs（G,v）;
}
/*广度遍历*/
voidBFS（ALGraphG,intv）
//从顶点编号v出发，广度遍历邻接表存储的图G
{
SqQueueQ;ArcNode*p;
InitQueue（&Q）;
printf（"%s",G.vertices[v].data）;
visited[v]=1;
EnQueue（&Q,v）;
while（!
QueueEmpty（Q））
{
v=DeQueue（&Q,&v）;
p=G.vertices[v].firstarc;
while（p!
=NULL）
{
if（visited[p->adjvex]==0）
{
v=p->adjvex;
printf（"%s",G.vertices[v].data）;
visited[v]=1;
EnQueue（&Q,v）;
}
p=p->nextarc;
}
}
}
voidBFSTraverse（ALGraphG）
{
intv;
//遍历G以前，初始化visited数组为0
for（v=1;v<=G.vexnum;v++）
visited[v]=0;
for（v=1;v<=G.vexnum;v++）
if（visited[v]==0）
BFS（G,v）;
}
voidmain（）
{
ALGraphG;
createALGraph（&G）;
printf（"深度遍历结果为：
\n"）;
dfsTraverse（G）;
printf（"\n广度遍历结果为：
\n"）;
BFSTraverse（G）;
system（"pause"）;
}
八、测试情况
程序的测试结果如下：
1、基于邻接矩阵的图的深度、广度遍历
结果正确
2、基于邻接表的图的深度、广度遍历
结果正确
九、参考文献
1、严蔚敏，《数据结构C语言》，清华大学出版社。
2、谭浩强，《c语言程序设计》，清华大学出版社。
小结
图的遍历是有关于图的算法中最常见、最典型的算法。
与树的
升级会员 