图的遍历-----深度优先遍历（dfs）,广度优先遍历（bfs）【java详解】

目录

简单介绍：什么是深度、广度优先遍历？

 深度优先搜索（DFS，Depth First Search）：

大致图解：

 广度优先搜索（BFS，Breadth First Search）：

大致图解：

一.图的创建（邻接矩阵）

 图的创建完整代码：

运行结果：

二.图的深度优先遍历（DFS）:

遍历思想：

算法步骤：

 访问初始结点v：

 查找结点v的第一个邻接结点w：

深度搜索算法：

 ​编辑

 三.图的广度优先遍历（BFS）:

广度优先算法：

深度 优先遍历 && 广度优先遍历的区别：

测试用例：

小结：

简单介绍：什么是深度、广度优先遍历？

图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列。

图的遍历过程中，根据搜索方法的不同，又可以划分为两种搜索策略：

  • 深度优先搜索（DFS，Depth First Search）
  • 广度优先搜索（BFS，Breadth First Search）

 深度优先搜索（DFS，Depth First Search）：

遍历思想：：首先从图中某个顶点v0出发，访问此顶点，标记已访问的顶点，然后依次从v0相邻的顶点出发深度优先遍历，直至图中所有与v路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。

大致图解：

 广度优先搜索（BFS，Breadth First Search）：

遍历思想：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。

大致图解：

一.图的创建（邻接矩阵）

 图的遍历基础是我们首先得有个图，这里我们创建一个图，用邻接矩阵的方法。这里我们创建一个如下图所示的图（左边是图，右边是图所对应的表示方法）：

 图的创建完整代码：

import java.util.*;
public class Graph {
    private ArrayList<String> vertexList;//一个一维数组用于存储顶点的信息
    private int[][] edges;//一个二维数组用于存储对应边的信息
    private int numOfEdges;//记录边的个数
    private boolean[] isVisited;//判断顶点是否被访问
     //测试
    public static void main(String[] args){
        String vertexs[] = {"A","B","C","D","E"};
        Graph graph = new Graph(5);
        for(String vertex : vertexs){
            graph.insertVertex(vertex);
        }
        //插入的节点展示：
        System.out.println("插入的节点展示：");
        for(String vertex : vertexs){
            System.out.print(vertex+" ");
        }
        System.out.println();                 //  A B C D E
        graph.insertEdge(0,1,1);              //A 0 1 1 0 0
        graph.insertEdge(0,2,1);              //B 1 0 1 1 1
        graph.insertEdge(1,2,1);              //C 1 1 0 0 0
        graph.insertEdge(1,3,1);              //D 0 1 0 0 0
        graph.insertEdge(1,4,1);              //E 0 1 0 0 0
        //创建的图展示：
        System.out.println("创建的图展示：");
        graph.showGraph();
        //边个数
        System.out.println("边个数:"+graph.numOfEdges);
    }
    //构造器
    public Graph(int n){
        vertexList = new ArrayList<String>(n);
        edges = new int[n][n];
        numOfEdges = 0;
    }

    //图的创建和展示--》方法
    //展示图
    public void showGraph(){
        for(int[] link : edges){
            System.out.println(Arrays.toString(link));
        }
    }
    //插入顶点
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }
    //插入边
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = 1;
        edges[v2][v1] = 1;
        numOfEdges++;
    }
//图的常见方法
   //得到顶点个数
    public int getNumOfVertex(){
        return vertexList.size();
    }
    //通过索引得到对应的顶点
    public String gerValueByIndex(int i){
        return vertexList.get(i);
    }
    //得到对应边的权重
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
}

运行结果：

二.图的深度优先遍历（DFS）:

遍历思想：

  1. 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
  2. 我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
  3. 显然，深度优先搜索是一个递归的过程

算法步骤：

  1. 访问初始结点v，并标记结点v为已访问。
  2. 查找结点v的第一个邻接结点w。
  3. 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。
  4. 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
  5. 查找结点v的w邻接结点的下一个邻接结点，转到步骤3。

 还是以上面创建的图为例：

 访问初始结点v：

//1.得到第一个邻接点的下标
    public int getFirstNeifhbor(int index){
        for(int j = 0;j < vertexList.size();j++){
            if(edges[index][j] > 0){
                return j;
            }
        }
        return -1;
    }

 查找结点v的第一个邻接结点w：

