图-深度遍历与广度遍历

1 思路

• 深度遍历

  • 从起始节点开始，不断深入，深入到节点周围节点都被走过。不断重复。
  • 借助栈实现

• 广度遍历

  • 像树的层次遍历，从起始节点开始，沿着起始相连节点一层层推进。直到所有节点便利完毕。
  • 借助队列实现

2 案例

案例

3 复杂度

• 时间复杂度
  • n^2

4 代码

• 把 Integer.MAX_VALUE / 2 当作我所有图相关 邻接矩阵的无限大。

package com.datastructure.map;

import java.util.*;

/**
 * BFS class
 *
 * @author 格林
 * @date 2021-06-01
 */
public class BFS {
    public static  void bfs(int[][] map){
        Queue<Integer> queue = new LinkedList<>();
        int start = 0;
        Set set = new HashSet();
        set.add(start);
        queue.add(start);
        System.out.print( "bfs：");
        while (queue.size() > 0) {
            Integer pop = ((LinkedList<Integer>) queue).pop();
            for(int i = 0; i < map[0].length; i ++) {
                if(  map[pop][i] != MAX &&  !set.contains(i)  ) {
                    set.add(i);
                    queue.offer(i);
                }
            }
            System.out.print(pop + " ");
        }
        System.out.println();
    }

    public static  void dfs(int[][] map){
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        Set set = new HashSet();
        set.add(start);
        stack.add(start);
        System.out.print( "dfs：");
        while (stack.size() > 0) {
            Integer pop = stack.pop();
            for(int i = 0; i < map[0].length; i ++) {
                if(  map[pop][i] != MAX &&  !set.contains(i)  ) {
                    set.add(i);
                    stack.push(i);
                }
            }
            System.out.print(pop + " ");
        }
        System.out.println();
    }


    public final static int MAX = Integer.MAX_VALUE / 2;
    public static void main(String[] args) {
        // 模式测试数据
        int[][] data = new int[16][3];
        data[0][0] = 0; data[0][1] = 1; data[0][2] = 1;
        data[1][0] = 0; data[1][1] = 2; data[1][2] = 5;
        data[2][0] = 1; data[2][1] = 2; data[2][2] = 3;
        data[3][0] = 1; data[3][1] = 4; data[3][2] = 5;
        data[4][0] = 1; data[4][1] = 3; data[4][2] = 7;
        data[5][0] = 2; data[5][1] = 5; data[5][2] = 7;
        data[12][0] = 2; data[12][1] = 4; data[12][2] = 1;
        data[6][0] = 3; data[6][1] = 4; data[6][2] = 2;
        data[7][0] = 4; data[7][1] = 5; data[7][2] = 3;
        data[8][0] = 3; data[8][1] = 6; data[8][2] = 3;
        data[9][0] = 4; data[9][1] = 6; data[9][2] = 6;
        data[10][0] = 4; data[10][1] = 7; data[10][2] = 9;
        data[13][0] = 5; data[13][1] = 7; data[13][2] = 5;
        data[11][0] = 6; data[11][1] = 7; data[11][2] = 2;
        data[14][0] = 6; data[14][1] = 8; data[14][2] = 7;
        data[15][0] = 7; data[15][1] = 8; data[15][2] = 4;

        // 初始化邻接矩阵
        int[][] map = new int[9][9];
        int num = map.length;
        for(int i = 0; i < num  ; i ++) {
            for (int j = 0; j <num ; j ++) {
                if(i == j) {
                    map[i][j] = 0;
                } else {
                    map[i][j] = MAX;
                }
            }
        }

        for(int i = 0; i < 16; i ++) {
            map[data[i][0]][data[i][1]] = data[i][2];
            map[data[i][1]][data[i][0]] = data[i][2];

        }
        System.out.println("邻接矩阵：");
        for(int i = 0; i < num; i ++ ) {
            System.out.println(Arrays.toString(map[i]));
        }
        bfs(map);
        System.out.println("----------------------");
        dfs(map);
    }
}

• 输出

邻接矩阵：
[0, 1, 5, 1073741823, 1073741823, 1073741823, 1073741823, 1073741823, 1073741823]
[1, 0, 3, 7, 5, 1073741823, 1073741823, 1073741823, 1073741823]
[5, 3, 0, 1073741823, 1, 7, 1073741823, 1073741823, 1073741823]
[1073741823, 7, 1073741823, 0, 2, 1073741823, 3, 1073741823, 1073741823]
[1073741823, 5, 1, 2, 0, 3, 6, 9, 1073741823]
[1073741823, 1073741823, 7, 1073741823, 3, 0, 1073741823, 5, 1073741823]
[1073741823, 1073741823, 1073741823, 3, 6, 1073741823, 0, 2, 7]
[1073741823, 1073741823, 1073741823, 1073741823, 9, 5, 2, 0, 4]
[1073741823, 1073741823, 1073741823, 1073741823, 1073741823, 1073741823, 7, 4, 0]
bfs：0 1 2 3 4 5 6 7 8 
----------------------
dfs：0 2 5 7 8 6 3 4 1