图的广度优先遍历和深度优先遍历

这篇具有很好参考价值的文章主要介绍了图的广度优先遍历和深度优先遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言:在上一篇博客我们学习了图的基本操作,包括图的建立、结点插入与删除等操作,怎么判断我们建立的图是否正确,很简单把它输出出来就是,但是如何输出它,这就是图的遍历问题了。

一.图的遍历

图的遍历是指从图中的某一顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图,所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
图的遍历比树的遍历要复杂得多,因为图的任意一个顶点都可能和其余的顶点相邻接,所以在访问某个顶点后,可能沿着某条路径搜索又回到该顶点上。为避免同- .顶点被访问多次,在遍历图的过程中,必须记下每个已访问过的顶点,为此可以设一个辅助数组visited[]来标记项点是否被访问过。图的遍历算法主要有两种:广度优先搜索和深度优先搜索

二.广度优先搜索(BFS)

1.基本原理

广度优先搜索( Breadth-First-Search, BFS)类似于二叉树的层序遍历算法。基本思想是:首先访问起始顶点v,接着由v出发,依次访问v的各个未访问过的邻接顶点w1, w2…,wn,然后依次访问w1, w2…, wn;的所有未被访问过的邻接顶点;再从这些访问过的顶点出发,访问它们所有未被访问过的邻接顶点,直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为始点,重复上述过程,直至图中所有顶点都被访问到为止。Dijkstra单源最短路径算法和Prim最小生成树算法也应用了类似的思想。换句话说,广度优先搜索遍历图的过程是以v为起始点,由近至远依次访问和v有路径相通且路径长度为1,2,… 的顶点。广度优先搜索是-种分层的查找过程,每向前走一步可能访问-批顶点,不像深度优先搜索那样有往回退的情况,因此它不是一个递归的算法。为了实现逐层的访问,算法必须借助一 个辅助队列,以记忆正在访问的顶点的下一层顶点。

2.举例说明

图的广度优先遍历和深度优先遍历

假设从a结点开始访问,a先入队。此时队列非空,取出队头元素a,由于b,c与a邻接且未被访问过,于是依次访问b,c,并将b,c依次入队。队列非空,取出队头元素b,依次访问与b邻接且未被访问的顶点d,e,并将d,e入队(注意: a与b也邻接,但a已置访问标记,故不再重复访问)。此时队列非空,取出队头元素c,访问与c邻接且未被访问的顶点f,g,并将f,g入队。此时,取出队头元素d,但与d邻接且未被访问的顶点为空,故不进行任何操作。继续取出队头元素e,将h入队列…最终取出队头元素h后,队列为空,从而循环自动跳出。遍历结果为abcdefgh。

三.深度优先收索(DFS)

1.基本原理

与广度优先搜索不同,深度优先搜索(Depth-First-Search, DFS)类似于树的先序遍历。如其名称中所暗含的意思-样,这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某- -起始顶点v,然后由v出发,访问与v邻接且未被访问的任意一个顶点w,再访问与wi邻接且未被访问的任意-一个 顶点…重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直至图中所有顶点均被访问过为止。

2.举例说明

以BFS例子的无向图为例,深度优先搜索的过程:首先访问a,并置a访问标记;然后访问与a邻接且未被访问的顶点b,置b访问标记;然后访问与b邻接且未被访问的顶点d,置d访问标记。此时d已没有未被访问过的邻接点,故返回上一个访问过的顶点b,访问与其邻接且未被访问的顶点e,置e .标…以此类推,直至图中所有的顶点都被访问一次。遍历结果为abdehcfg。

四.核心功能实现

1.BFS函数

void BFS(Graph *G,char x){
	int n;              
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  
		printf("Error: 结点不存在\n");
	}
	
	char queue[MAX_VERTEX_NUM], front = -1, rear = -1;          
	queue[++rear] = G->vertex[n];      
	visited[n] = true;                 
	while(front !=rear){        
		char current_vertex=queue[++front];      
		printf("%c ",current_vertex);
		
		for(int w=FirstNeighbor(G,current_vertex);w>=0;w=NextNeighbor(G,current_vertex,G->vertex[w])){    
			if(!visited[w]){
				queue[++rear]=G->vertex[w];
				visited[w]=true;    
			}
		}
	}   
}

2.DFS函数

//DFS函数
void DFS(Graph *G,char x){
	int n;              
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  
		printf("Error: 结点不存在\n");
	}
	printf("%c ",G->vertex[n]);       //访问顶点
	visited2[n]=true;            
	for(int w=FirstNeighbor(G,G->vertex[n]);w>=0;w=NextNeighbor(G,G->vertex[n],G->vertex[w]))
		if(!visited2[w]){
			DFS(G,G->vertex[w]);
		}
}
//DFS相比BFS函数,它使用的是栈也就是递归操作

3.效率分析

BFS(广度优先搜索)和DFS(深度优先搜索)是两种不同的图遍历算法,它们的时间和空间复杂度分析也有所不同。

