程序员经验分享-hwhale

无向图的遍历-BFS与DFS

2023-11-15

一，理论部分

无向图的遍历可用深度搜索（DFS）与广度搜索（BFS）

深度搜索的基本方式是由图的一个节点1出发然后随机选一个与其相邻的节点2，接着在选择一个与其相邻的节点3，当一条路遍历完后再选择最近一个遍历过的、且相邻节点有未遍历过的节点，重复上述操作，直至将图的点遍历完。适合用栈进行执行

广度搜索的基本方式是由图的一个节点出发，然后遍历所有与其相邻的节点，接着再遍历与相邻节点相邻的节点，重复上述步骤，直至将图上的节点遍历完

遍历的关键是如何判断节点是否已经遍历过，可以定义一个辅助结构体进行判断，结构体里储存的是节点和与之相关的系数flag，未遍历时flag为1，遍历flag后置为0。

这里我分别用邻接矩阵实现DFS，用邻接表实现BFS

二，代码部分

必要头文件及必要设置

#include <iostream>
#define MVNum 100       //最大顶点数 
#define MaxInt 32767   //极大值，即无限 
#include<stack>        //栈的头文件
#define PrintLine printf("\n") //换行
using namespace std;

辅助结构体的定义 

//定义辅助结构体类型
typedef struct Vexs{
	char vex;
	int flag;
}Vex[MVNum];

初始化方式是将图的节点依次存入，flag全部置为1

用邻接矩阵储存的图的初始化

	for(int i=0;i<G.vexnum;i++)//初始化辅助结构体 
	{
		V[i].vex=G.vexs[i];
		V[i].flag=1;//将每个节点的flag置为1
	}

用邻接表储存的图的初始化

for(int i=0;i<G.vexnum;i++)//初始化辅助结构体 
		{
			V[i].vex=G.vertices[i].data;
			V[i].flag=1;//将每个节点的flag置为0 
		}

判断是否完全遍历完成

//判断是否遍历完
int IsAllPrint(Vex V,int n)
{
	int flag = 1;
	for(int i = 0;i<n;i++)
	{
		if(V[i].flag==1) return 0;
	}
	return 1;
}

邻接矩阵储存图的基本操作

// 邻接矩阵储存图
typedef struct{
	char vexs[MVNum];    //顶点表 
	int arcs[MVNum][MVNum];  //邻接矩阵 
	int vexnum,arcnum; //图的当前点数和边数 
}AMGraph;

//返回顶点v在图中顶点表的位置 (邻接矩阵)
int LocateVex1(AMGraph &G,char v)
{
	for(int i=0;i<G.vexnum;++i)
		if(G.vexs[i]==v)
			return i;
	 
}

//创建邻接矩阵 
void CreateUDM(AMGraph &G)  
{
	char v1,v2;
	int w,i,j,k;
	cout<<"请输入总定点数与总边数："<<endl;
	cin>>G.vexnum>>G.arcnum;
	for(i=0;i<G.vexnum;++i)
	{
		cout<<"请输入第"<<i+1<<"个点"<<endl; 
		cin>>G.vexs[i];
	}
	
	for(i=0;i<G.vexnum;++i)//初始化矩阵，使权值全为最大值 
		for(int j=0;j<G.vexnum;++j)
			G.arcs[i][j]=MaxInt;
			
	for(k=0;k<G.arcnum;++k)
	{
		cout<<"请输入两个顶点以及它们连成边的权值："<<endl;
		cin>>v1>>v2>>w;
		i = LocateVex1(G,v1);j=LocateVex1(G,v2); //返回顶点的位置 
		G.arcs[i][j]=w;    //赋予权值 
		G.arcs[j][i]=G.arcs[i][j];  //将其对称点赋予相同的权值 
	}
}
//输出矩阵 
void PrintUDM(AMGraph &G)
{
	for(int i=0;i<G.vexnum;i++)
		{
			for(int j=0;j<G.vexnum;j++)
			{
				if(G.arcs[i][j]==MaxInt)
				printf("  ∞");
				else
				printf("%3d ",G.arcs[i][j]);
			}
			cout<<endl;
		}
}
//遍历图（邻接矩阵）
void DFS(AMGraph &G)
{
	Vex V;
	stack<struct Vexs> S;
	int i,j;
	for(int i=0;i<G.vexnum;i++)//初始化辅助结构体 
	{
		V[i].vex=G.vexs[i];
		V[i].flag=1;//将每个节点的flag置为1
	}
	S.push(V[0]);
	cout<<V[0].vex<<" ";
	V[0].flag=0;
	for(i=0;i<G.vexnum;i++)
	{
		int tag = 1;
		for(j=0;j<G.vexnum;j++)
		{
			if(G.arcs[i][j]!=MaxInt&&V[j].flag==1)
			{
				cout<<V[j].vex<<" ";
				S.push(V[j]);
				V[j].flag = 0;
				i = j - 1;
				tag = 0;
				break;
			}
		}
		if(tag==1) 
		{
			i = LocateVex1(G,S.top().vex)-1;
			S.pop();
		}
		if(IsAllPrint(V,G.vexnum)) break;
	}
}