//2.根据前一个邻接点的下标获取下一个邻接点
    public int getNextNeighbor(int v1,int v2){
        for(int j = v2 + 1;j < vertexList.size();j++){
            if(edges[v1][j] > 0){
                return j;
            }
        }
        return -1;
    }

深度搜索算法：

//深搜遍历算法
    //first step
    private void dfs(boolean[] isVisited,int i){
        System.out.print(getValueByIndex(i)+"->");
        isVisited[i] = true;
        int w = getFirstNeifhbor(i);
        while(w != -1){
            if(!isVisited[w]){
                dfs(isVisited,w);
            }
            w = getNextNeighbor(i,w);
        }
    }
//second step
    public void dfs(){
        isVisited = new boolean[vertexList.size()];
        for(int i = 0;i < vertexList.size();i++){
            if(!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }

遍历结果：

 

 三.图的广度优先遍历（BFS）:

基本思想：

图的广度优先搜索(Broad First Search) 。 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点

算法步骤：

  1. 访问初始结点v并标记结点v为已访问。
  2. 结点v入队列
  3. 当队列非空时，继续执行，否则算法结束。
  4. 出队列，取得队头结点u。
  5. 查找结点u的第一个邻接结点w。
  6. 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：                    6.1若结点w尚未被访问，则访问结点w并标记为已访问。                                               6.2 结点w入队列                                                                                                              6.3查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

广度优先算法：

//对一个结点进行广度优先遍历的方法
private void bfs(boolean[] isVisited, int i) {
	int u ; // 表示队列的头结点对应下标
	int w ; // 邻接结点w
	//队列，记录结点访问的顺序
	LinkedList queue = new LinkedList();
	//访问结点，输出结点信息
	System.out.print(getValueByIndex(i) + "=>");
	//标记为已访问
	isVisited[i] = true;
	//将结点加入队列
	queue.addLast(i);
	
	while( !queue.isEmpty()) {
		//取出队列的头结点下标
		u = (Integer)queue.removeFirst();
		//得到第一个邻接结点的下标 w 
		w = getFirstNeighbor(u);
		while(w != -1) {//找到
			//是否访问过
			if(!isVisited[w]) {
				System.out.print(getValueByIndex(w) + "=>");
				//标记已经访问
				isVisited[w] = true;
				//入队
				queue.addLast(w);
			}
			//以u为前驱点，找w后面的下一个邻结点
			w = getNextNeighbor(u, w); //体现出我们的广度优先
		}
	}
	
} 
//遍历所有的结点，都进行广度优先搜索
public void bfs() {
	isVisited = new boolean[vertexList.size()];
	for(int i = 0; i < getNumOfVertex(); i++) {
		if(!isVisited[i]) {
			bfs(isVisited, i);
		}
	}
}

遍历结果： 

深度 优先遍历 && 广度优先遍历的区别：

 这里由于上面的图比较简单，看不出深度和广度优先遍历的区别，我在举一个图的栗子：

测试用例：

 public static void main(String[] args){

        int n = 8;  //结点的个数
        String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};

        //创建图对象
        Graph graph = new Graph(n);
        //循环的添加顶点
        for(String vertex: Vertexs) {
            graph.insertVertex(vertex);
        }

        //更新边的关系
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);

        //显示一把邻结矩阵
        System.out.println("图的创建：");
        graph.showGraph();

        //测试一把，我们的dfs遍历是否ok
        System.out.println("深度优先遍历：");
        graph.dfs(); // A->B->C->D->E [1->2->4->8->5->3->6->7]
        System.out.println();
        System.out.println("广度优先遍历：");
        graph.bfs(); // A->B->C->D-E [1->2->3->4->5->6->7->8]
    }

运行结果：

最后完整代码：

import java.util.*;

public class Graph {
    private ArrayList<String> vertexList;
    private int[][] edges;
    private int numOfEdges;
    private boolean[] isVisited;

    public static void main(String[] args){

        int n = 8;  //结点的个数
        String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};

        //创建图对象
        Graph graph = new Graph(n);
        //循环的添加顶点
        for(String vertex: Vertexs) {
            graph.insertVertex(vertex);
        }

