淘先锋技术网

首页 1 2 3 4 5 6 7

图的深度优先遍历、广度优先遍历

这个题目是我在《啊哈！算法》中看到的，题目如下：

 

深度优先遍历：

思路如下：

首先，当地图二维数组e[x][y]的x = 5 的时候，说明已经到达5号城市，可以return了，所以，这个递归的终止条件伪代码如下：

        /*
        * 递归终止条件，x=5
        * 终止时，判断路径总和是否小于最小路径总和
        * */       
         if (x == 5){
            if (sum < min){
                min = sum;
            }
            return ;
        }

然后是递归部分，我们用book[x][y] = 1表示x城市到y城市已经走过了，并且当地图e[x][y]的值，也就是x城市到y城市有路径长度的时候大于0的时候，那么我们就把y城市当做起始城市传入下一递归中，伪代码如下：

        /*
        * 遍历y坐标，当[x][y]大于0时，将y作为x坐标递归，并且sum相加
        * */
        for (int i = 1; i < map[i].length - 1; i++) {

            if (book[x][i] == 1){
                continue;
            }

            if (map[x][i] != 0)
            {
                book[x][i] = 1;
                sum += map[x][i];
                dfs(i, sum);
            }

        }

最终代码如下：

package com.ziyu.aha;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName 第五章 第二节 城市地图
 * @Date
 * @Author
 * @Description TODO
 **/
public class test5 {

    //地图
    static int[][] map = new int[7][7];
    //book用来标记已走过的城市
    static int[][] book = new int[7][7];
    static int min = 999;
    //路径顺序
    static Queue<Integer> way = new LinkedList<>();
    //最短路径顺序
    static Queue<Integer> minway = new LinkedList<>();


    public static void main(String[] args){

        map[1][2] = 2;
        map[1][5] = 10;
        map[2][3] = 3;
        map[2][5] = 7;
        map[3][1] = 4;
        map[3][4] = 4;
        map[4][5] = 5;
        map[5][3] = 3;

        dfs(1, 0);

        System.out.println(min);
        minway.forEach(integer -> System.out.print(integer + "\t"));

    }

    public static void dfs(int x, int sum){

        /*
        * 递归终止条件，x=5
        * 终止时，判断路径总和是否小于最小路径总和
        * */
        if (x == 5){
            if (sum < min){
                min = sum;
            }
            return;
        }

        /*
        * 遍历y坐标，当[x][y]大于0时，将y作为x坐标递归，并且sum相加
        * */
        for (int i = 1; i < map[i].length - 1; i++) {

            if (book[x][i] == 1){
                continue;
            }

            if (map[x][i] != 0)
            {
                book[x][i] = 1;
                sum += map[x][i];
                dfs(i, sum);
            }

        }

    }

}

大家可以先想想，这样子是不是就是最终答案？

大家可以运行下试试，最终输出的结果是12。

但是，看都看得出，这个图中最短的路径是1->2->5，也就是2+7=9，那为什么代码会输出12呢？

我们一步一步来分析下，

第一次递归应该是i = 2的时候，因为x = 1是作为初始值传入的，第一次递归应该是e[1][2] = 2，sum = 0 + 2 = 2；

第二次递归时，x = 2， 当i = 3的时候，进入下一次递归。e[2][3] = 3，sum = 2 + 3 = 5；

第三次递归时，x = 3， 当i = 1的时候，进入下一次递归。e[3][1] = 4，sum = 5 + 4 = 9；

这里，x又回到了1，所以，第四次递归时，x = 1， 当i = 5的时候，进入下一次递归。e[1][5] = 10，sum = 9 + 10 = 19；

到这里，x = 5，进入终止条件并且return到上一次递归 ；

第五次递归时，x = 3， 当i = 4的时候，进入下一次递归。e[3][4] = 4，sum = 9 + 4 = 13；

第六次递归时，x = 4， 当i = 5的时候，进入下一次递归。e[4][5] = 5，sum = 13 + 5 = 18；

到这里，x = 5，进入终止条件并且return到上一次递归 ；

因为x = 3，x = 4，这两个城市作为起点都已经走过了，所以，return 回到x = 2；

第七次递归时，x = 2， 当i = 5的时候，进入下一次递归。e[2][5] = 7，sum = 5 + 7 = 12；

到这里，问题就已经显现出来了，按道理来说，1->2->5，理应路径和为9，现在路径和却为12，这是为什么呢？

