图的遍历(广度优先遍历BFS,深度优先遍历DFS)

目录

图的遍历概念:

图的广度优先遍历(BFS):

代码实现如下:

测试如下:

注意:

图的深度优先遍历(DFS):

代码实现如下:

测试如下:

总代码:

结语:


图的遍历概念:

给定一个图G和其中任意一个顶点v0,从v0出发,沿着图中各边访问图中的所有顶点,且每个顶点仅被遍历一次。"遍历"即对结点进行某种操作的意思。由于考试大多考邻接矩阵(GraphByMatrix),故下面的遍历都是用邻接矩阵(GraphByMatrix),不是邻接表(GraphByNode)。

图的广度优先遍历(BFS):

广度优先遍历类似于我们前面所学二叉树的层序遍历,一层一层的走,故可以使用队列来模拟实现。

比如:现在有三个抽屉(每个抽屉包含一个红色盒子,红色盒子中又包含一个绿色盒子),所需东西在那个抽屉不清楚,现在要将其找到,广度优先遍历的做法是:

(1)先将三个抽屉打开,在最外层找一遍。

(2)将每个抽屉中红色的盒子打开,再找一遍。

(3)最后将红色盒子中绿色盒子打开,再找一遍。

直到找完所有的盒子,注意:每个盒子只能找一次,不能重复找。

例如下图:

该图的广度优先遍历过程如下:

故其广度优先遍历的结果为:ABCDEFGHI。

代码实现如下:

1、初始化一个布尔类型数组visited,默认所有顶点都没有被遍历到。

2、获取当前开始的顶点V 的下标。

3、定义一个队列,存储当前需要遍历的顶点的下标。

4、取出当前队列的头部。

5、把当前的顶点的这一行都放到队列。

由于getIndexOfV,arrayV,matrix在上一篇文章中已经非常详细的描述过,故这里我只解释其作用,如若需要源码和更加详细的解释请友友前往:图的存储结构 

(1)geiIndexOfV 获取顶点元素在其数组中的下标 。

(2)arrayV 顶点元素的一维数组。

(3)matrix 利用matrix二维数组来存储顶点之间边的权重。