        //更新边的关系
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);

        //显示一把邻结矩阵
        System.out.println("图的创建：");
        graph.showGraph();

        //测试一把，我们的dfs遍历是否ok
        System.out.println("深度优先遍历：");
        graph.dfs(); // A->B->C->D->E [1->2->4->8->5->3->6->7]
        System.out.println();
        System.out.println("广度优先遍历：");
        graph.bfs(); // A->B->C->D-E [1->2->3->4->5->6->7->8]
    }
    //构造器
    public Graph(int n){
        vertexList = new ArrayList<String>(n);
        edges = new int[n][n];
        numOfEdges = 0;
    }

    //图的常见方法
    public int getNumOfVertex(){
        return vertexList.size();
    }
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    //图的创建和展示
    public void showGraph(){
        for(int[] link : edges){
            System.out.println(Arrays.toString(link));
        }
    }
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = 1;
        edges[v2][v1] = 1;
        numOfEdges++;
    }
    //深度优先搜索：
    //1.得到第一个邻接点的下标
    public int getFirstNeighbor(int index){
        for(int j = 0;j < vertexList.size();j++){
            if(edges[index][j] > 0){
                return j;
            }
        }
        return -1;
    }
    //2.根据前一个邻接点的下标获取下一个邻接点
    public int getNextNeighbor(int v1,int v2){
        for(int j = v2 + 1;j < vertexList.size();j++){
            if(edges[v1][j] > 0){
                return j;
            }
        }
        return -1;
    }
    //深搜遍历算法
    //first step
    private void dfs(boolean[] isVisited,int i){
        System.out.print(getValueByIndex(i)+"->");
        isVisited[i] = true;
        int w = getFirstNeighbor(i);
        while(w != -1){
            if(!isVisited[w]){
                dfs(isVisited,w);
            }
            w = getNextNeighbor(i,w);
        }
    }
    //second step
    public void dfs(){
        isVisited = new boolean[vertexList.size()];
        for(int i = 0;i < vertexList.size();i++){
            if(!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }

    //广度优先遍历：
    //first steop
    public void bfs(boolean[] isVisited,int i){
        int u;
        int w;
        LinkedList queue = new LinkedList();
        System.out.print(getValueByIndex(i)+"->");
        isVisited[i] = true;
        queue.addLast(i);
        while(!queue.isEmpty()){
            u = (Integer) queue.removeFirst();
            w = getFirstNeighbor(u);
            while(w != -1){
                if(!isVisited[w]){
                    System.out.print(getValueByIndex(w)+"->");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                w = getNextNeighbor(u,w);
            }
        }
    }
    //second step
    public void bfs(){
        isVisited = new boolean[vertexList.size()];
        for(int i = 0;i < getNumOfVertex();i++){
            if(!isVisited[i]){
                bfs(isVisited,i);
            }
        }
    }
}

小结：

图的深度优先遍历（Depth First Search，DFS）和广度优先遍历（Breadth First Search，BFS）是两种常用的图遍历算法，它们的主要区别如下：

  1. 遍历顺序：

    • DFS：从起始节点开始，沿着一条路径尽可能深入地遍历，直到无法继续深入为止，然后回溯到前一个节点，再选择另一条路径继续遍历，直到遍历完所有节点。
    • BFS：从起始节点开始，先遍历其所有相邻节点，然后再依次遍历这些相邻节点的相邻节点，以此类推，直到遍历完所有节点。

  2. 数据结构：

    • DFS：通常使用栈（Stack）数据结构来实现，通过递归或显式栈来保存遍历路径。
    • BFS：通常使用队列（Queue）数据结构来实现，通过将节点按照遍历顺序依次加入队列中。

  3. 遍历顺序的特点：

    • DFS：深度优先遍历更加注重深度，会优先探索离起始节点较远的节点，可能会在较深的层级上找到目标节点。
    • BFS：广度优先遍历更加注重广度，会优先探索离起始节点较近的节点，可能会在较浅的层级上找到目标节点。

结语： 写博客不仅仅是为了分享学习经历，同时这也有利于我巩固自己的知识点，总结该知识点，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进。同时也希望读者们不吝啬你们的点赞+关注+收藏，你们的鼓励是我创作的最大动力！

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

数据结构·顺序表

数据结构·顺序表

1数据结构简介 学习数据结构与算法之前&#xff0c;一般是先学数据结构&#xff0c;方便之后学习算法&#xff0c;那么数据结构拆开介绍&#xff0c;就是数据 和 结构&#xff0c;数据&#xff0c;生活中到处都是&#xff0c;结构&#xff0c;就是数据存储的方式&#xff0c;即…
阅读更多...
分布式系统一致性与共识算法

分布式系统一致性与共识算法

分布式系统的一致性是指从系统外部读取系统内部的数据时&#xff0c;在一定约束条件下相同&#xff0c;即数据&#xff08;元数据&#xff0c;日志数据等等&#xff09;变动在系统内部各节点应该是一致的。 一致性模型分为如下几种&#xff1a; ① 强一致性 所有用户在任意时…
阅读更多...
git使用过的命令记录

git使用过的命令记录

目录 git add .git commit --amendgit push -f origin HEAD:mastergit checkout .git stash想把某个pr的修改应用到本地git pull 将远程仓库的最新代码更新到本地git 撤销&#xff0c;放弃本地修改参考文档 git add . 将本地修改提交到暂存区 git commit --amend 如果本地有…
阅读更多...
MySQL 8.0.36 WorkBench安装

MySQL 8.0.36 WorkBench安装

一、下载安装包 百度网盘链接&#xff1a;点击此处下载安装文件 提取码&#xff1a;hhwz 二、安装&#xff0c;跟着图片来 选择Custom,然后点Next 顺着左边框每一项的加号打开到每一个项的最底层&#xff0c;点击选中最底层的项目&#xff0c;再点击传过去右边的绿色箭头&a…
阅读更多...
MATLAB 导出可编辑的eps格式图像

MATLAB 导出可编辑的eps格式图像

任务描述&#xff1a;部分期刊要求提交可编辑的eps格式图像&#xff0c;方便美工编辑对图像进行美化 我试了直接print或者在figure窗口导出&#xff0c;发现导出的文件放到Adobe AI中并不能编辑&#xff0c;经Google找到解决办法&#xff1a; %EPS exportgraphics(gcf,myVect…
阅读更多...
FFmpeg的HEVC解码器源代码学习笔记-1

FFmpeg的HEVC解码器源代码学习笔记-1

一直想写一个HEVC的码流解析工具&#xff0c;看了雷神264码流解析工具&#xff0c;本来想尝试模仿写一个相似的265码流分析工具&#xff0c;但是发现265的解码过程和结构体和264的不太一样&#xff0c;很多结构体并没有完全暴露出来&#xff0c;没有想到很好的方法获得量化参数…
阅读更多...
[晓理紫]AI专属会议截稿时间订阅

[晓理紫]AI专属会议截稿时间订阅

AI专属会议截稿时间订阅 VX关注{晓理紫}免费，每日更新最新AI专属会议信息，如感兴趣，请转发给有需要的同学，谢谢支持！！ VX关注{晓理紫}免费 IROS 2024 Deadline: Sat Mar 2nd 2024 03:59:59 PM CST (2024-03-02 15:59:59 UTC-08) date_location: October 14-18, 2024. A…
阅读更多...
鸿蒙会成为安卓的终结者吗？

鸿蒙会成为安卓的终结者吗？

随着近期鸿蒙OS系统推送测试版的时间确定&#xff0c;关于鸿蒙系统的讨论再次升温。 作为华为自主研发的操作系统&#xff0c;鸿蒙给人的第一印象是具有颠覆性。 早在几年前&#xff0c;业内就开始流传鸿蒙可能会代替Android的传言。毕竟&#xff0c;Android作为开源系统&…
阅读更多...
第10讲用户登录SpringSecurity查库实现

第10讲用户登录SpringSecurity查库实现

用户登录SpringSecurity查库实现 security包下新建MyUserDetailServiceImpl Service public class MyUserDetailServiceImpl implements UserDetailsService {AutowiredSysUserService sysUserService;Overridepublic UserDetails loadUserByUsername(String username) throw…
阅读更多...
C#算法（12）—对图像像素做X/Y方向的偏移

C#算法（12）—对图像像素做X/Y方向的偏移

我们在上位机开发领域有时候需要对获取的图像的像素做整体的偏移，比如所有像素在X方向上偏移几个像素，或者所有像素在Y方向上偏移几个像素，本文就是开发了像素整体偏移算法来解决这个问题。 比如有一个图像大小为3*3，像素值如下图1，如果我想实现将这个幅图像的像素整体往右…
阅读更多...
【深蓝学院】移动机器人运动规划--第5章 最优轨迹生成--作业

【深蓝学院】移动机器人运动规划--第5章 最优轨迹生成--作业

0. 题目 1. 解答 — Listing1&#xff1a; void minimumJerkTrajGen(// Inputs:const int pieceNum,const Eigen::Vector3d &initialPos,const Eigen::Vector3d &initialVel,const Eigen::Vector3d &initialAcc,const Eigen::Vector3d &terminalPos,const Eig…
阅读更多...
UML---活动图

UML---活动图

活动图概述 活动图&#xff08;Activity Diagram&#xff09;是UML&#xff08;Unified Modeling Language&#xff0c;统一建模语言&#xff09;中的一种行为建模工具&#xff0c;主要用于描述系统或业务流程中的一系列活动或操作。活动图通常用于描述用例中的行为&#xff0c…
阅读更多...
算法项目（5）—— 时序模型TFT数据趋势预测

算法项目（5）—— 时序模型TFT数据趋势预测

本文包含什么？ TFT+机器学习融合完整的在线运行的代码环境(免配置环境)代码介绍运行有问题? csdn上后台随时售后.项目说明 本文主要实现用谷歌的论文Temporal Fusion Transformers for Interpretable Multi-horizon Time Series Forecasting(TFT)来做时间序列的预测. 模型整…
阅读更多...
C++类和对象——多态详解

C++类和对象——多态详解

目录 1.多态的基本语法 2.多态的原理剖析 示例&#xff1a;计算机类 3.纯虚函数和抽象类 示例&#xff1a;制作饮品 4.虚析构和纯虚析构 示例&#xff1a;电脑组装 1.多态的基本语法 代码示例&#xff1a; #include<bits/stdc.h> using namespace std;class mus…
阅读更多...
1903_CoreMark白皮书阅读笔记

1903_CoreMark白皮书阅读笔记

1903_CoreMark白皮书阅读笔记 全部学习汇总&#xff1a; g_embedded: 嵌入式通用技术学习笔记 (gitee.com) 再看ARM的内核架构介绍的时候看到了不同的内核都测试了一个CoreMark/Mhz的参数。从名称看&#xff0c;可以理解为是MCU的算力跑分。至于这部分究竟是测试了哪些功能&…
阅读更多...
CV论文--2024.2.22

CV论文--2024.2.22

SOURCE&#xff1a;CV论文--2024.2.22 1、CounterCurate: Enhancing Physical and Semantic Visio-Linguistic Compositional Reasoning via Counterfactual Examples 中文标题&#xff1a;CounterCurate&#xff1a;通过反事实示例增强物理和语义视觉语言组合推理 简介&…
阅读更多...
“替代云”知多少？Akamai Linode 重新定义公有云服务！

“替代云”知多少？Akamai Linode 重新定义公有云服务！

自2006年云计算概念提出以来&#xff0c;云产业已经成为数字化时代所必备的底层基础&#xff0c;但随着多元化的业务需求的增多&#xff0c;多云战略、本地部署所形成混合环境&#xff0c;都使得云复杂性&#xff0c;日渐成为了迫在眉睫的挑战。 451 Research 云价格指数 (CPI…
阅读更多...
HarmonyOS Stage模型基本概念讲解

HarmonyOS Stage模型基本概念讲解

本文 我们来说harmonyos中的一种应用模型 Stage模型 官方提供了两种模型 一种是早期的 FA模型 另一种就是就是 harmonyos 3.1才开始的新增的一种模型 Stage模型 目前来讲 Stage 会成为现在乃至将来 长期推进的一种模型 也就是 无论是 现在的harmonyos 4.0 乃至 之后要发布的 …
阅读更多...
pytest基本应用

pytest基本应用

文章目录 1.pytest安装2.用例运行规则3.常用参数断言运行参数用例控制setup和teardownini配置文件 4.常用插件5.pytest高阶用法用例跳过参数化 6.pytest之Fixture使用fixture使用装饰器usefixtures 7.pytest之conftest.py8.conftestfixtureyieldyield介绍前后置使用 1.pytest安…
阅读更多...
2012及其以上系统修改服务器密码指南

2012及其以上系统修改服务器密码指南

修改服务器密码指南,目前介绍两种不同的方案 方法一 指令式 winR键 弹出运行框里输入 cmd 点击确认或者右下角开始程序里面的点开运行 2.在弹出框里手动输入以下一组文字&#xff1a;net user administrator 123456 框内无法粘贴 需要手动输入 其中administrator 是用…
阅读更多...
最新文章

Copyright @ 2022~2023