其实这是一个递归初学者比较容易犯的错误，包括我自己，因为我也是初学者。

这错误是什么呢？给大家再回顾一下，大家就知道了。再贴下递归部分代码

        /*
        * 遍历y坐标，当[x][y]大于0时，将y作为x坐标递归，并且sum相加
        * */
1        for (int i = 1; i < map[i].length - 1; i++) {
2
3            if (book[x][i] == 1){
4                continue;
5            }
6
7            if (map[x][i] != 0)
8            {
9                book[x][i] = 1;
10                sum += map[x][i];
11                dfs(i, sum);
12            }
13
14        }

给大家标个序号可能会更清楚点，

第一次进入递归是从第9行开始，book标记已走过，

第10行执行后sum = 2，然后以x = 2，sum = 2进入下个递归，

大家想想，当x = 2走完一轮return 回到 x = 1的时候，sum应该等于多少？是不是0？但是，在我的代码中，当x return回1的时候，sum其实是2，因为sum已经+=2了，所以不会是0。

简单的说，就是在递归中，如果涉及到累计的递归，那么，要注意，累计的那个值sum在没进入下次递归前，一定不能跟着递归改变，

就是说，sum在还没进入递归的时候，他就已经被递归的值所影响了，所以递归在return回来的时候，sum的值就会出错。

修改后的代码如下：

package com.ziyu.aha;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName 第五章 第二节 城市地图
 * @Date
 * @Author
 * @Description TODO
 **/
public class test5 {

    //地图
    static int[][] map = new int[7][7];
    //book用来标记已走过的城市
    static int[][] book = new int[7][7];
    static int min = 999;
    //路径顺序
    static Queue<Integer> way = new LinkedList<>();
    //最短路径顺序
    static Queue<Integer> minway = new LinkedList<>();


    public static void main(String[] args){

        map[1][2] = 2;
        map[1][5] = 10;
        map[2][3] = 3;
        map[2][5] = 7;
        map[3][1] = 4;
        map[3][4] = 4;
        map[4][5] = 5;
        map[5][3] = 3;

        dfs(1, 0, 0);

        System.out.println(min);
        minway.forEach(integer -> System.out.print(integer + "\t"));

    }

    public static void dfs(int x, int length, int sum){

        sum += length;


        /*
        * 递归终止条件，x=5
        * 终止时，判断路径总和是否小于最小路径总和
        * */
        if (x == 5){
            if (sum < min){
                min = sum;
            }
            return;
        }


        /*
        * 遍历y坐标，当[x][y]大于0时，将y作为x坐标递归
        * */
        for (int i = 1; i < map[i].length - 1; i++) {

            if (book[x][i] == 1){
                continue;
            }

            if (map[x][i] != 0)
            {
                book[x][i] = 1;
                dfs(i, map[x][i], sum);
            }

        }

    }

}

虽然结果一样，但是其实上面的代码，还可以再做优化，比如：如果sum大于最小路径，直接返回

        /*
        * 如果sum大于最小路径，直接返回
        * */
        if (sum > min)
            return;

而且，在return之后，book标记应该被清除掉，

下面是我参照了书中的代码后，做的修改，

1.sum累加的方式修改了（自认为比较重要）

2.在return之后，book标记会被清除掉

3.新增路径记录

完整代码如下：

package com.ziyu.aha;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @ClassName 第五章 第二节 城市地图
 * @Date
 * @Author
 * @Description TODO
 **/
public class test5 {

    //地图
    static int[][] map = new int[7][7];
    //book用来标记已走过的城市
    static int[][] book = new int[7][7];
    static int min = 999;
    //路径顺序
    static Stack<Integer> way = new Stack<>();
    //最短路径顺序
    static Stack<Integer> minway = new Stack<>();

    public static void main(String[] args){

        map[1][2] = 2;
        map[1][5] = 10;
        map[2][3] = 3;
        map[2][5] = 7;
        map[3][1] = 4;
        map[3][4] = 4;
        map[4][5] = 5;
        map[5][3] = 3;

        dfs(1, 0);

        System.out.println("min:" + min);
        minway.forEach(integer -> System.out.print(integer + "\t"));

    }

