• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

图的遍历及应用

算法笔记 站点默认 1个月前 (11-10) 42次浏览 已收录 1个评论
文章目录[隐藏]

图的遍历

的两种遍历方法: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协议进行授权
转载请注明原文链接:图的遍历及应用
喜欢 (1)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到
(1)个小伙伴在吐槽