【基础知识】一文看懂深度优先算法和广度优先算法

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

概览

先上个图
【基础知识】一文看懂深度优先算法和广度优先算法

现在我们要访问图中的每个节点,即图的遍历。

图的遍历是指,从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中的所有顶点,使每个顶点仅被访问一次,这个过程称为图的遍历。
我们根据访问节点的顺序与方式(根据搜索方法),可以分为广度优先(BFS)和深度优先(DFS),这是图论中两种非常重要的算法,生产上广泛用于拓扑排序,寻路(走迷宫),搜索引擎,爬虫等。

我们分别来介绍

一、深度优先(DFS)

深度优先搜索(Depth-First-Search),简称 DFS。
我们以上图为例,现在需要访问每个节点,且只访问一次,可以看到,图分成了很多之路,

主要思路是从图中一个未访问的顶点 V (比如A)开始,沿着一条路一直走到底,深入到不能再深入为止(够深),然后从这条路尽头的节点回退到上一个节点, 如果上一个节点存在没有探索的分支,便继续探索若没有则继续回退,再从另一条路开始走到底…,不断递归重复此过程,直到所有的顶点都遍历完成,它的特点是不撞南墙不回头,先走完一条路,再换一条路继续走。

这就是暴力穷举,

1.1 图解过程

【基础知识】一文看懂深度优先算法和广度优先算法
1、我们从根节点 A 开始遍历,它相邻的节点有 B,E,先遍历节点 B,再遍历 B 的子节点 C
2、上图中一条路已经走到底了(C是叶子节点,再无可遍历的节点),此时就从 C 回退到上一个节点 B,看下节点 B 是否还有除 C 以外的节点,发现 B有 D节点,然后遍历D,
3、同理,上图中一条路已经走到底了(D是叶子节点,再无可遍历的节点),此时就从 D 回退到上一个节点 B,B的节点都遍历过了,然后在回到A, 同样的逻辑,再到,E、F

1.2 java 实现

package com.test;

import java.util.ArrayList;
import java.util.List;

public class DepthFirstSearch {

    // 定义图结构
    private List<Integer>[] graph;

    // 构造函数,初始化图结构
    public DepthFirstSearch(int numVertices) {
        graph = new ArrayList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    // 添加边
    public void addEdge(int v1, int v2) {
        graph[v1].add(v2);
    }

    // 深度优先搜索算法实现
    public void dfs(int start) {
        boolean[] visited = new boolean[graph.length]; // 标记每个顶点是否被访问过
        dfsHelper(start, visited); // 递归实现深度优先搜索算法
    }

    // 递归实现深度优先搜索算法
    private void dfsHelper(int vertex, boolean[] visited) {
        visited[vertex] = true; // 标记当前顶点已被访问过
        System.out.print(geta(vertex)); // 输出当前顶点编号
        for (int neighbor : graph[vertex]) { // 遍历当前顶点的邻居顶点
            if (!visited[neighbor]) { // 如果邻居顶点未被访问过,则递归访问它
                dfsHelper(neighbor, visited);
            }
        }
    }

    private String geta(int index){
        switch (index) {
            case 0:
                return "A";
            case 1:
                return "B";
            case 2:
                return "C";
            case 3:
                return "D";
            case 4:
                return "E";
            case 5:
                return "F";
        }
        return "";
    }

    // 测试代码
    public static void main(String[] args) {
        DepthFirstSearch graph = new DepthFirstSearch(6); // 创建图结构,包含6个顶点
        graph.addEdge(0, 1); // 添加边,
        graph.addEdge(0, 4); // 添加边,
        graph.addEdge(1, 2); // 添加边,
        graph.addEdge(1, 3); // 添加边,
        graph.addEdge(4, 5); // 添加边,
        System.out.print("深度优先搜索结果:"); // 输出深度优先搜索结果
        graph.dfs(0); // 从顶点0开始进行深度优先搜索
    }
}

在这个示例代码中,我们首先定义了一个DepthFirstSearch类,用于表示图结构。在构造函数中,我们初始化了图结构,并定义了一个addEdge方法,用于添加边。
然后,我们定义了一个dfs方法,用于执行深度优先搜索算法。在dfs方法中,我们首先创建了一个visited数组,用于标记每个顶点是否被访问过。然后,我们调用dfsHelper方法递归实现深度优先搜索算法。
在dfsHelper方法中,我们首先标记当前顶点已被访问过,并输出当前顶点编号。然后,我们遍历当前顶点的邻居顶点,如果邻居顶点未被访问过,则递归访问它。
最后,我们在测试代码中创建了一个包含6个顶点的图结构,并从顶点0开始进行深度优先搜索。运行测试代码后,输出深度优先搜索结果为:ABCDEF。

深度优先搜索结果:ABCDEF

二、广度优先(BFS)

广度优先遍历是首先把起点相邻的几个点探索完成,然后去探索距离起点稍远一些(隔一层)的点,然后再去玩探索距离起点更远一些(隔两层)的点… 是一层一层的向外探索。

遍历规则:
1)先访问完当前顶点的所有邻接点。(应该看得出广度的意思)
2)先访问顶点的邻接点先于后访问顶点的邻接点被访问。