对于BFS算法,其时间复杂度为O(|V|+|E|),其中|V|表示图中节点的数量,|E|表示边的数量。在BFS中,我们访问每个节点一次,并且遍历了所有与该节点相邻的边,因此时间复杂度为O(|V|+|E|)。对于空间复杂度,BFS需要使用一个队列来存储待访问的节点,因此空间复杂度为O(|V|),其中最坏情况下所有节点都在队列中。因此,当图稠密时,即|E| ~ |V|^2时,BFS的空间复杂度可能会很高。

对于DFS算法,其时间复杂度与图的连接性质有关,最坏情况下可以达到O(|V|+|E|)。然而,实际应用中,DFS的时间复杂度通常比BFS低。对于空间复杂度,DFS需要使用一个栈来存储待访问的节点,因此在最坏情况下,空间复杂度为O(|V|),其中最坏情况下整个图都是一条链。因此,当图非常深时,DFS的空间复杂度可能会很高。

总体而言,BFS和DFS的时间复杂度都是O(|V|+|E|),其中|V|表示图中节点数量,|E|表示边数量。它们的主要区别在于空间复杂度上,BFS需要使用队列存储待访问的节点,空间复杂度为O(|V|),而DFS需要使用栈存储待访问的节点,空间复杂度为O(|V|)。因此,如果空间复杂度很重要,可以选择DFS;如果需要找到最短路径等问题,可以选择BFS。

五.完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTEX_NUM 20  // 最大顶点数

typedef struct {
	char vertex[MAX_VERTEX_NUM];  // 存放顶点信息
	int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 存放边信息
	int vertex_num;  // 顶点数
	int edge_num;  // 边数
} Graph;

bool visited1[MAX_VERTEX_NUM];             //BFS访问标记数组
bool visited2[MAX_VERTEX_NUM];             //DFS访问标记数组

//求图G中顶点x的第一个邻接点下标
int FirstNeighbor(Graph *G,char x){
	int n = -1;      //待查询结点在数组里的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  // 如果查询节点不存在
		printf("Error: 结点不存在\n");
	}
	int count=0;
	int nx;        //第一个邻接点在数组里的下标
	//现在知道了他在第n个,所以我们查询边矩阵第n行中第一个1在哪就知道第一个邻接点是谁
	for(int j=0;j<G->vertex_num;j++){
		if(G->edge[n][j]==1) count++;
		if(count==1){
			nx=j;
			break;
		}
	}
	return nx;
}

int NextNeighbor(Graph *G,char x,char y){
	int n = -1;      //待查询结点在数组里的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  // 如果查询节点不存在
		printf("Error: 结点不存在\n");
	}
	int count=0;
	int ny = -1;   //存放返回邻接点数组下标
	for(int j=0;j<G->vertex_num;j++){
		if(G->vertex[j]==y) {
			ny=j;
			break;
		}
	}
	int nx = -1;   //存放返回邻接点数组下标
	for(int j=ny+1;j<G->vertex_num;j++){
		if(G->edge[n][j]==1){
			nx=j;
			break;
		}   
	}
	return nx;
}

void BFS(Graph *G,char x){
	int n;              
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  
		printf("Error: 结点不存在\n");
	}
	
	char queue[MAX_VERTEX_NUM], front = -1, rear = -1;          
	queue[++rear] = G->vertex[n];      
	visited1[n] = true;                 
	while(front !=rear){        
		char current_vertex=queue[++front];      
		printf("%c ",current_vertex);
		
		for(int w=FirstNeighbor(G,current_vertex);w>=0;w=NextNeighbor(G,current_vertex,G->vertex[w])){    
			if(!visited1[w]){
				queue[++rear]=G->vertex[w];
				visited1[w]=true;    
			}
		}
	}   
}
//你以为这就是执行函数吗?如果你这样做存在多个连通分量绝对出错


//BFS执行函数
void BFSTraverse(Graph *G){
	for(int i=0;i<G->vertex_num;i++){
		visited1[i]=false;           //标记数组初始化
	}
	for(int i=0;i<G->vertex_num;++i){
		if(!visited1[i])
			BFS(G,G->vertex[i]);
	}
}

//DFS函数
void DFS(Graph *G,char x){
	int n;              
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  
		printf("Error: 结点不存在\n");
	}
	printf("%c ",G->vertex[n]);       //访问顶点
	visited2[n]=true;            
	for(int w=FirstNeighbor(G,G->vertex[n]);w>=0;w=NextNeighbor(G,G->vertex[n],G->vertex[w]))
		if(!visited2[w]){
			DFS(G,G->vertex[w]);
		}
}
//DFS相比BFS函数,它使用的是栈也就是递归操作

//DFS执行函数
void DFSTraverse(Graph *G){
	for(int i=0;i<G->vertex_num;i++){
		visited2[i]=false;           //标记数组初始化
	}
	for(int i=0;i<G->vertex_num;++i){
		if(!visited2[i])
			DFS(G,G->vertex[i]);
	}
}

