精华内容
下载资源
问答
  • 深度优先遍历和广度优先遍历

    万次阅读 多人点赞 2019-05-29 21:24:38
    深度优先遍历和广度优先遍历 什么是 深度/广度 优先遍历? 深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。 这两...

    深度优先遍历和广度优先遍历
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    什么是 深度/广度 优先遍历?

    深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。

    这两种遍历方式有什么不同呢?我们来举个栗子:

    我们来到一个游乐场,游乐场里有11个景点。我们从景点0开始,要玩遍游乐场的所有景点,可以有什么样的游玩次序呢?

    在这里插入图片描述
    第一种是一头扎到底的玩法。我们选择一条支路,尽可能不断地深入,如果遇到死路就往回退,回退过程中如果遇到没探索过的支路,就进入该支路继续深入。

    在图中,我们首先选择景点1的这条路,继续深入到景点7、景点8,终于发现走不动了(景点旁边的数字代表探索次序):
    在这里插入图片描述
    于是,我们退回到景点7,然后探索景点10,又走到了死胡同。于是,退回到景点1,探索景点9:
    在这里插入图片描述
    按照这个思路,我们再退回到景点0,后续依次探索景点2、3、5、4、6,终于玩遍了整个游乐场:
    在这里插入图片描述
    像这样先深入探索,走到头再回退寻找其他出路的遍历方式,就叫做深度优先遍历(DFS)。
    在这里插入图片描述
    在这里插入图片描述
    除了像深度优先遍历这样一头扎到底的玩法以外,我们还有另一种玩法:首先把起点相邻的几个景点玩遍,然后去玩距离起点稍远一些(隔一层)的景点,然后再去玩距离起点更远一些(隔两层)的景点…

    在图中,我们首先探索景点0的相邻景点1、2、3、4:
    在这里插入图片描述
    接着,我们探索与景点0相隔一层的景点7、9、5、6:
    在这里插入图片描述
    最后,我们探索与景点0相隔两层的景点8、10:
    在这里插入图片描述
    像这样一层一层由内而外的遍历方式,就叫做广度优先遍历(BFS)。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    深度优先遍历

    首先说说深度优先遍历的实现过程。这里所说的回溯是什么意思呢?回溯顾名思义,就是自后向前,追溯曾经走过的路径。

    我们把刚才游乐场的例子抽象成数据结构的图,假如我们依次访问了顶点0、1、7、8,发现无路可走了,这时候我们要从顶点8退回到顶点7。

    在这里插入图片描述
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190529211147549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyMjE3MDE4MTAz,size_16,color_FFFFFF,t_70

    而后我们探索了顶点10,又无路可走了,这时候我们要从顶点10退回到顶点7,再退回到顶点1。
    在这里插入图片描述
    像这样的自后向前追溯曾经访问过的路径,就叫做回溯。

    要想实现回溯,可以利用栈的先入后出特性,也可以采用递归的方式(因为递归本身就是基于方法调用栈来实现)。

    下面我们来演示一下具体实现过程。

    首先访问顶点0、1、7、8,这四个顶点依次入栈,此时顶点8是栈顶:
    在这里插入图片描述
    从顶点8退回到顶点7,顶点8出栈:
    在这里插入图片描述
    接下来访问顶点10,顶点10入栈:
    在这里插入图片描述
    从顶点10退到顶点7,从顶点7退到顶点1,顶点10和顶点7出栈:
    在这里插入图片描述
    探索顶点9,顶点9入栈:
    在这里插入图片描述
    以此类推,利用这样一个临时栈来实现回溯,最终遍历完所有顶点。

    广度优先遍历

    接下来该说说广度优先遍历的实现过程了。刚才所说的重放是什么意思呢?似乎听起来和回溯差不多?其实,回溯与重放是完全相反的过程。

    仍然以刚才的图为例,按照广度优先遍历的思想,我们首先遍历顶点0,然后遍历了邻近顶点1、2、3、4:

    在这里插入图片描述
    接下来我们要遍历更外围的顶点,可是如何找到这些更外围的顶点呢?我们需要把刚才遍历过的顶点1、2、3、4按顺序重新回顾一遍,从顶点1发现邻近的顶点7、9;从顶点3发现邻近的顶点5、6。
    在这里插入图片描述
    像这样把遍历过的顶点按照之前的遍历顺序重新回顾,就叫做重放。同样的,要实现重放也需要额外的存储空间,可以利用队列的先入先出特性来实现。

    下面我们来演示一下具体实现过程。
    首先遍历起点顶点0,顶点0入队:
    在这里插入图片描述
    接下来顶点0出队,遍历顶点0的邻近顶点1、2、3、4,并且把它们入队:
    在这里插入图片描述
    然后顶点1出队,遍历顶点1的邻近顶点7、9,并且把它们入队:
    在这里插入图片描述
    然后顶点2出队,没有新的顶点可入队:
    在这里插入图片描述
    以此类推,利用这样一个队列来实现重放,最终遍历完所有顶点。

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    /**

    图的顶点
    
    / private static class Vertex { int data; Vertex(int data) {    this.data = data; } } /*
    
    图(邻接表形式)
    
    / private static class Graph { private int size; private Vertex[] vertexes; private LinkedList adj[]; Graph(int size){    this.size = size;    //初始化顶点和邻接矩阵    vertexes = new Vertex[size];    adj = new LinkedList[size];    for(int i=0; i*
    
    深度优先遍历
    
    / public static void dfs(Graph graph, int start, boolean[] visited) { System.out.println(graph.vertexes[start].data); visited[start] = true; for(int index : graph.adj[start]){    if(!visited[index]){        dfs(graph, index, visited);    } } } /*
    
    广度优先遍历
    
    */
    
    public static void bfs(Graph graph, int start, boolean[] visited, LinkedList queue) {
    
    queue.offer(start);
    
    while (!queue.isEmpty()){
    
       int front = queue.poll();
    
       if(visited[front]){
    
           continue;
    
       }
    
       System.out.println(graph.vertexes[front].data);
    
       visited[front] = true;
    
       for(int index : graph.adj[front]){
    
           queue.offer(index);;
    
       }
    
    }
    
    }
    
    public static void main(String[] args) {
    
    Graph graph = new Graph(6);
    
    graph.adj[0].add(1);
    
    graph.adj[0].add(2);
    
    graph.adj[0].add(3);
    
    graph.adj[1].add(0);
    
    graph.adj[1].add(3);
    
    graph.adj[1].add(4);
    
    graph.adj[2].add(0);
    
    graph.adj[3].add(0);
    
    graph.adj[3].add(1);
    
    graph.adj[3].add(4);
    
    graph.adj[3].add(5);
    
    graph.adj[4].add(1);
    
    graph.adj[4].add(3);
    
    graph.adj[4].add(5);
    
    graph.adj[5].add(3);
    
    graph.adj[5].add(4);
    
    System.out.println("图的深度优先遍历:");
    
    dfs(graph, 0, new boolean[graph.size]);
    
    System.out.println("图的广度优先遍历:");
    
    bfs(graph, 0, new boolean[graph.size], new LinkedList());
    
    }
    

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 主要介绍了JavaScript树的深度优先遍历和广度优先遍历算法,结合实例形式分析了JavaScript树的深度优先遍历、广度优先遍历递归与非递归相关实现技巧,需要的朋友可以参考下
  • 主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考下
  • 深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。 这两种遍历方式有什么不同呢?我们来举个栗子: 我们来到一个游乐场,游乐场里有...

    ————— 第二天 —————

    什么是 深度/广度 优先遍历?

    深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。

    这两种遍历方式有什么不同呢?我们来举个栗子:

    我们来到一个游乐场,游乐场里有11个景点。我们从景点0开始,要玩遍游乐场的所有景点,可以有什么样的游玩次序呢?

    第一种是一头扎到底的玩法。我们选择一条支路,尽可能不断地深入,如果遇到死路就往回退,回退过程中如果遇到没探索过的支路,就进入该支路继续深入。

    在图中,我们首先选择景点1的这条路,继续深入到景点7、景点8,终于发现走不动了(景点旁边的数字代表探索次序):

    于是,我们退回到景点7,然后探索景点10,又走到了死胡同。于是,退回到景点1,探索景点9:

    按照这个思路,我们再退回到景点0,后续依次探索景点2、3、5、4、6,终于玩遍了整个游乐场:

    像这样先深入探索,走到头再回退寻找其他出路的遍历方式,就叫做深度优先遍历(DFS)。

    除了像深度优先遍历这样一头扎到底的玩法以外,我们还有另一种玩法:首先把起点相邻的几个景点玩遍,然后去玩距离起点稍远一些(隔一层)的景点,然后再去玩距离起点更远一些(隔两层)的景点......

    在图中,我们首先探索景点0的相邻景点1、2、3、4:

    接着,我们探索与景点0相隔一层的景点7、9、5、6:

    最后,我们探索与景点0相隔两层的景点8、10:

    像这样一层一层由内而外的遍历方式,就叫做广度优先遍历(BFS)。

    深度/广度优先遍历 的实现

    深度优先遍历

    首先说说深度优先遍历的实现过程。这里所说的回溯是什么意思呢?回溯顾名思义,就是自后向前,追溯曾经走过的路径。

    我们把刚才游乐场的例子抽象成数据结构的图,假如我们依次访问了顶点0、1、7、8,发现无路可走了,这时候我们要从顶点8退回到顶点7。

    而后我们探索了顶点10,又无路可走了,这时候我们要从顶点10退回到顶点7,再退回到顶点1。

    像这样的自后向前追溯曾经访问过的路径,就叫做回溯。

    要想实现回溯,可以利用栈的先入后出特性,也可以采用递归的方式(因为递归本身就是基于方法调用栈来实现)。

    下面我们来演示一下具体实现过程。

    首先访问顶点0、1、7、8,这四个顶点依次入栈,此时顶点8是栈顶:

    从顶点8退回到顶点7,顶点8出栈:
    接下来访问顶点10,顶点10入栈:

    从顶点10退到顶点7,从顶点7退到顶点1,顶点10和顶点7出栈:

    探索顶点9,顶点9入栈:

    以此类推,利用这样一个临时栈来实现回溯,最终遍历完所有顶点。

    广度优先遍历

    接下来该说说广度优先遍历的实现过程了。刚才所说的重放是什么意思呢?似乎听起来和回溯差不多?其实,回溯与重放是完全相反的过程。

    仍然以刚才的图为例,按照广度优先遍历的思想,我们首先遍历顶点0,然后遍历了邻近顶点1、2、3、4:

    接下来我们要遍历更外围的顶点,可是如何找到这些更外围的顶点呢?我们需要把刚才遍历过的顶点1、2、3、4按顺序重新回顾一遍,从顶点1发现邻近的顶点7、9;从顶点3发现邻近的顶点5、6。

    像这样把遍历过的顶点按照之前的遍历顺序重新回顾,就叫做重放。同样的,要实现重放也需要额外的存储空间,可以利用队列的先入先出特性来实现。

    下面我们来演示一下具体实现过程。

    首先遍历起点顶点0,顶点0入队:

    接下来顶点0出队,遍历顶点0的邻近顶点1、2、3、4,并且把它们入队:

    然后顶点1出队,遍历顶点1的邻近顶点7、9,并且把它们入队:

    然后顶点2出队,没有新的顶点可入队:

    以此类推,利用这样一个队列来实现重放,最终遍历完所有顶点。

    
    /**
     * 图的顶点
     */
    private static class Vertex {
        int data;
        Vertex(int data) {
            this.data = data;
        }
    }
    
    /**
     * 图(邻接表形式)
     */
    private static class Graph  {
    private int size;
    private Vertex[] vertexes;
    private LinkedList<Integer> adj[];
     Graph(int size){
    this.size = size;
    //初始化顶点和邻接矩阵
    vertexes = new Vertex[size];
    adj = new LinkedList[size];
    for(int i=0; i<size; i++){
    vertexes[i] = new Vertex(i);
    adj[i] = new LinkedList();
            }
        }
    }
    
    /**
     * 深度优先遍历
     */
    public static void dfs(Graph graph, int start, boolean[] visited) {
        System.out.println(graph.vertexes[start].data);
        visited[start] = true;
        for(int index : graph.adj[start]){
            if(!visited[index]){
                dfs(graph, index, visited);
            }
        }
    }
    
    /**
     * 广度优先遍历
     */
    public static void bfs(Graph graph, int start, boolean[] visited, LinkedList<Integer> queue) {
        queue.offer(start);
        while (!queue.isEmpty()){
            int front = queue.poll();
            if(visited[front]){
                continue;
            }
            System.out.println(graph.vertexes[front].data);
            visited[front] = true;
            for(int index : graph.adj[front]){
                queue.offer(index);;
            }
        }
    }
    
    
    public static void main(String[] args) {
        Graph graph = new Graph(6);
    
        graph.adj[0].add(1);
        graph.adj[0].add(2);
        graph.adj[0].add(3);
    
        graph.adj[1].add(0);
        graph.adj[1].add(3);
        graph.adj[1].add(4);
    
        graph.adj[2].add(0);
    
        graph.adj[3].add(0);
        graph.adj[3].add(1);
        graph.adj[3].add(4);
        graph.adj[3].add(5);
    
        graph.adj[4].add(1);
        graph.adj[4].add(3);
        graph.adj[4].add(5);
    
        graph.adj[5].add(3);
        graph.adj[5].add(4);
    
        System.out.println("图的深度优先遍历:");
        dfs(graph, 0, new boolean[graph.size]);
        System.out.println("图的广度优先遍历:");
        bfs(graph, 0, new boolean[graph.size], new LinkedList<Integer>());
    }
    复制代码

    note:生命太短暂,不要去做一些根本没有人想要的东西。

    转载于:https://juejin.im/post/5c9a468c51882531f12dcd7c

    展开全文
  • 数据结构–图(深度优先遍历和广度优先遍历)(Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢! 图的常用概念 图是一种数据...

    数据结构–图(深度优先遍历和广度优先遍历)(Java)

    博客说明

    文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢!

    图的常用概念

    图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。

    • 顶点(vertex)
    • 边(edge)
    • 路径
    • 无向图

    eed2c4bd39386337d471d4a36c30e67f.png
    • 有向图

    9e941f0e46e62cb9077167c0187a16d9.png
    • 带权图

    d1b837e25d301f55950a10404cbf8c8f.png

    图的表示方式

    图的表示方式有两种:二维数组表示(邻接矩阵);链表表示(邻接表)。

    邻接矩阵

    邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于n个顶点的图而言,矩阵是的row和col表示的是1....n个点。

    d57c15bd9b22d33b843a458c2726f312.png
    邻接表

    邻接矩阵需要为每个顶点都分配n个边的空间,其实有很多边都是不存在,会造成空间的一定损失

    邻接表的实现只关心存在的边,不关心不存在的边。因此没有空间浪费,邻接表由数组+链表组成

    25f4763871e5e666164ad97565545370.png

    代码实现

    package com.guizimo;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    
    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);
    
            //遍历图
            graph.showGraph();
    
            System.out.println("广度优先遍历
            graph.dfs(); 
            System.out.println("深度优先遍历
            graph.bfs();
    
        }
    
        public Graph(int n) {
            edges = new int[n][n];
            vertexList = new ArrayList<String>(n);
            numOfEdges = 0;
        }
    
    
        public int getFirstNeighbor(int index) {
            for(int j = 0; j < vertexList.size(); j++) {
                if(edges[index][j] > 0) {
                    return j;
                }
            }
            return -1;
        }
    
        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;
        }
    
        //深度优先遍历
        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);
            }
    
        }
    
        public void dfs() {
            isVisited = new boolean[vertexList.size()];
            for(int i = 0; i < getNumOfVertex(); i++) {
                if(!isVisited[i]) {
                    dfs(isVisited, i);
                }
            }
        }
    
        //广度优先遍历
        private 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); 
                }
            }
    
        } 
    
        public void bfs() {
            isVisited = new boolean[vertexList.size()];
            for(int i = 0; i < getNumOfVertex(); i++) {
                if(!isVisited[i]) {
                    bfs(isVisited, i);
                }
            }
        }
    
        public int getNumOfVertex() {
            return vertexList.size();
        }
    
        //遍历
        public void showGraph() {
            for(int[] link : edges) {
                System.err.println(Arrays.toString(link));
            }
        }
    
        public int getNumOfEdges() {
            return numOfEdges;
        }
    
        public String getValueByIndex(int i) {
            return vertexList.get(i);
        }
    
        public int getWeight(int v1, int v2) {
            return edges[v1][v2];
        }
    
        //添加邻接矩阵
        public void insertVertex(String vertex) {
            vertexList.add(vertex);
        }
    
      //插入权值
        public void insertEdge(int v1, int v2, int weight) {
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    }
    

    图的深度优先搜索(Depth First Search)

    深度优先遍历,从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点, 可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点

    算法
    • 访问初始结点v,并标记结点v为已访问。
    • 查找结点v的第一个邻接结点w。
    • 若w存在,则继续执行4,如果w不存在,则回到第1步,将从v的下一个结点继续。
    • 若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。
    • 查找结点v的w邻接结点的下一个邻接结点,转到步骤3
    代码
    //深度优先遍历
    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);
      }
    
    }
    
    public void dfs() {
      isVisited = new boolean[vertexList.size()];
      for(int i = 0; i < getNumOfVertex(); i++) {
        if(!isVisited[i]) {
          dfs(isVisited, i);
        }
      }
    }

    图的广度优先搜索(Broad First Search)

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

    算法
    • 访问初始结点v并标记结点v为已访问。
    • 结点v入队列
    • 当队列非空时,继续执行,否则算法结束。
    • 出队列,取得队头结点u。
    • 查找结点u的第一个邻接结点w。
    • 若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:
      • 若结点w尚未被访问,则访问结点w并标记为已访问。
      • 结点w入队列
      • 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6
    代码
    //广度优先遍历
    private 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); 
        }
      }
    
    } 
    
    public void bfs() {
      isVisited = new boolean[vertexList.size()];
      for(int i = 0; i < getNumOfVertex(); i++) {
        if(!isVisited[i]) {
          bfs(isVisited, i);
        }
      }
    }

    感谢

    尚硅谷

    以及勤劳的自己,个人博客,GitHub

    http://weixin.qq.com/r/0zguNoLEUt8trcZV923B (二维码自动识别)

    展开全文
  • 本文实例讲述了python实现树的深度优先遍历广度优先遍历。分享给大家供大家参考,具体如下:广度优先(层次遍历)从树的root开始,从上到下从左到右遍历整个树的节点数二叉树的区别就是,二叉树只有左右两个节点...

    本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下:

    广度优先(层次遍历)

    从树的root开始,从上到下从左到右遍历整个树的节点

    数和二叉树的区别就是,二叉树只有左右两个节点

    广度优先 顺序:A - B - C - D - E - F - G - H - I

    代码实现

    def breadth_travel(self, root):

    """利用队列实现树的层次遍历"""

    if root == None:

    return

    queue = []

    queue.append(root)

    while queue:

    node = queue.pop(0)

    print node.elem,

    if node.lchild != None:

    queue.append(node.lchild)

    if node.rchild != None:

    queue.append(node.rchild)

    深度优先

    深度优先有三种算法:前序遍历,中序遍历,后序遍历

    先序遍历 在先序遍历中,我们先访问根节点,然后递归使用先序遍历访问左子树,再递归使用先序遍历访问右子树

    根节点->左子树->右子树

    #实现 1

    def preorder(self, root):

    """递归实现先序遍历"""

    if root == None:

    return

    print root.elem

    self.preorder(root.lchild)

    self.preorder(root.rchild)

    #实现 2

    def depth_tree(tree_node):

    if tree_node is not None:

    print (tree_node._data)

    if tree_node._left is noe None:

    return depth_tree(tree_node._left)

    if tree_node._right is not None:

    return depth_tree(tree_node._right)

    中序遍历 在中序遍历中,我们递归使用中序遍历访问左子树,然后访问根节点,最后再递归使用中序遍历访问右子树

    左子树->根节点->右子树

    def inorder(self, root):

    """递归实现中序遍历"""

    if root == None:

    return

    self.inorder(root.lchild)

    print root.elem

    self.inorder(root.rchild)

    后序遍历 在后序遍历中,我们先递归使用后序遍历访问左子树和右子树,最后访问根节点

    左子树->右子树->根节点

    def postorder(self, root):

    """递归实现后续遍历"""

    if root == None:

    return

    self.postorder(root.lchild)

    self.postorder(root.rchild)

    print root.elem

    更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

    希望本文所述对大家Python程序设计有所帮助。

    时间: 2019-10-26

    展开全文
  • 图的深度优先遍历和广度优先遍历深度优先遍历广度优先遍历 邻接表的形式表示一个图: const graph = { 0: [1,2], 1: [2], 2: [3,0], 3: [3,0] } 深度优先遍历 深度优先遍历就是优先遍历完一条完整路径,和树的...
  • Java实现二叉树的深度优先遍历和广度优先遍历算法示例 树的深度优先遍历和广度优先遍历的原理   二叉树的深度优先遍历(栈)和广度优先遍历(队列)   二叉树的深度优先遍历(DFS)与广度优先遍历(BFS)  ...
  • JS深度优先遍历和广度优先遍历 深度优先遍历 (DFS) Depth First Search (1)访问顶点v; (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问; (3)若此时图中尚...
  • C语言实现图的深度优先遍历和广度优先遍历

    千次阅读 多人点赞 2019-11-28 20:29:17
    图的深度优先遍历和广度优先遍历图的遍历深度优先遍历广度优先遍历 图的遍历 从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中所有顶点,使每个顶点仅被访问一次,这个过程称为图的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,701
精华内容 1,880
关键字:

深度优先遍历和广度优先遍历