数据结构与算法(三十一)图的遍历--深度优先遍历和广度优先遍历

图的深度优先遍历介绍

图遍历介绍
所谓图的遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历
深度优先遍历基本思想

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

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

深度优先遍历算法步骤

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

代码实现

首先增加几个方法和属性

 //表示是否被访问过
    private boolean [] isVisited;

/**
     * 得到第一个邻接节点的下标  不存在返回-1
     * @param index
     * @return
     */
    public int getFirstNeighbor(int index){
        for (int j=0;j<vertexList.size();j++){
            if (edges[index][j]>0){
                return j;
            }
        }
        return -1;
    }

 /**
     * 根据前一个邻接节点的下标来获取下一个邻接节点
     * @param v1
     * @param v2
     * @return
     */
    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;
    }

深度优先遍历

/**
     * 深度优先遍历
     * @param isVisited
     * @param i
     */
    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(){
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }

广度优先遍历基本思想

图的广度优先搜索(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);
            }
        }
    }

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.fengpt.cn/archives/数据结构与算法三十一图的遍历