    public static void dfs(int x, int sum){

        way.push(x);

        /*
        * 如果sum大于最小路径，直接返回
        * */
        if (sum > min)
            return;

        /*
        * 递归终止条件，x=5
        * 终止时，判断路径总和是否小于最小路径总和
        * */
        if (x == 5){
            System.out.println(sum);
            way.forEach(integer -> System.out.print(integer + "——>"));
            System.out.println();
            if (sum < min){
                min = sum;
                minway.clear();
                minway.addAll(way);
            }
            return;
        }

        /*
        * 遍历y坐标，当[x][y]大于0时，将y作为x坐标递归，并且sum相加
        * */
        for (int i = 1; i < map[i].length - 1; i++) {

            if (book[x][i] == 1){
                continue;
            }

            if (map[x][i] != 0)
            {
                book[x][i] = 1;
                dfs(i, sum + map[x][i]);
                way.pop();
                book[x][i] = 0;
            }

        }

    }

}

最后输出结果是这样：

广度优先遍历：

广度优先其实和深度优先差不了太多，主要是通过队列的方式实现

代码如下：

//int[0] 城市 int[1] sum路径和
    static Queue<int[]> queue = new LinkedList<>();

    public static void bsf(){

        while (!queue.isEmpty()){

            int[] peek = queue.peek();
            int x = peek[0];
            int sum = peek[1];

            if (sum > min)
                return;

            if (x == 5) {
                if (sum < min){
                    min = sum;
                    queue.remove();
                    continue;
                }
            }

            for (int i = 1; i < map[0].length; i++){

                if (book[x][i] == 1){
                    continue;
                }

                //入队
                if (map[x][i] != 0)
                {
                    book[x][i] = 1;
                    int[] next = new int[2];
                    next[0] = i;
                    next[1] = sum + map[x][i];
                    queue.add(next);
                }

            }
            
            //出队
            queue.remove();

        }
    }

最终整篇完整的代码如下

package com.ziyu.aha;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @ClassName 第五章 第二节 城市地图
 * @Date
 * @Author
 * @Description TODO
 **/
public class test5 {

    //地图
    static int[][] map = new int[7][7];
    //book用来标记已走过的城市
    static int[][] book = new int[7][7];
    static int min = 999;
    //路径顺序
    static Stack<Integer> way = new Stack<>();
    //最短路径顺序
    static Stack<Integer> minway = new Stack<>();

    public static void main(String[] args){

        map[1][2] = 2;
        map[1][5] = 10;
        map[2][3] = 3;
        map[2][5] = 7;
        map[3][1] = 4;
        map[3][4] = 4;
        map[4][5] = 5;
        map[5][3] = 3;

//        dfs(1, 0);

        int[] a = new int[]{1,0};
        queue.add(a);

        book[1][1] = 1;
        bsf();

        System.out.println("min:" + min);
//        minway.forEach(integer -> System.out.print(integer + "\t"));

    }

    public static void dfs(int x, int sum){

        way.push(x);

        /*
        * 如果sum大于最小路径，直接返回
        * */
        if (sum > min)
            return;

        /*
        * 递归终止条件，x=5
        * 终止时，判断路径总和是否小于最小路径总和
        * */
        if (x == 5){
            System.out.println(sum);
            way.forEach(integer -> System.out.print(integer + "——>"));
            System.out.println();
            if (sum < min){
                min = sum;
                minway.clear();
                minway.addAll(way);
            }
            return;
        }

        /*
        * 遍历y坐标，当[x][y]大于0时，将y作为x坐标递归，并且sum相加
        * */
        for (int i = 1; i < map[i].length - 1; i++) {

            if (book[x][i] == 1){
                continue;
            }

            if (map[x][i] != 0)
            {
                book[x][i] = 1;
                dfs(i, sum + map[x][i]);
                way.pop();
                book[x][i] = 0;
            }

        }

    }

    //int[0] 城市 int[1] sum路径和
    static Queue<int[]> queue = new LinkedList<>();

    public static void bsf(){

        while (!queue.isEmpty()){

            int[] peek = queue.peek();
            int x = peek[0];
            int sum = peek[1];

            if (sum > min)
                return;

            if (x == 5) {
                if (sum < min){
                    min = sum;
                    queue.remove();
                    continue;
                }
            }

            for (int i = 1; i < map[0].length; i++){

                if (book[x][i] == 1){
                    continue;
                }

                //入队
                if (map[x][i] != 0)
                {
                    book[x][i] = 1;
                    int[] next = new int[2];
                    next[0] = i;
                    next[1] = sum + map[x][i];
                    queue.add(next);
                }

            }

            //出队
            queue.remove();

        }
    }

}

广度优先遍历是我自加的，书中没有代码，所以，上述如果有什么错误的地方，欢迎指正！