/*** 广度优先遍历* @param v*/public void bfs(char v){//1、初始化一个布尔类型数组,默认所有顶点都没有被遍历到boolean[] visited = new boolean[arrayV.length];//2、获取当前开始的顶点V的下标int index = getIndexOfV(v);//3、定义一个队列,存储当前需要遍历的顶点的下标Queue<Integer> qu = new LinkedList<>();qu.offer(index);//起点放进来while(!qu.isEmpty()){//4、取出当前队列的头部int top = qu.poll();System.out.print(arrayV[top]+":"+"-> ");visited[top] = true;//5、把当前的顶点的这一行都放到队列for(int i = 0;i < arrayV.length;i++){//如果这一行的i下标不等于MAX_VALUE,并且也没有被访问过if(matrix[top][i] != Integer.MAX_VALUE && visited[i] == false){qu.offer(i);//注意,防止重复打印visited[i] = true;}}}System.out.println("null");}

测试如下:

测试代码均围绕下图进行:

遍历结果为BACD显然符合我们的预期。 

注意:

下面话红线的地方不能省去。

如若省去会发生重复遍历例如:

发生了DD的重复打印。

那为什么会发生重复打印呢?这是因为在C出队时,D已经在队列中了但是其还是false,故C出队会再次把D入队,这样就会重复打印。具体过程如下动图:

解决方法:在入队时一起把元素对应下标的visited数组设置为false。

为了方便友友调试下面将测试代码给出:

public static void main(String[] args) {GraphByMatrix graph = new GraphByMatrix(4,true);char[] array = {'A','B','C','D'};graph.initArrayV(array);graph.addEdge('A','B',1);graph.addEdge('A','D',1);graph.addEdge('B','A',1);graph.addEdge('B','C',1);graph.addEdge('C','B',1);graph.addEdge('C','D',1);graph.addEdge('D','A',1);graph.addEdge('D','C',1);graph.bfs('B');}

图的深度优先遍历(DFS):

图的深度优先遍历类似于前面所学二叉树的前序遍历,有路就走,走完没路了再回退,使用递归来实现。

比如:现在有三个抽屉(每个抽屉包含一个红色盒子,红色盒子中又包含一个绿色盒子),所需东西在那个抽屉不清楚,现在要将其找到,深度优先遍历的做法是:

(1)先将第一个抽屉打开,在最外层找一遍。

(2)将第一个抽屉中红色的盒子打开,在红色箱子里找一遍。

(3)将红色盒子中绿色盒子打开,在绿箱子里找一遍。

(4)递归查找剩余两个箱子。

深度优先遍历:将一个抽屉一次性遍历完(包括该抽屉中包含的小盒子),再去递归遍历其它盒子。

其过程如图所示:

其深度优先遍历结果为:ABEGCFDHI。

代码实现如下:

实现一个方法dfschild来进行递归,为什么不用dfs直接递归呢?这是因为如果直接把dfs递归哪visited会一直被开辟,堆上的内存占用太大,要把visited设置在dfs外面才行。

部分流程和前面所说的广度优先遍历类似,关于getIndexOfV,arrayV,matrix在广度优先遍历那已解释故这里不再过多描述。

 /*** 给定顶点,从顶点处开始进行深度优先遍历* @param v*/public void dfs(char v){//1、初始化一个布尔类型数组,默认所有顶点都没有被遍历到boolean[] visited = new boolean[arrayV.length];//2、获取当前开始的顶点V 的下标int index = getIndexOfV(v);//3、开始从index位置进行深度遍历dfsChild(index,visited);System.out.print("null");}/*** 从index位置开始深度优先遍历* @param index* @param visited*/private void dfsChild(int index,boolean[] visited){System.out.print(arrayV[index]+":"+"-> ");visited[index] = true;//当前index位置的,所有的连接点都在这一行for(int i = 0;i < arrayV.length;i++){//如果这一行的i下标不等于0,并且也没有被访问过if(matrix[index][i] != Integer.MAX_VALUE && visited[i] == false){dfsChild(i,visited);}}}

测试如下:

遍历结果为:BADC显然符合我们的预期。

总代码:

import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
public class GraphByMatrix {private char[] arrayV;//存放顶点·private int[][] matrix;//存放边private boolean isDirect;//是否是有向图public GraphByMatrix(int size,boolean isDirect){arrayV = new char[size];matrix = new int[size][size];for(int i = 0;i < size;i++){Arrays.fill(matrix[i],Integer.MAX_VALUE);}this.isDirect = isDirect;}/*** 初始化* @param array 顶点集合*/public void initArrayV(char[] array){for(int i = 0;i < array.length;i++){arrayV[i] = array[i];}}/**** @param v1 起始* @param v2 终点* @param weight 权值*/public void addEdge(char v1,char v2,int weight){int index1 = getIndexOfV(v1);int index2 = getIndexOfV(v2);matrix[index1][index2] = weight;if(!isDirect){matrix[index2][index1] = weight;}}/*** 获取顶点元素在其数组中的下标* @param v* @return*/public int getIndexOfV(char v){for(int i = 0;i < arrayV.length;i++){if(v == arrayV[i]){return i;}}return -1;}/*** 获取顶点的度* @param v* @return*/public int getDevOfV(char v){int indexV = getIndexOfV(v);int count = 0;for(int i = 0;i < arrayV.length;i++){if(matrix[indexV][i] != Integer.MAX_VALUE){count++;}}if(isDirect){for(int i = 0;i < arrayV.length;i++){if(matrix[i][indexV] != Integer.MAX_VALUE){count++;}}}return count;}public void printGraph(){for(int i = 0;i < arrayV.length;i++){System.out.print(arrayV[i] + " ");}System.out.println();for(int i = 0;i < matrix.length;i++){for(int j = 0;j < matrix[i].length;j++){if(matrix[i][j] == Integer.MAX_VALUE) {System.out.print("∞ ");}else {System.out.print(matrix[i][j]+" ");}}System.out.println();}}//广度优先遍历/*** 广度优先遍历* @param v*/public void bfs(char v){//1、初始化一个布尔类型数组,默认所有顶点都没有被遍历到boolean[] visited = new boolean[arrayV.length];//2、获取当前开始的顶点V的下标int index = getIndexOfV(v);//3、定义一个队列,存储当前需要遍历的顶点的下标Queue<Integer> qu = new LinkedList<>();qu.offer(index);//起点放进来while(!qu.isEmpty()){//4、取出当前队列的头部int top = qu.poll();System.out.print(arrayV[top]+":"+"-> ");visited[top] = true;//5、把当前的顶点的这一行都放到队列for(int i = 0;i < arrayV.length;i++){//如果这一行的i下标不等于MAX_VALUE,并且也没有被访问过if(matrix[top][i] != Integer.MAX_VALUE && visited[i] == false){qu.offer(i);//注意,防止重复打印
//                    visited[i] = true;}}}System.out.println("null");}//图的深度优先遍历/*** 给定顶点,从顶点处开始进行深度优先遍历* @param v*/public void dfs(char v){//1、初始化一个布尔类型数组,默认所有顶点都没有被遍历到boolean[] visited = new boolean[arrayV.length];//2、获取当前开始的顶点V 的下标int index = getIndexOfV(v);//3、开始从index位置进行深度遍历dfsChild(index,visited);System.out.print("null");}/*** 从index位置开始深度优先遍历* @param index* @param visited*/private void dfsChild(int index,boolean[] visited){System.out.print(arrayV[index]+":"+"-> ");visited[index] = true;//当前index位置的,所有的连接点都在这一行for(int i = 0;i < arrayV.length;i++){//如果这一行的i下标不等于0,并且也没有被访问过if(matrix[index][i] != Integer.MAX_VALUE && visited[i] == false){dfsChild(i,visited);}}}
}

结语:

其实写博客不仅仅是为了教大家,同时这也有利于我巩固自己的知识点,和一个学习的总结,由于作者水平有限,对文章有任何问题的还请指出,接受大家的批评,让我改进,如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注,这可以激励我写出更加优秀的文章。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/260251.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SSL证书怎么申请最合适

SSL证书对于网络安全的作用毋庸置疑&#xff0c;作为数字证书的一种&#xff0c;皆是由权威数字证书机构验证网站身份后进行颁发&#xff0c;可以实现浏览器和网站服务器数据加密传输。而网站安装部署SSL证书后会在浏览器页面显示安全锁标志&#xff0c;而后数据传输协议则从ht…

Swift Combine 使用 print 操作符调试管道 从入门到精通二十四

Combine 系列 Swift Combine 从入门到精通一Swift Combine 发布者订阅者操作者 从入门到精通二Swift Combine 管道 从入门到精通三Swift Combine 发布者publisher的生命周期 从入门到精通四Swift Combine 操作符operations和Subjects发布者的生命周期 从入门到精通五Swift Com…

【数据结构】每天五分钟,快速入门数据结构(一)——数组

目录 一.初始化语法 二.特点 三.数组中的元素默认值 四.时间复杂度 五.Java中的ArrayList类 可变长度数组 1 使用 2 注意事项 3 实现原理 4 ArrayList源码 5 ArrayList方法 一.初始化语法 // 数组动态初始化&#xff08;先定义数组&#xff0c;指定数组长度&#xf…

【C#】使用代码实现龙年春晚扑克牌魔术(守岁共此时),代码实现篇

欢迎来到《小5讲堂》 大家好&#xff0c;我是全栈小5。 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对知识点的理解和掌握。…

DS:栈和队列的相互实现

创作不易&#xff0c;感谢友友们三连&#xff01;&#xff01; 一、前言 栈和队列的相互实现是用两个栈去实现队列或者是用两个队列去实现栈&#xff0c;这样其实是把问题复杂化的&#xff0c;实际中没有什么应用价值&#xff0c;但是通过他们的相互实现可以让我们更加深入地理…

PyTorch使用Tricks:Dropout,R-Dropout和Multi-Sample Dropout等 !!

文章目录 1、为什么使用Dropout&#xff1f; 2、Dropout的拓展1&#xff1a;R-Dropout 3、Dropout的拓展2&#xff1a;Multi-Sample Dropout 4、Dropout的拓展3&#xff1a;DropConnect 5、Dropout的拓展4&#xff1a;Standout 6、Dropout的拓展5&#xff1a;Gaussian Dropout …

Jest和Mocha对比:两者之间有哪些区别?

什么是单元测试&#xff1f; 所谓单元测试&#xff0c;是对软件中单个功能组件进行测试的一种软件测试方式&#xff0c;其目的是确保代码中的每一个基本单元都能正常运行。因此&#xff0c;开发人员在应用程序开发的整个过程&#xff08;即代码编写过程&#xff09;中都需要进行…

Avalonia学习(二十四)-系统界面

目前项目式练习&#xff0c;界面内容偏多&#xff0c;所以不给大家贴代码了&#xff0c;可以留言交流。此次为大家展示的是物联项目的例子&#xff0c;仅仅是学习&#xff0c;我把一些重点列举一下。 界面无边框 以前的样例主要是通过实现控件来完成的&#xff0c;前面已经有窗…

美团外卖商超药店商品销量

外卖药店商品月销量 外卖商超商品月销量

学习总结19

# 奶牛的耳语 ## 题目描述 在你的养牛场&#xff0c;所有的奶牛都养在一排呈直线的牛栏中。一共有 n 头奶牛&#xff0c;其中第 i 头牛在直线上所处的位置可以用一个整数坐标 pi(0< pi < 10^8) 来表示。在无聊的日子里&#xff0c;奶牛们常常在自己的牛栏里与其它奶牛交…

术业有专攻!三防加固平板助力工业起飞

在日常使用中的商业电脑比较追求时效性&#xff0c;以市场定位做标准&#xff0c;内部元件只需满足一般要求就行&#xff0c;使用寿命比较短。而三防平板电脑是主要运用在复杂、恶劣的环境下所以在需求方面较高,需要保证产品在恶劣条件下正常使用&#xff0c;满足行业领域的需求…

Jakarta Bean Validation

Validation 官网 https://beanvalidation.org/ 常见注解 Bean Validation中定义的注解&#xff1a; 注解详细信息Null被注释的元素必须为 nullNotNull被注释的元素必须不为 nullAssertTrue被注释的元素必须为 trueAssertFalse被注释的元素必须为 falseMin(value)被注释的元素…

【linux】体系结构和os管理

冯诺依曼体系结构 输入单元&#xff1a;包括键盘, 鼠标&#xff0c;扫描仪, 写板等 中央处理器(CPU)&#xff1a;含有运算器和控制器等 输出单元&#xff1a;显示器&#xff0c;打印机等 这里的存储器指的是内存 三者是相互连接的&#xff0c;设备之间会进行数据的来回拷贝&am…

【springboot+vue项目(十五)】基于Oauth2的SSO单点登录(二)vue-element-admin框架改造整合Oauth2.0

Vue-element-admin 是一个基于 Vue.js 和 Element UI 的后台管理系统框架&#xff0c;提供了丰富的组件和功能&#xff0c;可以帮助开发者快速搭建现代化的后台管理系统。 一、基本知识 &#xff08;一&#xff09;Vue-element-admin 的主要文件和目录 vue-element-admin/ |…

人工智能_普通服务器CPU_安装清华开源人工智能AI大模型ChatGlm-6B_001---人工智能工作笔记0096

使用centos安装,注意安装之前,保证系统可以联网,然后执行yum update 先去更新一下系统,可以省掉很多麻烦 20240219_150031 这里我们使用centos系统吧,使用习惯了. ChatGlm首先需要一台个人计算机,或者服务器, 要的算力,训练最多,微调次之,推理需要算力最少 其实很多都支持C…

stable diffusion webui学习总结(2):技巧汇总

一、脸部修复&#xff1a;解决在低分辨率下&#xff0c;脸部生成异常的问题 勾选ADetailer&#xff0c;会在生成图片后&#xff0c;用更高的分辨率&#xff0c;对于脸部重新生成一遍 二、高清放大&#xff1a;低分辨率照片提升到高分辨率&#xff0c;并丰富内容细节 1、先通过…

【LeetCode】树的BFS(层序遍历)精选6题

目录 1. N 叉树的层序遍历&#xff08;中等&#xff09; 2. 二叉树的锯齿形层序遍历&#xff08;中等&#xff09; 3. 二叉树的最大宽度&#xff08;中等&#xff09; 4. 在每个树行中找最大值&#xff08;中等&#xff09; 5. 找树左下角的值&#xff08;中等&#xff09…

票务系统平台架构设计与实现

票务系统是一个复杂的平台&#xff0c;涉及到用户购票、票务管理、支付结算等多方面功能。本文将介绍票务系统平台的架构设计原则、技术选型以及实现过程&#xff0c;帮助读者了解如何构建一个高效、稳定的票务系统。 正文&#xff1a; 1. 系统设计原则 在设计票务系统平台时…

【计算机网络】网络基础

初识网络 一、网络发展二、认识协议三、认识网络协议1. 协议分层2. OSI 七层模型3. TCP/IP五层模型4. OS和网络协议栈 四、网络传输基本流程1. TCP/IP 协议通讯过程2. 以太网通信&#xff08;1&#xff09;以太网通信原理&#xff08;2&#xff09;数据碰撞 3. 数据跨网络传输 …

计算机网络概论和数据通信基础

文章目录 计算机网络概论从物理构成上看&#xff0c;计算机网络包括硬件、软件和协议三大部分计算机网络的功能组成计算机网络的分类网络体系结构分层与体系结构接口、协议和服务数据传送单位OSI模型TCP/IP模型 数据通信基础数字信号调制为模拟信号正交振幅调制QAM 模拟数据编码…