2.1 图解过程

【基础知识】一文看懂深度优先算法和广度优先算法

2.2 java代码实现

import java.util.*;  
  
public class BFS {  
    // 定义图结构  
    private List<List<Integer>> graph;  
  
    // 构造函数,初始化图结构  
    public BFS(int numVertices) {  
        graph = new ArrayList<>();  
        for (int i = 0; i < numVertices; i++) {  
            graph.add(new ArrayList<>());  
        }  
    }  
  
    // 添加边  
    public void addEdge(int v1, int v2) {  
        graph.get(v1).add(v2);  
        graph.get(v2).add(v1);  
    }  
  
    // 广度优先搜索算法实现  
    public void bfs(int start) {  
        boolean[] visited = new boolean[graph.size()]; // 标记每个顶点是否被访问过  
        Queue<Integer> queue = new LinkedList<>(); // 创建队列,用于存储待访问的顶点  
        visited[start] = true; // 标记起始顶点已访问过  
        queue.offer(start); // 将起始顶点加入队列中  
        while (!queue.isEmpty()) { // 当队列非空时,继续遍历队列中的顶点  
            int vertex = queue.poll(); // 取出队列头部顶点  
            System.out.print(vertex + " "); // 输出当前顶点编号  
            for (int neighbor : graph.get(vertex)) { // 遍历当前顶点的邻居顶点  
                if (!visited[neighbor]) { // 如果邻居顶点未被访问过,则标记为已访问过,并加入队列中  
                    visited[neighbor] = true;  
                    queue.offer(neighbor);  
                }  
            }  
        }  
    }  
  
    // 测试代码  
    public static void main(String[] args) {  
        BFS graph = new BFS(6); // 创建图结构,包含6个顶点  
        graph.addEdge(0, 1); // 
        graph.addEdge(0, 4); // 
        graph.addEdge(1, 2); //   
        graph.addEdge(1, 3); // 
        graph.addEdge(4, 5); // 
        System.out.print("广度优先搜索结果:"); // 输出广度优先搜索结果  
        graph.bfs(0); // 从顶点0开始进行广度优先搜索  
    }  
}

在这个示例代码中,我们首先定义了一个BFS类,用于表示图结构。在构造函数中,我们初始化了图结构,并定义了一个addEdge方法,用于添加边。
然后,我们定义了一个bfs方法,用于执行广度优先搜索算法。在bfs方法中,我们首先创建了一个visited数组,用于标记每个顶点是否被访问过。
然后,我们创建了一个队列,用于存储待访问的顶点。我们将起始顶点加入队列中,并标记为已访问过。然后,我们开始遍历队列中的顶点。对于每个队列头部顶点,我们输出其编号,并遍历其邻居顶点。如果邻居顶点未被访问过,则将其标记为已访问过,并加入队列中。
最后,我们使用一个测试代码来测试我们的广度优先搜索算法实现。运行测试代码后,输出广度优先搜索结果为:0 1 2 3 4 5。

三、总结

3.1 深度优先遍历:

1、对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历(我们前面使用的是先序遍历)。
2、不全部保留结点,占用空间少;有回溯操作(即有入栈、出栈操作),运行速度慢。
3、一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索要快些

3.2 广度优先遍历:

1、又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止
2、保留全部结点,占用空间大; 无回溯操作(即无入栈、出栈操作),运行速度快。
3、一般需存储产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题文章来源地址https://www.toymoban.com/news/detail-488061.html

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

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

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