int main(){
	Graph G;
	G.vertex_num=5;
	G.edge_num=6;
	//人为构造图的顶点
	for(int i=0;i<G.vertex_num;i++){
		G.vertex[i]= 'A'+i;
	}
	for(int i=0; i<G.vertex_num; i++){
		for(int j=0; j<G.vertex_num; j++){
			G.edge[i][j]=0;
		}
	}
	//人为构造图的边
	G.edge[0][1]=1;
	G.edge[0][3]=1;
	G.edge[1][2]=1;
	G.edge[2][3]=1;
	G.edge[1][4]=1;
	G.edge[2][4]=1;
	printf("BFS的遍历结果为:");
	BFSTraverse(&G);
	printf("\n");
	printf("DFS的遍历结果为:");
	DFSTraverse(&G);	
	return 0;
}

六.运行结果

图的广度优先遍历和深度优先遍历文章来源地址https://www.toymoban.com/news/detail-508628.html

到了这里,关于图的广度优先遍历和深度优先遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图的遍历-深度优先遍历与广度优先遍历(C语言)

    图的遍历 概念:指的是从图中的任一顶点出发,对图中的所有顶点访问一次且只访问一次。 邻接矩阵及邻接表的创建 : 图的存储结构-无向邻接矩阵与无向邻接表(C语言). 结构定义 邻接矩阵的深度优先遍历操作 邻接矩阵的深度优先递归算法 结构定义 邻接表的深度优先遍

    2024年02月06日
    浏览(48)
  • 大话数据结构-图的深度优先遍历和广度优先遍历

      图的遍历分为深度优先遍历和广度优先遍历两种。   深度优先遍历(Depth First Search),也称为深度优先搜索,简称DFS,深度优先遍历,是指从某一个顶点开始,按照一定的规则,访问并记录下一个未访问顶点。对于非连通图,则是按连通分量,采用同一规则进行深度优

    2024年02月04日
    浏览(58)
  • 图的遍历之 深度优先搜索和广度优先搜索

    深度优先搜索的图文介绍 1. 深度优先搜索介绍 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至

    2024年02月13日
    浏览(52)
  • 蛮力算法之深度优先遍历和广度优先遍历——图的深度优先遍历和广度优先遍历,附带案例:迷宫问题及矩阵中传染性传播问题

    这两种搜索方法本质上都是基于蛮力法思路 这两种搜索方法对有向图和无向图都适用 1.1 邻接矩阵 邻接矩阵示意图: 1.2 邻接表 注意:边结点代表的是图中的边,而并非图中的结点;头结点才表示图中的结点;头结点身后所连接的为边结点 邻接表示意图:(一般默认为出边

    2024年02月05日
    浏览(66)
  • (超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

            根据下图,编写代码实现图的深度优先遍历和广度优先遍历。          按照英文字母顺序,以邻接表为存储结构,实现图的深度优先和广度优先遍历。遍历的顺序从顶点a开始。 以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。   (1)从顶点a,

    2024年02月08日
    浏览(60)
  • 图详解第二篇:图的遍历(广度优先+深度优先)

    所谓图的遍历: 即从图中的任一顶点出发,对图中的所有顶点访问一次且只访问一次。 给定一个图G和其中任意一个顶点v0,从v0出发,沿着图中各边访问图中的所有顶点,且每个顶点仅被遍历一次。 ps: 我们后面讲解这些图相关的算法默认都针对邻接矩阵结构的图去讲解,

    2024年02月08日
    浏览(58)
  • 【数据结构与算法】图的深度优先和广度优先遍历

    😊😊作者简介😊😊 : 大家好,我是南瓜籽,一个在校大二学生,我将会持续分享Java相关知识。 🎉🎉个人主页🎉🎉 : 南瓜籽的主页 ✨✨座右铭✨✨ : 坚持到底,决不放弃,是成功的保证,只要你不放弃,你就有机会,只要放弃的人,他肯定是不会成功的人。 图是一

    2024年02月02日
    浏览(58)
  • 【数据结构】图的遍历:广度优先(BFS),深度优先(DFS)

    目录 1、广度优先(BFS) 算法思想  广度优先生成树  知识树  代码实现  2、深度优先(DFS) 算法思想  深度优先生成树 知识树  代码实现           图的广度优先遍历(BFS)是一种遍历图的算法,其思想是从起始顶点开始遍历图,先访问起始顶点的所有直接邻居,然

    2024年02月04日
    浏览(66)
  • 数据结构学习笔记——图的遍历算法(深度优先搜索和广度优先搜索)

    图的遍历指从图中某一顶点出发(任意一个顶点都可以作为访问的起始顶点),按照某种遍历方法,对图中所有的顶点访问一次且只访问一次。图与树不一样,其中一个顶点可能与多个顶点相连,所以需记录已访问过的顶点,当访问一个顶点后,考虑如何选取下一个要访问的

    2024年02月05日
    浏览(53)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包