图的深度广度遍历算法与数据结构课程设计备课讲稿Word文档下载推荐.docx
《图的深度广度遍历算法与数据结构课程设计备课讲稿Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《图的深度广度遍历算法与数据结构课程设计备课讲稿Word文档下载推荐.docx(21页珍藏版)》请在冰点文库上搜索。
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)
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)
实现图的一次广度遍历
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;
/*表节点*/
TElemTypedata;
ArcNode*firstarc;
}VNode,AdjList[MAXVER];
/*表节点*/
AdjListvertices;
}ALGraph;
七、源程序
一、基于邻接矩阵的图的深度、广度遍历
#include"
stdlib.h"
stdio.h"
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;
{
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;
(*Q).rear->
next=p;
(*Q).rear=p;
/****出队列****/
StatusDeQueue(LinkQueue*Q,QElemType*e)
if((*Q).front==(*Q).rear)returnERROR;
p=(*Q).front->
next;
*e=p->
data;
next=p->
if((*Q).rear==p)(*Q).rear=(*Q).front;
free(p);
/**************以下为图的操作************/
/*图的类型定义*/
}MGraph;
/*顶点在顶点向量中的定位*/
intLocateVex(MGraphG,VertexTypev)
{inti;
for(i=0;
i<
G.vexnum;
i++)
if(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);
Input%dvexs:
(*G).vexnum);
(*G).vexnum;
i++)/*输入顶点向量*/
{scanf("
%s"
(*G).vexs[i]);
vexslist\n"
G->
vexnum;
i++)/*输出顶点向量*/
puts(G->
vexs[i]);
i++)/*邻接矩阵初始化*/
for(j=0;
j<
j++)
(*G).arcs[i][j].adj=0;
\nInput%darcs(vivj):
\n"
(*G).arcnum);
for(k=0;
k<
(*G).arcnum;
k++)/*输入无权图的边*/
%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;
\nMGraph:
i<
i++)
{printf("
%10s"
G.vexs[i]);
j<
j++)
%4d"
G.arcs[i][j].adj);
/*查找第1个邻接点*/
intFirstAdjVex(MGraphG,intv)
{intj,p=-1;
if(G.arcs[v][j].adj==1){p=j;
break;
returnp;
/*查找下一个邻接点*/
intNextAdjVex(MGraphG,intv,intw)
for(j=w+1;
/*深度遍历*/
Booleanvisited[MAX_VERTEX_NUM];
/*设置全局的访问标志数组*/
voidDfs(MGraphG,intv)
{intw;
visited[v]=TRUE;
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;
v<
v++)
visited[v]=FALSE;
for(v=0;
visited[v])Dfs(G,v);
/*广度遍历*/
voidBfsTraverse(MGraphG)
{intv,u,w;
LinkQueueQ;
v++)visited[v]=FALSE;
InitQueue(&
Q);
visited[v])
{visited[v]=TRUE;
EnQueue(&
Q,v);
while(!
QueueEmpty(Q))
{DeQueue(&
Q,&
u);
for(w=FirstAdjVex(G,u);
w=NextAdjVex(G,u,w))
visited[w])
{visited[w]=TRUE;
G.vexs[w]);
Q,w);
/*主函数*/
main()
MGraphG;
CreateGraph(&
G);
PrintGraph(G);
\nDfs:
DfsTraverse(G);
/*深度遍历*/
\nBfs:
BfsTraverse(G);
/*广度遍历*/
二:
基于邻接表的图的深度、广度遍历
#defineMAXVER21
#defineN100
typedefcharTElemType[10];
/*循环队列的操作*/
typedefintElemType;
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;
return0;
intEnQueue(SqQueue*Q,ElemTypee)
{if((Q->
rear+1)%N==Q->
front)
Q->
base[Q->
rear]=e;
rear=(Q->
rear+1)%N;
return1;
intDeQueue(SqQueue*Q,ElemType*e)
{if(Q->
rear==Q->
*e=Q->
front];
front=(Q->
front+1)%N;
/*图的操作*/
intadjvex;
structArcNode*nextarc;
TElemTypedata;
voidcreateALGraph(ALGraph*G)
{
inti,s,d;
ArcNode*p,*q;
for(i=1;
=G->
{
\n输入第%d个顶点信息:
i);
G->
vertices[i].data);
G->
vertices[i].firstarc=NULL;
}//输入第i个结点值并初始化第i个单链表为空
arcnum;
\n输入第%d条边的始点和终点:
s,&
d);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->
adjvex=d;
nextarc=G->
vertices[s].firstarc;
vertices[s].firstarc=p;
//将新建的以d为信息的表结点p插入s单链表的头结点后
q=(ArcNode*)malloc(sizeof(ArcNode));
q->
adjvex=s;
vertices[d].firstarc;
vertices[d].firstarc=q;
//将新建的以s为信息的表结点q插入d单链表的头结点后
intvisited[MAXVER];
//定义全局数组遍历visited
voiddfs(ALGraphG,intv)//被遍历的图G采用邻接表作为存储结构,v为出发顶点编号
ArcNode*p;
printf("
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;
=G.vexnum;
visited[v]=0;
//从各个未被访问过的顶点开始进行深度遍历
v<
v++)
if(visited[v]==0)dfs(G,v);
/*广度遍历*/
voidBFS(ALGraphG,intv)
//从顶点编号v出发,广度遍历邻接表存储的图G
SqQueueQ;
ArcNode*p;
G.vertices[v].data);
v=DeQueue(&
v);
adjvex]==0)
v=p->
adjvex;
voidBFSTraverse(ALGraphG)
//遍历G以前,初始化visited数组为0
if(visited[v]==0)
BFS(G,v);
voidmain()
ALGraphG;
createALGraph(&
深度遍历结果为:
dfsTraverse(G);
\n广度遍历结果为:
BFSTraverse(G);
system("
pause"
八、测试情况
程序的测试结果如下:
1、基于邻接矩阵的图的深度、广度遍历
结果正确
2、基于邻接表的图的深度、广度遍历
九、参考文献
1、严蔚敏,《数据结构C语言》,清华大学出版社。
2、谭浩强,《c语言程序设计》,清华大学出版社。
小结
图的遍历是有关于图的算法中最常见、最典型的算法。
与树的