图的遍历及应用
图的遍历
图的两种遍历方法：DFS和BFS
dfs遍历代码（教材上的）
//深度优先遍历算法
#include "graph.cpp"
int visited[MAXV]={0};
void DFS(AdjGraph *G,int v)
{
ArcNode *p;
visited[v]=1; //置已访问标记
printf("%d ",v); //输出被访问顶点的编号
p=G->adjlist[v].firstarc; //p指向顶点v的第一条弧的弧头结点
while (p!=NULL)
{
if (visited[p->adjvex]==0) //若p->adjvex顶点未访问,递归访问它
DFS(G,p->adjvex);
p=p->nextarc; //p指向顶点v的下一条弧的弧头结点
}
}
int main()
{
AdjGraph *G;
int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
int n=5, e=8;
CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表G
printf("深度优先序列(递归):");DFS(G,2);printf("\n");
DestroyAdj(G); //销毁邻接表
return 1;
}bfs遍历代码
typedef struct
{
ElemType data[MaxSize];
int front,rear; //队首和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{ q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)
{
free(q);
}
bool QueueEmpty(SqQueue *q)
{
return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)
{ if ((q->rear+1)%MaxSize==q->front) //队满上溢出
return false;
q->rear=(q->rear+1)%MaxSize;
q->data[q->rear]=e;
return true;
}
bool deQueue(SqQueue *&q,ElemType &e)
{ if (q->front==q->rear) //队空下溢出
return false;
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return true;
}
//---------------------------------------------------------
void BFS(AdjGraph *G,int v)
{
int w,i;
ArcNode *p;
SqQueue *qu; //定义环形队列指针
InitQueue(qu); //初始化队列
int visited[MAXV]; //定义顶点访问标志数组
for (i=0;i<G->n;i++) visited[i]=0; //访问标志数组初始化
printf("%2d",v); //输出被访问顶点的编号
visited[v]=1; //置已访问标记
enQueue(qu,v);
while (!QueueEmpty(qu)) //队不空循环
{
deQueue(qu,w); //出队一个顶点w
p=G->adjlist[w].firstarc; //指向w的第一个邻接点
while (p!=NULL) //查找w的所有邻接点
{
if (visited[p->adjvex]==0) //若当前邻接点未被访问
{
printf("%2d",p->adjvex); //访问该邻接点
visited[p->adjvex]=1; //置已访问标记
enQueue(qu,p->adjvex); //该顶点进队
}
p=p->nextarc; //找下一个邻接点
}
}
printf("\n");
}
int main()
{
AdjGraph *G;
int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
int n=5, e=8;
CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表G
printf("广度优先序列:");BFS(G,2);printf("\n");
DestroyAdj(G); //销毁邻接表
return 1;
}图的遍历的应用
基于深度优先遍历的应用
假设图采用邻接表存储，设计一个算法，判断无向图g是否连通。若连通返回true，否则返回false
只需要设计一个函数，将visited数组初始化为0，然后调用dfs函数，从任何一个顶点开始遍历，只会遍历一遍visited数组，当我们发现有值为0的元素就说明该图是不连通的，因为有顶点没有被访问到
//【例8.3】的算法:判断无向图G是否连通
#include "graph.cpp"
int visited[MAXV]; //全局数组
void DFS(AdjGraph *G,int v) //深度优先遍历算法
{ ArcNode *p;
visited[v]=1; //置已访问标记
printf("%d ",v); //输出被访问顶点的编号
p=G->adjlist[v].firstarc; //p指向顶点v的第一个邻接点
while (p!=NULL)
{ if (visited[p->adjvex]==0) //若p->adjvex顶点未访问,递归访问它
DFS(G,p->adjvex);
p=p->nextarc; //p指向顶点v的下一个邻接点
}
}
bool Connect(AdjGraph *G) //判断无向图G的连通性
{ int i;
bool flag=true;
for (i=0;i<G->n;i++) //visited数组置初值
visited[i]=0;
DFS(G,0); //调用前面的中DSF算法,从顶点0开始深度优先遍历
for (i=0;i<G->n;i++)
if (visited[i]==0)
{ flag=false;
break;
}
return flag;
}
int main()
{
AdjGraph *G;
int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
int n=5, e=8;
CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表G
printf("\n图G%s连通的\n",(Connect(G)?"是":"不是"));
DestroyAdj(G); //销毁邻接表
return 1;
}设计一个算法判断从顶点u到v是否存在简单路径
稍微改动一下dfs函数，增加两个形参，v和has，其中has表示判断，v则表示终点，dfs起点从u开始，中间添加条件判断语句，当u等于v时候，则找到了。参数中，u不断变换，就是dfs的带入顶点，v则一直不变
//【例8.4】的算法:判断图G中从顶点u到v是否存在简单路径
#include "graph.cpp"
int visited[MAXV]; //全局数组
void ExistPath(AdjGraph *G,int u,int v,bool &has)
{ //has表示u到v是否有路径,初值为false
int w; ArcNode *p;
visited[u]=1; //置已访问标记
if (u==v) //找到了一条路径
{ has=true; //置has为true并返回
return;
}
p=G->adjlist[u].firstarc; //p指向顶点u的第一个邻接点
while (p!=NULL)
{ w=p->adjvex; //w为顶点u的邻接点
if (visited[w]==0) //若w顶点未访问,递归访问它
ExistPath(G,w,v,has);
p=p->nextarc; //p指向顶点u的下一个邻接点
}
}
int main()
{
AdjGraph *G;
int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
int n=5, e=8;
CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表G
bool has=false;
int u=0, v=3;
ExistPath(G,u,v,has);
printf("\n图G中顶点%d到顶点%d%s路径\n\n",u,v,(has?"有":"没有"));
DestroyAdj(G); //销毁邻接表
return 1;
}设计一个算法，输出从顶点u到v的一条简单路径（假设从顶点u到v至少有一条简单路径）
和上面的一样，稍微修改一下dfs函数，增加一个path数组类型的形参，和d形参（表示路径长度），和v形参（终点）
//【例8.5】的算法:输出图G中从顶点u到v的一条简单路径
#include "graph.cpp"
int visited[MAXV]; //全局数组
void FindaPath(AdjGraph *G,int u,int v,int path[],int d)
{ //d表示path中的路径长度，初始为-1
int w,i; ArcNode *p;
visited[u]=1;
d++; path[d]=u; //路径长度d增1，顶点u加入到路径中
if (u==v) //找到一条路径后输出并返回
{ for (i=0;i<=d;i++)
printf("%d ",path[i]);
printf("\n");
return;
}
p=G->adjlist[u].firstarc; //p指向顶点u的第一个邻接点
while (p!=NULL)
{ w=p->adjvex; //邻接点的编号为w
if (visited[w]==0)
FindaPath(G,w,v,path,d);
p=p->nextarc; //p指向顶点u的下一个邻接点
}
}
int main()
{
AdjGraph *G;
int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
int n=5, e=8;
CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表G
int u=0, v=3;
int path[MAXV];
printf("\n图G中顶点%d到顶点%d的一条简单路径为:",u,v);
FindaPath(G,u,v,path,-1);
DestroyAdj(G); //销毁邻接表
return 1;
}设计一个算法，输出从顶点u到v的所有条简单路径（假设从顶点u到v至少有一条简单路径
采用回溯法
//【例8.6】的算法:输出图G中从顶点u到v的所有简单路径
#include "graph.cpp"
int visited[MAXV]; //全局数组
void FindAllPath(AdjGraph *G,int u,int v,int path[],int d)
{ //d表示path中的路径长度，初始为-1
int w,i; ArcNode *p;
d++; path[d]=u; //路径长度d增1，顶点u加入到路径中
visited[u]=1; //置已访问标记
if (u==v && d>=0) //找到一条路径则输出
{ for (i=0;i<=d;i++)
printf("%2d",path[i]);
printf("\n");
}
p=G->adjlist[u].firstarc; //p指向顶点u的第一个邻接点
while (p!=NULL)
{ w=p->adjvex; //w为顶点u的邻接点
if (visited[w]==0) //若w顶点未访问,递归访问它
FindAllPath(G,w,v,path,d);
p=p->nextarc; //p指向顶点u的下一个邻接点
}
visited[u]=0; //恢复环境,使该顶点可重新使用
}
int main()
{
AdjGraph *G;
int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
int n=5, e=8;
CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表G
int u=0, v=3;
int path[MAXV];
printf("\n图G中顶点%d到顶点%d的所有简单路径:\n",u,v);
FindAllPath(G,u,v,path,-1);
DestroyAdj(G); //销毁邻接表
return 1;
}设计一个算法，输出图g中从顶点u到v的长度为l的所有简单路径
增加一个形参l，在判断语句中增加d==l即可，形参l为指定长度
//【例8.7】的算法:输出图G中从顶点u到v的长度为l的所有简单路径
#include "graph.cpp"
int visited[MAXV];
void PathAll(AdjGraph *G,int u,int v,int l,int path[],int d)
{ //d表示path中的路径长度，初始为-1
int w,i; ArcNode *p;
visited[u]=1;
d++; path[d]=u; //路径长度d增1，顶点u加入到路径中
if (u==v && d==l) //输出一条路径
{ printf(" ");
for (i=0;i<=d;i++)
printf("%d ",path[i]);
printf("\n");
}
p=G->adjlist[u].firstarc; //p指向顶点u的第一个邻接点
while (p!=NULL)
{ w=p->adjvex; //w为u的邻接点
if (visited[w]==0) //若该顶点未标记访问,则递归访问之
PathAll(G,w,v,l,path,d);
p=p->nextarc; //p指向顶点u的下一个邻接点
}
visited[u]=0; //恢复环境：使该顶点可重新使用
}
int main()
{
int path[MAXV];
int u=1,v=4,l=3;
int n=5, e=8;
int A[MAXV][MAXV]={
{0,1,0,1,1},
{1,0,1,1,0},
{0,1,0,1,1},
{1,1,1,0,1},
{1,0,1,1,0}};
AdjGraph *G;
CreateAdj(G,A,n,e); //建立图8.1(a)的邻接表
for (int i=0;i<n;i++) //visited数组置初值
visited[i]=0;
printf("图G:\n");DispAdj(G);//输出邻接表
printf("从顶点%d到%d的所有长度为%d路径:\n",u,v,l);
PathAll(G,u,v,l,path,-1);
printf("\n");
DestroyAdj(G); //销毁邻接表
return 1;
}教材还有两个应用，太难这里不写了，看看以后刷题要是遇到该类问题，后面再补
基于广度优先遍历的应用
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：图的遍历及应用
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-11-10)，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