邻接表储存图的基本操作

//邻接表储存图
typedef struct Arcnode{ //边结点 
	int adjvex;   //该边所指顶点位置 
	struct Arcnode *nextarc;  //指向下一条边的指针 
	int longth; //边的权值 
}ArcNode;

typedef struct Vnode{  //顶点信息 
	char data;         //顶点 
	ArcNode *firstarc;   //指向第一条依附该顶点的边的指针 
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型

typedef struct{
	AdjList vertices;//定义邻接表 
	int vexnum,arcnum; //图的顶点数与边数 
}ALGraph; 
//返回顶点v在图的顶点表的位置 
int LocateVex2(ALGraph &G,char v)
{
	for(int i =0;i<G.vexnum;++i)
		if(G.vertices[i].data==v)
			return i;
} 
//创建邻接表
void CreateUDG(ALGraph &G)
{
	int i,j,k,w;
	char v1,v2;
	ArcNode *p1,*p2;
	cout<<"请输入顶点数与边数："<<endl;
	cin>>G.vexnum>>G.arcnum;
	for(i=0;i<G.vexnum;++i)
	{
		cout<<"请输入第"<<i+1<<"个顶点"<<endl;
		cin>>G.vertices[i].data;
		G.vertices[i].firstarc=NULL;  //初始化表头结点的指针域 
	 } 
	 for(k=0;k<G.arcnum;++k)
	 {
	 	cout<<"请输入两个顶点与所连成边的权值"<<endl;
		cin>>v1>>v2>>w; 
		i=LocateVex2(G,v1);j=LocateVex2(G,v2);
		
		p1 = new ArcNode;
		p1->adjvex=j;
		p1->nextarc=G.vertices[i].firstarc;
		G.vertices[i].firstarc=p1;
		G.vertices[i].firstarc->longth=w;
		
		//进行对称处理 
		p2 = new ArcNode;
		p2->adjvex=i;
		p2->nextarc=G.vertices[j].firstarc;
		G.vertices[j].firstarc=p2;
		G.vertices[j].firstarc->longth=w;
	} 
 }
//输出邻接表 
void PrintUDG(ALGraph &G)
{
	ArcNode *p;
	VNode *q;
	for(int i=0;i<G.vexnum;i++)
	{
		printf("%2c",G.vertices[i].data);
		p = G.vertices[i].firstarc;
		while(p!=NULL)
		{
			printf("%2c",G.vertices[p->adjvex].data);
			p=p->nextarc;
		}
		printf("\n");	
	}
}
//邻接表遍历
void BFS(ALGraph &G,Vex V,int i)//i为节点位置 
{
	if(IsAllPrint(V,G.vexnum))return; 
	ArcNode *p=G.vertices[i].firstarc;
	if(V[i].flag==1)
	{
		cout<<G.vertices[i].data<<" ";
		V[i].flag=0;
	}
	while(p!=NULL)
	{
		if(V[p->adjvex].flag==1)
		{
			cout<<G.vertices[p->adjvex].data<<" ";
			V[p->adjvex].flag=0;
			BFS(G,V,p->adjvex);
		}
		p=p->nextarc;
		if(IsAllPrint(V,G.vexnum)) return;
		
	}
}

 三，完整代码

#include <iostream>
#define MVNum 100       //最大顶点数 
#define MaxInt 32767   //极大值，即无限 
#include<stack> //栈的头文件
#define PrintLine printf("\n")//换行 
using namespace std;
//定义辅助结构体类型
typedef struct Vexs{
	char vex;
	int flag;
}Vex[MVNum];

//判断是否遍历完
int IsAllPrint(Vex V,int n)
{
	int flag = 1;
	for(int i = 0;i<n;i++)
	{
		if(V[i].flag==1) return 0;
	}
	return 1;
} 
// 邻接矩阵储存图
typedef struct{
	char vexs[MVNum];    //顶点表 
	int arcs[MVNum][MVNum];  //邻接矩阵 
	int vexnum,arcnum; //图的当前点数和边数 
}AMGraph;

//返回顶点v在图中顶点表的位置 (邻接矩阵)
int LocateVex1(AMGraph &G,char v)
{
	for(int i=0;i<G.vexnum;++i)
		if(G.vexs[i]==v)
			return i;
	 
}

//创建邻接矩阵 
void CreateUDM(AMGraph &G)  
{
	char v1,v2;
	int w,i,j,k;
	cout<<"请输入总定点数与总边数："<<endl;
	cin>>G.vexnum>>G.arcnum;
	for(i=0;i<G.vexnum;++i)
	{
		cout<<"请输入第"<<i+1<<"个点"<<endl; 
		cin>>G.vexs[i];
	}
	
	for(i=0;i<G.vexnum;++i)//初始化矩阵，使权值全为最大值 
		for(int j=0;j<G.vexnum;++j)
			G.arcs[i][j]=MaxInt;
			
	for(k=0;k<G.arcnum;++k)
	{
		cout<<"请输入两个顶点以及它们连成边的权值："<<endl;
		cin>>v1>>v2>>w;
		i = LocateVex1(G,v1);j=LocateVex1(G,v2); //返回顶点的位置 
		G.arcs[i][j]=w;    //赋予权值 
		G.arcs[j][i]=G.arcs[i][j];  //将其对称点赋予相同的权值 
	}
}
//输出矩阵 
void PrintUDM(AMGraph &G)
{
	for(int i=0;i<G.vexnum;i++)
		{
			for(int j=0;j<G.vexnum;j++)
			{
				if(G.arcs[i][j]==MaxInt)
				printf("  ∞");
				else
				printf("%3d ",G.arcs[i][j]);
			}
			cout<<endl;
		}
}
//遍历图（邻接矩阵）
void DFS(AMGraph &G)
{
	Vex V;
	stack<struct Vexs> S;
	int i,j;
	for(int i=0;i<G.vexnum;i++)//初始化辅助结构体 
	{
		V[i].vex=G.vexs[i];
		V[i].flag=1;//将每个节点的flag置为1
	}
	S.push(V[0]);
	cout<<V[0].vex<<" ";
	V[0].flag=0;
	for(i=0;i<G.vexnum;i++)
	{
		int tag = 1;
		for(j=0;j<G.vexnum;j++)
		{
			if(G.arcs[i][j]!=MaxInt&&V[j].flag==1)
			{
				cout<<V[j].vex<<" ";
				S.push(V[j]);
				V[j].flag = 0;
				i = j - 1;
				tag = 0;
				break;
			}
		}
		if(tag==1) 
		{
			i = LocateVex1(G,S.top().vex)-1;
			S.pop();
		}
		if(IsAllPrint(V,G.vexnum)) break;
	}
} 

//邻接表储存图
typedef struct Arcnode{ //边结点 
	int adjvex;   //该边所指顶点位置 
	struct Arcnode *nextarc;  //指向下一条边的指针 
	int longth; //边的权值 
}ArcNode;

typedef struct Vnode{  //顶点信息 
	char data;         //顶点 
	ArcNode *firstarc;   //指向第一条依附该顶点的边的指针 
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型

typedef struct{
	AdjList vertices;//定义邻接表 
	int vexnum,arcnum; //图的顶点数与边数 
}ALGraph; 
//返回顶点v在图的顶点表的位置 
int LocateVex2(ALGraph &G,char v)
{
	for(int i =0;i<G.vexnum;++i)
		if(G.vertices[i].data==v)
			return i;
} 
//创建邻接表
void CreateUDG(ALGraph &G)
{
	int i,j,k,w;
	char v1,v2;
	ArcNode *p1,*p2;
	cout<<"请输入顶点数与边数："<<endl;
	cin>>G.vexnum>>G.arcnum;
	for(i=0;i<G.vexnum;++i)
	{
		cout<<"请输入第"<<i+1<<"个顶点"<<endl;
		cin>>G.vertices[i].data;
		G.vertices[i].firstarc=NULL;  //初始化表头结点的指针域 
	 } 
	 for(k=0;k<G.arcnum;++k)
	 {
	 	cout<<"请输入两个顶点与所连成边的权值"<<endl;
		cin>>v1>>v2>>w; 
		i=LocateVex2(G,v1);j=LocateVex2(G,v2);
		
		p1 = new ArcNode;
		p1->adjvex=j;
		p1->nextarc=G.vertices[i].firstarc;
		G.vertices[i].firstarc=p1;
		G.vertices[i].firstarc->longth=w;
		
		//进行对称处理 
		p2 = new ArcNode;
		p2->adjvex=i;
		p2->nextarc=G.vertices[j].firstarc;
		G.vertices[j].firstarc=p2;
		G.vertices[j].firstarc->longth=w;
	} 
 }
//输出邻接表 
void PrintUDG(ALGraph &G)
{
	ArcNode *p;
	VNode *q;
	for(int i=0;i<G.vexnum;i++)
	{
		printf("%2c",G.vertices[i].data);
		p = G.vertices[i].firstarc;
		while(p!=NULL)
		{
			printf("%2c",G.vertices[p->adjvex].data);
			p=p->nextarc;
		}
		printf("\n");	
	}
}
//邻接表遍历
void BFS(ALGraph &G,Vex V,int i)//i为节点位置 
{
	if(IsAllPrint(V,G.vexnum))return; 
	ArcNode *p=G.vertices[i].firstarc;
	if(V[i].flag==1)
	{
		cout<<G.vertices[i].data<<" ";
		V[i].flag=0;
	}
	while(p!=NULL)
	{
		if(V[p->adjvex].flag==1)
		{
			cout<<G.vertices[p->adjvex].data<<" ";
			V[p->adjvex].flag=0;
			BFS(G,V,p->adjvex);
		}
		p=p->nextarc;
		if(IsAllPrint(V,G.vexnum)) return;
		
	}
} 
void Menu()
{
	int choice;
	cout<<"================================"<<endl;
	cout<<"1.邻接矩阵创建图\n"<<"2.邻接表创建图\n";
	cout<<"================================"<<endl;
	cout<<"请输入你要进行的操作：" <<endl;
	cin>>choice;
	if(choice==1)
	{
		AMGraph G;
		CreateUDM(G);
		PrintLine;
		PrintUDM(G);
		PrintLine;
		DFS(G);
		
	}
	else if(choice==2)
	{
		ALGraph G;
		CreateUDG(G);
		PrintLine;
		PrintUDG(G);
		PrintLine;
		Vex V;
		for(int i=0;i<G.vexnum;i++)//初始化辅助结构体 
		{
			V[i].vex=G.vertices[i].data;
			V[i].flag=1;//将每个节点的flag置为0 
		}
			BFS(G,V,0);
		}
	else
	cout<<"输入错误！";
	 
}

int main()
{
 	Menu();
 	return 1;
	
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

深度搜索

广度搜索

图论

网络图

无向图的遍历-BFS与DFS 的相关文章

  • react中使用less和全局样式

    前言 使用create react app脚手架搭建的react项目 会自带css和sass 但是没有less 如果在项目中需要使用less 需要进行下载并进行一些配置 1 配置 1 暴露webpack配置文件 create react a

随机推荐

  • 解决 in ./node_modules/cesium/Source/ThirdParty/zip.js报错

    由于在 node modules cesium Source ThirdParty zip js 文件中使用了 import meta 语法 webpack 默认不支持 在进行项目构建时 会报如下错误 提示信息需要添加 loader 接下来

  • 谷歌浏览器配置微信浏览器_使用Chrome修改user agent模拟微信内置浏览器

    很多时候 我们需要模拟微信内置浏览器 今天教大家用chrome简单模拟 如图设置 F12或者右键审查元素进入开发者模式 点击Emulation 然后点击Network 把Spoof user agent改成Other 并把下面的带复制进去

  • PaddleSpeech调研、安装、使用

    PaddleSpeech概述 PaddleSpeech asr 模块目前只支持中英文的语音自动识别 建议在Linux环境下安装和使用 配置环境要求 gcc gt 4 8 5 paddlepaddle gt 2 4 1 python gt 3

  • 概率论与数理统计

    目录 一 概率论的基本概念 1 1 概率论的直观解释和数学定义 1 2 条件概率与乘法公式 1 3 全概率公式与贝叶斯公式 1 4 事件的独立性 二 随机变量与分布函数 2 1 随机变量与分布函数 2 2 离散型随机变量和常用分布 2 3

  • 定时任务——Cron表达式详解

    Cron表达式是一个字符串 字符串以5或6个空格隔开 分为6或7个域 每一个域代表一个含义 Cron有如下两种语法格式 Seconds Minutes Hours DayofMonth Month DayofWeek Year或 Secon

  • C++ : 在一个string字符串中查找给定的字符串并提取

    C 在一个string字符串中查找给定的字符串并提取 1 string find last of 返回类型 size t 2 string find first of 返回类型 size t 3 string substr size t a

  • 力扣刷题-面试题 17.13. 恢复空格、字典树、前缀树的应用

    基本概念 Trie 树 又称单词查找树 前缀树 是一种树形结构 典型应用是用于统计 排序和保存大量的字符串 但不仅限于字符串 它的优点是 利用字符串的公共前缀来减少查询时间 最大限度地减少无谓的字符串比较 比哈希表更快 基本性质 根节点不包

  • 正负样本分配策略（OTA, SimOTA，TAS）

    文章目录 OTA SimOTA TAL ATSS OTA 论文 OTA Optimal Transport Assignment for Object Detection 代码 Megvii BaseDetection OTA 标签分配算法

  • c++静态代码扫描工具clang-tidy详细介绍

    clang tidy 文章目录 clang tidy 1 什么是clang tidy 2 clang tidy可以解决什么问题 3 工作原理 4 如何使用clang tidy 4 总结 5 举例说明 1 什么是clang tidy Clan

  • 十五年学不会英语的原因

    学习前预热 轻松学英语第一步 建立英语思维 为什么大家学英语学得这么累 最后依然对英语糊糊涂涂 原因只有一个 就是我们的学习能力太差了 我们的老师太笨了 这篇文章主要是给大家讲英语的基本结构 看了这篇文章 你们会突然就明白 英语怎么会如此简

  • 第19章：python自动化——ChromeOptions与WebUI实操

    目录 一 ChromeOptions设置项 二 WebUI实操 一 ChromeOptions设置项 浏览器在启动之初 如果需要对浏览器进行一些特定内容的定义 可以直接通过浏览器的options类来实现相对应的配置内容 不同的浏览器有不同的

  • Vue中如何配置自定义路径别名

    Vue中如何配置自定义路径别名 在我们日常开发中 常常会导入一些模块或者组件 如果采用相对路径的方式 import uEditor from components tools 会显得臃肿 多余 如果引用稍有差错就会出现 404的报错 不优雅

  • A Survey on Large Language Model based Autonomous Agents

    本文是LLM系列的文章 针对 A Survey on Large Language Model based Autonomous Agents 的翻译 基于大模型的自动agents综述 摘要 1 引言 2 基于LLM的自动代理构建 3 基于

  • 学网络安全都是一群什么人？

    大家好呀 我是知了姐 又是一期学员故事栏目 3月下旬知了堂信安方向开新班 知了姐跟着去采访 了解到新学员们的求学故事 嘿你别说 虽然大家出身专业不同 经历背景不同 如今却在同一个地点相遇 加入到知了堂这个大家庭 不同专业 年龄的他们 为什么

  • 格式工厂5.10.0版本安装

    目前格式工厂有很多 大多都可以进行视频转换 之前遇到一个用ffmpeg拉流保存的MP4在vlc和迅雷都无法正常播放的问题 发现视频长度不对 声音也不对 最后换到了格式工厂的格式播放器是可以正常播放的 格式工厂下载之家的地址 https ww

  • OSG for Android新手教程系列（二）——项目配置

    在上一篇教程中 主要介绍了如何把OSG源代码编译成为能够在Android项目下使用的函数库 在这一篇教程中 我将针对如何在自己的Android项目中配置OSG函数库进行详细讲解 现阶段网上关于OSGfor Android的配置方式教程有很多

  • 用户登录的详细流程（二）JWT生成token登录

    JWT生成token登录 1 jwt的构成 1 header 2 payload 3 signature 2 token的登陆原理 3 在实际中如何应用token 1 设置token的生成代码 2 如何从token中获取有用的信息 3 验证

  • 汇编程序设计与计算机体系结构软件工程师教程笔记：总结

    汇编程序设计与计算机体系结构 软件工程师教程 这本书是由Brain R Hall和Kevin J Slonka著 由爱飞翔译 中文版是2019年出版的 个人感觉这本书真不错 书中介绍了三种汇编器GAS NASM MASM异同 全部示例代码都

  • EC11旋转编码器、stm32f103驱动程序

    1 EC11手册的要点 注意 旋转的速度 RC滤波 手册中推荐的电路 已含有RC滤波 输出波形特点 2 硬件电路 加上RC滤波电路 做法是两个端点都采用10pF电容接地 10K 电阻接VCC 实测100pF电容也行 用示波器看看波形有无噪声

  • 无向图的遍历-BFS与DFS

    一 理论部分 无向图的遍历可用深度搜索 DFS 与广度搜索 BFS 深度搜索的基本方式是由图的一个节点1出发然后随机选一个与其相邻的节点2 接着在选择一个与其相邻的节点3 当一条路遍历完后再选择最近一个遍历过的 且相邻节点有未遍历过的节点

热门标签