精华内容
下载资源
问答
  • 图的深度优先遍历(DFS)和广度优先遍历(BFS)算法分析

    千次阅读 多人点赞 2020-07-31 10:31:21
    遍历深度优先遍历无向图的深度优先遍历图解有向图的深度优先遍历图解广度优先遍历无向图的广度优先遍历图解有向图的广度优先遍历图解 图的遍历,所谓遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些...


    图的遍历,所谓遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略:

    • 深度优先遍历

    • 广度优先遍历

    深度优先遍历

    深度优先遍历(Depth First Search)的主要思想是:

    1. 首先以一个未被访问过的顶点作为起始顶点,沿当前顶点的边走到未访问过的顶点;
    2. 当没有未访问过的顶点时,则回到上一个顶点,继续试探别的顶点,直至所有的顶点都被访问过。

    在此可以用一句话来形容 “不到南墙不回头”。

    无向图的深度优先遍历图解

    以下"无向图"为例:

    在这里插入图片描述

    对上无向图进行深度优先遍历,从A开始:

    • 第1步:访问A。

    • 第2步:访问B(A的邻接点)。 在第1步访问A之后,接下来应该访问的是A的邻接点,即"B,D,F"中的一个。但在本文的实现中,顶点ABCDEFGH是按照顺序存储,B在"D和F"的前面,因此,先访问B。

    • 第3步:访问G(B的邻接点)。 和B相连只有"G"(A已经访问过了)

    • 第4步:访问E(G的邻接点)。 在第3步访问了B的邻接点G之后,接下来应该访问G的邻接点,即"E和H"中一个(B已经被访问过,就不算在内)。而由于E在H之前,先访问E。

    • 第5步:访问C(E的邻接点)。 和E相连只有"C"(G已经访问过了)。

    • 第6步:访问D(C的邻接点)。

    • 第7步:访问H。因为D没有未被访问的邻接点;因此,一直回溯到访问G的另一个邻接点H。

    • 第8步:访问(H的邻接点)F。

    因此访问顺序是:A -> B -> G -> E -> C -> D -> H -> F

    有向图的深度优先遍历图解

    在这里插入图片描述

    对上有向图进行深度优先遍历,从A开始:

    • 第1步:访问A。

    • 第2步:访问(A的出度对应的字母)B。 在第1步访问A之后,接下来应该访问的是A的出度对应字母,即"B,C,F"中的一个。但在本文的实现中,顶点ABCDEFGH是按照顺序存储,B在"C和F"的前面,因此,先访问B。

    • 第3步:访问(B的出度对应的字母)F。 B的出度对应字母只有F。

    • 第4步:访问H(F的出度对应的字母)。 F的出度对应字母只有H。

    • 第5步:访问(H的出度对应的字母)G。H的出度对应字母只有G。

    • 第6步:访问(G的出度对应字母)C。 在第5步访问G之后,接下来应该访问的是G的出度对应字母,即"B,C,E"中的一个。但在本文的实现中,顶点B已经访问了,由于C在E前面,所以先访问C。

    • 第7步:访问(C的出度对应的字母)D。访问C之后,接下来应该访问的是C的出度对应字母,即"B,D"中的一个。但在本文的实现中,顶点B已经访问了,所以访问D。

    • 第8步:访问E。D无出度,所以一直回溯到G对应的另一个出度E。

    因此访问顺序是:A -> B -> F -> H -> G -> C -> D -> E

    广度优先遍历

    广度优先遍历(Depth First Search)的主要思想是:类似于树的层序遍历。

    无向图的广度优先遍历图解

    在这里插入图片描述

    从A开始,有4个邻接点,“B,C,D,F”,这是第二层;

    在这里插入图片描述

    在分别从B,C,D,F开始找他们的邻接点,为第三层。以此类推。

    因此访问顺序是:A -> B -> C -> D -> F -> G -> E -> H

    有向图的广度优先遍历图解

    在这里插入图片描述

    与无向图类似 。可以参考。

    在这里插入图片描述

    因此访问顺序是:A -> B -> C -> F -> D -> H -> G -> E

    习题

    1. 下列哪一种图的邻接矩阵是对称矩阵()。

    A.有向网

    B.无向网

    C.AOV网

    D.AOE网

    正确答案:B

    答案解析:

    无向图是没有方向的,所以它的邻接矩阵是对称的。无向图的邻接矩阵存储中,每条表存储两次,且A[i][j]A[j][i]。

    扩展资料:

    AOV网(baiActivity On Vertex Network)是指在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网。AOV网中的弧表示活动之间的某种约束关系。AOV网中不存在回路(即无环的有向图)。

    AOE网(Activity On Edge Network)是指在一个表示工程的带权有向图中,用顶点表示事件,用弧表示活动,用弧上的权值表示活动持续的时间,这种有向图的弧表示活动的网。AOE网中没有入度的顶点称为始点或源点,没有出度的顶点叫做终点或汇点。

    在这里插入图片描述

    AOV网和AOE网虽然都是用来对工程建模的,但它们还是有很大的区别,主要体现在AOV网是顶点表示活动的网,它只描述了活动之间的约束关系,而AOE网是用有向边表示活动,边上的权值表示活动持续的时间。

    AOE网是建立在AOV网基础之上(活动之间约束关系没有矛盾),再来分析完成整个工程至少需要多少时间,或者为缩短完成工程所需时间,应当加快那些活动等问题。

    1. 要连通具有 n 个顶点的有向图,最少需要()条边。

    A. n+l
    B. n-l
    C. 2n
    D. n

    正确答案:D

    答案解析:

    有向图的话,连通=所有节点成环,不然怎么走的通。

    • 连通n个结点的有向图,至少需要n条边。
    • 连通n个结点的无向图,至少需要n-1条边。

    如有不同见解,欢迎留言讨论~~

    展开全文
  • } 本文的重头戏来了,最麻烦的DFS & BFS 三、深度优先算法 四、广度优先算法 广度遍历类似于层级遍历 , 需要将当前结点的全部邻接结点都遍历完, 才能开始下一层遍历 我们在搭建邻接矩阵的时候, 将两个连通的顶点间的...


    前言

    千呼万唤始出来,终于开始学图喽 , 虽然学校的课程早结课了(水完了) , 话不多说,开始整活,本文用地是无向图


    提示:以下是本篇文章正文内容,下面案例可供参考

    一、图的基本概念

    下面讲几个常用的概念,

    1.图的定义

    图(graph) ,是由两个集合组成的 ,其一为顶点集, 其二为边集 ,其中顶点集不允许为空 ,边集可为空, 也就是说,只有一个顶点没有边的图也可以叫做图

    2.基本术语

    1. 度,出/入度: 顶点的度是指与该顶点相关联的边的个数,对于有向图,度还细分
    	为入度和出度, 其度=入度+出度, 一般地, 度数 / 2 = 边数
    2. 路径和路径长度: 路径指的是从顶点到顶点的弧或直线, 而路径长度是指从
    	某一顶点出发到另一顶点所经过的路径的条数
    3.连通: 有路径即为连通,如果图中任意两个顶点间都有路径连接,就是连通图,
    	而连通分量指的是图中包含的最大连通子图
    4.生成树: 树中包含了图的所有顶点,和n-1条边(也就是说生成树就是缺了一条边
    	,使其无法连通的图)
    

    二、图的基本算法

    讲图的算法前, 得先讲讲构建一张图需要哪些属性

    我们都知道图是由边和顶点构成的,因此在构造数据结构的时候,需要一个二维数组存放边的两个顶点 (邻接矩阵) , 需要一个一维数组存放顶点, 一个布尔数组用于标记各个顶点是否已被遍历, 一个整型变量表示边的数量

    1.初始化图

    最方便的方式就是通过构造函数来初始化一个图, 在初始化时, 顶点个数是必须要作为参数传入的,因为一张图可以没有边,但是必须要有顶点

    代码如下(示例):

    	//传入顶点个数numOdVertex
        public Graph(Integer numOdVertex) {
            this.vertexs = new ArrayList<>();
            this.edges = new int[numOdVertex][numOdVertex]; //矩阵的大小等于顶点个数的平方
            this.numOdEdges = 0; //边数默认为0
            this.isVisited = new boolean[numOdVertex];
        }
    

    2.插入顶点和边

    在对图完成初始化之后, 还要对图的点边关系进行构造 , 也就是插入顶点和边的操作.

    在添加顶点的时候, 我们只需要简单地向顶点数组中加入元素即可, 因为这个顶点可以没有连接边

    在添加边的时候, 我们需要按顶点的索引对边进行赋权值操作 , 由于是无向图, 两端顶点索引对应的值要双面赋值(这点详见下面代码)

    代码如下(示例):

    	//添加边 ,三个要素,边的两个顶点(邻接矩阵的两个元素中的索引,无向图添加是双向的)
        public void insertEdge(Integer vertex01,Integer vertex02,int weight) {
            this.edges[vertex01][vertex02] = weight; //双面赋值
            this.edges[vertex02][vertex01] = weight;
            //边数++
            this.numOdEdges++;
        }
    

    3.矩阵打印

    这里有一个小技巧 ,也是第一次碰到的, 对于一个二维数组 , 我们可以将其看作是一个一维数组, 那么其中的元素其实就是一个个的一维数组, 对于一维数组, 我们完全可以通过Arrays工具类直接输出它 ,这里能上一层for循环, 代码优雅很多

    	//打印图(邻接矩阵)
        public void showGraph(){
            for (int[] row:
                 this.edges) {
                System.out.println(Arrays.toString(row));
            }
        }
    

    4.返回第一个邻接结点的下标

    可以参见下文广度优先算法的那张矩阵图 , 我们将矩阵按行分为了5组 , 那么每组代表一个结点, 纵向的每一列可以视为该结点的邻接点 , 那么就拿下图来说, A点只与E点有连接, 因此值为1 ,其余为0

    因此在遍历的过程中 , 结点个数将作为循环的上限

    //返回第一个临接结点的下标
       public Integer getFirstAdjust(int index){ //传入当前当前结点的下标
           for(int i = 0 ; i < this.vertexs.size() ; i++){
               if(this.edges[index][i] > 0){ //找到了第一个临接结点
                   return i;
               }
           }
           return -1;
       }
    

    5.返回第一个邻接结点的下一个结点的下标

    既然要求出下一个结点的下标 , 那么我们就需要两个参数 ,一个是当前结点的下标,一个是与当前结点邻接的结点的下标, 这个函数非常重要,在下面会着重介绍它的作用,这里先给出代码

    //返回第一个临接结点的下一个结点的下标
        public Integer getNextAdjust(int index01,int index02){
            for(int i = index02+1 ; i < this.vertexs.size() ; i++){
                if(edges[index01][i] > 0){
                    return i;
                }
            }
            return -1;
        }
    

    本文的重头戏来了,最麻烦的DFS & BFS

    三、深度优先算法

    四、广度优先算法

    广度遍历类似于层级遍历 , 需要将当前结点的全部邻接结点都遍历完, 才能开始下一层遍历

    我们在搭建邻接矩阵的时候, 将两个连通的顶点间的权值设为了1 ,不连通的顶点权值设为0,这样在进行广度优先遍历的时候,当遇到矩阵中值为1的位置时, 说明它和所在行所代表的顶点是连通的

    在遍历过程中还需一个LinkedList作为辅助, 其原因也是在于这是广度遍历, 我们需要存下结点的邻接结点的下标, 在找到邻接结点的下标以后, 就要在邻接矩阵中,通过该下标找到该邻接结点的所在行,再对该行进行遍历,找出新的,还没被遍历过的结点 ,以此类推

    在这里插入图片描述
    就上图而言, 我们的第一个结点是A ,于是从第一行开始遍历, B,C,D都与A无连接 , 只有E有, 通过getFirstAdjust方法获取第一个临接结点的下标, 跳转到最后一行E行 , 从第一列开始遍历, 找到了C,再以此类推 ,与A点相邻的所有结点都被遍历完了 , 再开始下一个结点的广度优先遍历

    ,最后得出的广度优先遍历顺序为AECBD ,与深度遍历同

    	public void bfs(){
            for(int i = 0 ; i < this.getNumOfVertex() ; i++){
                if(!isVisited[i]){
                    bfs(i,isVisited);
                }
            }
        }
    
        private void bfs(int index,boolean[]isVisited) {
            int head; //队列头结点对应的下标
            int next; //临接结点对应的下标
            LinkedList queue = new LinkedList();
            System.out.println(this.getValueByIndex(index) + "=>");
            isVisited[index] = true;
            queue.addLast(index);
            while(!queue.isEmpty()){ //队列不为空
                head = (Integer)queue.removeFirst();
                next = this.getFirstAdjust(head);
                while(next != -1){
                    if(!isVisited[next]){ //临接结点存在且没被访问过
                        //输出并标记为已访问
                        System.out.println(this.getValueByIndex(next));
                        isVisited[next] = true;
                        //入队
                        queue.addLast(next);
                    }
                    next = this.getNextAdjust(head,next);
                    //this.dfs(head,isVisited);
                }
            }
        }
    

    该处使用的url网络请求的数据。


    总结

    这两个算法确实非常的难理解,
    今天先写这么多.

    展开全文
  • 考虑通过递归对二叉树进行后序遍历,当遇到节点 p 或 q 时返回。从底至顶回溯,当节点 p, q在节点 root的异侧时,节点 root即为最近公共祖先,则向上返回 root。 递归解析 1.终止条件: 当越过叶节点,则直接返回 ...

    题目地址:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

    题目

    在这里插入图片描述

    分析:

    祖先的定义: 若节点 p 在节点 root 的左(右)子树中,或 p = roott ,则称 root是 p的祖先。
    在这里插入图片描述
    最近公共祖先的定义: 设节点 root 为节点 p, q 的某公共祖先,若其左子节点 root.left 和右子节点 root.right都不是 p,q的公共祖先,则称 root 是 “最近的公共祖先” 。

    根据以上定义,若 root是 p, q 的 最近公共祖先 ,则只可能为以下情况之 一:

    1. p 和 q 在 root 的子树中,且分列 root 的 异侧(即分别在左、右子树中);
    2. p = root ,且 q 在 root的左或右子树中;
    3. q = root ,且 p 在 root的左或右子树中;
      在这里插入图片描述
      考虑通过递归对二叉树进行后序遍历,当遇到节点 pq 时返回。从底至顶回溯,当节点 p, q在节点 root的异侧时,节点 root即为最近公共祖先,则向上返回 root

    递归解析

    1.终止条件:

    当越过叶节点,则直接返回 null ;
    当 root等于 p, q,则直接返回 root ;

    2.递推工作:

    开启递归左子节点,返回值记为 left ;
    开启递归右子节点,返回值记为 right ;

    3.返回值: 根据 left 和 right,可展开为四种情况;

    当 left 和 right 同时为空 :说明 root的左 / 右子树中都不包含 p,q ,返回 null;
    当 left和 right 同时不为空 :说明 p, q分列在 root的 异侧 (分别在 左 / 右子树),因此 root为最近公共祖先,返回 root ;
    当 left为空 ,right 不为空 :p,q 都不在 root 的左子树中,直接返回 right。具体可分为两种情况:
    p,q 其中一个在 root的 右子树 中,此时 right 指向 pp(假设为 pp ); p,q两节点都在 root的 右子树 中,此时的 right 指向 最近公共祖先节点 ;

    4.当 left 不为空 , right为空 :与情况 3. 同理;

    观察发现, 情况 1. 可合并至 3. 和 4. 内,详见文章末尾代码。

    代码:

    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || root == p || root == q) return root;
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if(left == null) return right;
            if(right == null) return left;
            return root;
        }
    }
    

    情况 1. , 2. , 3. , 4. 的展开写法如下。

    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || root == p || root == q) return root;
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if(left == null && right == null) return null; // 1.
            if(left == null) return right; // 3.
            if(right == null) return left; // 4.
            return root; // 2. if(left != null and right != null)
        }
    }
    
    
    展开全文
  • 顾名思义,这种遍历方法是以深度为优先进行对图的搜索或者遍历,至于什么是以深度为优先条件,先看下面DFS的基本步骤: ( 这是一个递归思想的DFSDFS:从当前节点开始,先标记当前节点,再寻找与当前节点相邻,且...

    DFS (Deep First Search)

    概念:
    顾名思义,这种遍历方法是以深度为优先进行对图的搜索或者遍历,至于什么是以深度为优先条件,先看下面DFS的基本步骤:

    ( 这是一个递归思想的DFS)

    DFS:从当前节点开始,先标记当前节点,再寻找与当前节点相邻,且未标记过的节点:

    (1): 当前节点不存在下一个节点,则返回前一个节点进行DFS

    (2): 当前节点存在下一个节点,则从下一个节点进行DFS

    下面是图解:

    一开始,可以看出,若没有走到死路,这种遍历方式会从start节点沿着一条路一直深入下去(start -> 1 -> 2 -> 3。
    在这里插入图片描述

    若走到死路,便会退回上一节点,遍历上一节点的其他相邻节点(2 -> 4)。
    在这里插入图片描述
    这样一直重复,直到找到终点。
    在这里插入图片描述
    DFS的伪代码:

     find(节点){
    
                if(此结点已经遍历 || 此节点在图外 || 节点不满足要求) return;
     
                if(找到了end节点) 输出结果 ; return;
     
                标记此节点,表示已经遍历过了;
     
                while(存在下一个相邻节点) find(下一个节点);
     
            }
    

    BFS (Breadth First Search)

    概念:
    对于深度优先算法,强迫症就很不爽了,并表示:“为什么不干干净净,一层一层地从start节点搜索下去呢,就像病毒感染一样,这样才像正常的搜索的样子嘛。”于是便有了BFS算法(误)。广度优先算法便如其名字,它是以广度为优先的,一层一层搜索下去的,就像病毒感染,扩散性的传播下去。

    图解:

    下图中,start为搜索的初始节点,end为目标节点
    在这里插入图片描述
    我们先把star节点的关联节点遍历一次
    在这里插入图片描述
    接下来把第一步遍历过的节点当成start,重复第一步
    在这里插入图片描述
    重复一二步,这样便是一个放射样式的搜哦防范,直到找到end节点
    在这里插入图片描述
    可以看出,这样放射性的寻找方式,能找到从start到end的最近路(因为每次只走一步,且把所有的可能都走了,谁先到end说明这就是最短路)。怎么实现呢?

    这里需要用到队列:
    
    a. 比如每遍历start周围的一个“1”节点的时候,就把跟它相关联的“2”节点保存到队列中(“1”节点访问完之后队列内容:2,2,2,2)
    
    b. 然后依次访问队列内容,并对每个队列元素重复a步骤(访问一个“2”节点之后队列的内容:2,2,2,3,3)。
    
    c. 由此重复下去,直到队列为空或者搜索到终点。
    

    广度优先的[递归]伪代码:
    把start节点push入队列;

        while(队列不为空) {
    
            把队列首节点pop出队列;
    
            对节点进行相关处理或者判断;
    
            while(此节点有下一个相关节点){
    
                把相关节点push入对列;
    
            }
    
        }
    
    展开全文
  • 目录一、什么是图的遍历二、深度优先遍历DFS)的基本思想三、深度优先遍历DFS)的步骤详解及案例图解四、深度优先遍历DFS)的代码实现 一、什么是图的遍历 图的遍历,指的是从图中的任一顶点出发,对图中的...
  • 一、深度优先搜索(DFS,Depth First Search) 深度优先搜索的主要思想:首先从一个未走过的顶点作为起始...DFS遍历图解过程如下: 1、DFS邻接矩阵核心代码实现(可以链表实现,以下是数组实现): bool boo...
  • 1.思路图解兼样例:接下来将用此图例作为测试用例 2.输出结果: (1)邻接矩阵: (2)邻接表: 一、邻接矩阵 import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; public ...
  • 目录 定义 邻接表存储图 深度优先遍历 广度优先遍历: BFS部分 完整代码 定义 要实现该算法首先要知道邻接表的概念。...其图解如下: firstedge指向边表第一个结点。 边表的adjvex的值代表与V0顶...
  • // 打印中序遍历 void dfs(Node* root) { if(root == nullptr) return; dfs(root->left); // 左 cout <...
  • BFS算法和DFS算法(含图解:简单易懂)

    千次阅读 多人点赞 2020-08-30 13:54:17
    图解BFS算法和DFS算法BFS算法算法思路实现过程Python代码实现DFS算法算法思路实现过程Python代码实现 BFS算法 BFS类似于树的层次遍历过程,从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法...
  • dfs遍历使用递归: void dfs(TreeNode root) { if (root == null) { return; } dfs(root.left); dfs(root.right); } BFS遍历使用队列数据结构: void bfs (TreeNode root) { Queue<TreeNode> queue = ...
  • 图解DFS&BFS 对比: DFS 算法 思想: 一直往深处走,直到找到解或者走不下去为止;通常用递归或者栈(保存未被遍历的结点,结点按照深度优先的次序被访问并依次被压入栈中)来实现;反复进行直到所有节点都被...
  • 深度优先搜索: 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归,先朝一个方向搜到底,再回溯至上个节点,沿另一个方向搜索,以此类推。 剪枝: 在搜索中,遇到这条路不可能和目标字符串匹配成功 的情况...
  • 深度遍历算法原理及图解 深度遍历算法例题应用 1:全排列问题 2:ABC+DEF=GHI问题 3:二维数组寻找点到点的最短路径 4:求岛屿的面积 5:求岛屿的个数 6:地板的埔法有多少种 7:二叉树的深度遍历 8:图的深度遍历 9...
  • 文章目录深度优先遍历的理解实现遍历的过程图解非递归实现遍历递归方法实现遍历完整过程 深度优先遍历的理解 深度优先搜索(Depth First Search),简称DFS,这种方法类似于二叉树的前序遍历。 假设 初始状态时...
  • DFS 由某一个顶点出发,一直往下一个未被访问的邻接点遍历,以该顶点为新的邻接点,重复此步骤直至未没有没被访问的邻接点为止。 再返回上一个访问过的邻接点,访问下一个未被访问的邻接点 重复以上步骤到结束 递归...
  • 树的dfs序(待填)

    2020-07-13 21:41:50
    树的dfs序定义图解 定义 每个节点在dfs深度优先遍历中的进出栈的时间序列 图解
  • 解题思路: 参考了『手画图解』剖析DFS、BFS解法 | 二叉树的序列化与反序列化。 该题实际上并没有严格的要求将二叉树序列化为[1,2,3,null,null,4,5]的形式,只要...使用DFS遍历每个节点。 如果遇到节点为空,则返回X

空空如也

空空如也

1 2 3
收藏数 56
精华内容 22
关键字:

dfs遍历图解