相关文章

  • 5、电子元器件基础知识大全,一文了解所有基本元器件

    一、电阻 电阻在电路中用“R”加数字表示,如:R15表示编号为15的电阻。电阻在电路中的 主要作用为分流、限流、分压、偏置、滤波(与电容器组合使用)和阻抗匹配等。 1.参数识别:电阻的单位为欧姆(Ω),倍率单位有:千欧(KΩ),兆欧(MΩ)等。换算方法是: 1兆欧=1000干欧=000000欧电

    2024年02月11日
    浏览(49)
  • 深度学习torch基础知识

    detach是截断反向传播的梯度流 将某个node变成不需要梯度的Varibale。因此当反向传播经过这个node时,梯度就不会从这个node往前面传播。 拼接:将多个维度参数相同的张量连接成一个张量 torch.nn.DataParallel(module, device_ids=None, output_device=None, dim=0) module即表示你定义的模型,devic

    2024年02月13日
    浏览(48)
  • 【一文详解】知识分享:(ASP.Net Core基础学习及快速入门)

    .Net .NET是微软的一个开发平台,这个平台的一大特点就是跨语言性,不管是什么语言,c、c++、c#、F#、J#、vb等语言都可以用这个平台合作开发; .NET,它是微软创建的一个用于构建多种不同类型的应用程序的开发人员平台。 .NET 是一个广泛的术语,用于描述整个 Microsoft 的软件

    2024年02月01日
    浏览(68)
  • 深度学习基础知识神经网络

    1. 感知机 感知机(Perceptron)是 Frank Rosenblatt 在1957年提出的概念,其结构与MP模型类似,一般被视为最简单的人工神经网络,也作为二元线性分类器被广泛使用。通常情况下指单层的人工神经网络,以区别于多层感知机(Multilayer Perceptron)。尽管感知机结构简单,但能够学习

    2024年02月03日
    浏览(53)
  • 深度学习基础知识(三)-线性代数的实现

    1.标量使用 标量由只有一个元素的张量表示,标量可以做最简单的计算。 结果: 2.向量使用 向量:将标量值组成的列表就是向量 结果: 访问张量的长度 只有一个轴的张量,形状只有一个元素 创建一个二维矩阵5行4列,然后将矩阵做转置,轴对称的一个转置 结果:其实就是把

    2024年02月10日
    浏览(60)
  • 深度学习基础知识-pytorch数据基本操作

    1.1.1 数据结构 机器学习和神经网络的主要数据结构,例如                 0维:叫标量,代表一个类别,如1.0                 1维:代表一个特征向量。如  [1.0,2,7,3.4]                 2维:就是矩阵,一个样本-特征矩阵,如: [[1.0,2,7,3.4 ]                   

    2024年02月11日
    浏览(49)
  • 深度学习基础知识-感知机+神经网络的学习

    参考书籍:(找不到资源可以后台私信我) 《深度学习入门:基于Python的理论与实现 (斋藤康毅)》 《Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow, 2nd Edition (Aurelien Geron [Géron, Aurélien])》 机器学习和深度学习的区别: Perceptron(感知机) 感知机就是一种接收多种输入信

    2023年04月26日
    浏览(61)
  • 【知识存储】用于深度学习研究的 ☆ 概率论和数理统计☆ 基础理论知识,用时查阅,灵活运用,很基础很重要

    随机事件和概率 1.事件的关系与运算 (1) 子事件: A ⊂ B A subset B A ⊂ B ,若 A A A 发生,则 B B B 发生。 (2) 相等事件: A = B A = B A = B ,即 A ⊂ B A subset B A ⊂ B ,且 B ⊂ A B subset A B ⊂ A 。 (3) 和事件: A ⋃ B Abigcup B A ⋃ B (或 A + B A + B A + B ), A A A 与 B B B 中至少有一个发生

    2024年02月16日
    浏览(63)
  • 现代C++中的从头开始深度学习【1/8】:基础知识

            提及机器学习框架与研究和工业的相关性。现在很少有项目不使用Google TensorFlow或Meta PyTorch,在于它们的可扩展性和灵活性。 也就是说,花时间从头开始编码机器学习算法似乎违反直觉,即没有任何基本框架。然而,事实并非如此。自己对算法进行编码可以清晰而

    2024年02月13日
    浏览(44)
  • 计算机视觉基础知识(十二)--神经网络与深度学习

    一种机器学习的算法 一般有输入层--隐藏层--输出层 隐藏层数量多于两个的称为深度神经网络; 输入的是特征向量; 特征向量代表的是变化的方向; 或者说是最能代表这个事物的特征方向; 权重是特征值,有正有负,加强或抑制; 权重的绝对值大小,代表输入信号对神经元的影响大小

    2024年02月21日
    浏览(59)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包