BFS（Breadth First Search）广度优先遍历，从图的某一结点出发，首先依次访问该结点的所有邻接顶点 Vi1, Vi2, …, Vin 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。

广度优先一般使用队列来完成,不需要使用递归,相对来说比较简单,接下来是一个广度优先算法的一个模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 顶点数
private int number = 9;
// 记录顶点是否被访问
private boolean[] flag;
// 顶点
private String[] vertexs = { "A", "B", "C", "D", "E", "F", "G", "H", "I" };
// 边
private int[][] edges = { 
        { 0, 1, 0, 0, 0, 1, 1, 0, 0 }, 
        { 1, 0, 1, 0, 0, 0, 1, 0, 1 }, 
        { 0, 1, 0, 1, 0, 0, 0, 0, 1 },
        { 0, 0, 1, 0, 1, 0, 1, 1, 1 },
        { 0, 0, 0, 1, 0, 1, 0, 1, 0 }, 
        { 1, 0, 0, 0, 1, 0, 1, 0, 0 },
        { 0, 1, 0, 1, 0, 1, 0, 1, 0 },
        { 0, 0, 0, 1, 1, 0, 1, 0, 0 }, 
        { 0, 1, 1, 1, 0, 0, 0, 0, 0 } 
        };


// 图的广度遍历操作
void BFSTraverse() {
    flag = new boolean[number];
    Queue<Integer> queue = new LinkedList<Integer>();
    for (int i = 0; i < number; i++) {
        if (flag[i] == false) {
            flag[i] = true;
            System.out.print(vertexs[i] + " ");
            queue.add(i);
            while (!queue.isEmpty()) {
                int j = queue.poll();
                for (int k = 0; k < number; k++) {
                    if (edges[j][k] == 1 && flag[k] == false) {
                        flag[k] = true;
                        System.out.print(vertexs[k] + " ");
                        queue.add(k);
                    }
                }
            }
        }
    }
}

还是用九个顶点的图来作为示例,首先,创建一个标志数组,用来标示该顶点有没有被访问过,接下来,从第一个顶点开始(其实任意一个顶点都可以),将该顶点加入到队列中,接下来开启循环,拿出队列头部的一个节点,如果该队列有邻接的节点,那么将邻接节点添加到队列中,直到有所节点都被访问完为止.

运行结果:

A->B->F->G->C->I->E->D->H

广度优先遍历一个典型的题目就是按照二叉树的层次打印节点的值.

当然也可以解决最短路径的问题,如果只要求输出最短路径的长度,这个时间复杂度是比深度优先好的,但是如果要把最短的路径打印出来,广度优先就显得无能为力了,还是要用深度优先.还是前一篇文章深度优先算法中走迷宫的例子,我们这次使用广广度优先,只输出最短路径的值,不打印具体路径;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
static int[][] arr = {
        {0, 1, 1, 1, 1},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 1, 0},
        {1, 1, 1, 0, 0},
};

static class Pair {
    int i;
    int j;

    public Pair(int i, int j) {
        this.i = i;
        this.j = j;
    }

    @Override
    public String toString() {
        return i + "<>" + j;
    }
}


static void bfs() {
    LinkedList<Pair> queue = new LinkedList<Pair>();
    queue.add(new Pair(0, 0));
    dp[0][0] = true;
    int level = 1;
    int preCount = 1;
    int curCount = 0;

    while (!queue.isEmpty()) {
        //首先把当前层的全部都拿出来
        while (preCount-- > 0) {
            Pair pair = queue.poll();
          //如果走到的右下角,打印层次,结束程序
            if (pair.i == arr.length - 1 && pair.j == arr[0].length - 1) {
                System.out.println(level);
                return;
            }
            //向下
            if (pair.i + 1 < arr.length && !dp[pair.i + 1][pair.j] && arr[pair.i + 1][pair.j] == 0) {
                dp[pair.i + 1][pair.j] = true;
                queue.offer(new Pair(pair.i + 1, pair.j));
                curCount++;
            }

            //向右
            if (pair.j + 1 < arr[0].length && !dp[pair.i][pair.j + 1] && arr[pair.i][pair.j + 1] == 0) {
                dp[pair.i][pair.j + 1] = true;
                queue.offer(new Pair(pair.i, pair.j + 1));
                curCount++;
            }

            //向上
            if (pair.i - 1 >= 0 && !dp[pair.i - 1][pair.j] && arr[pair.i - 1][pair.j] == 0) {
                dp[pair.i - 1][pair.j] = true;
                queue.offer(new Pair(pair.i - 1, pair.j));
                curCount++;
            }

            //向左
            if (pair.j - 1 >= 0 && !dp[pair.i][pair.j - 1] && arr[pair.i][pair.j - 1] == 0) {
                dp[pair.i][pair.j - 1] = true;
                queue.offer(new Pair(pair.i, pair.j - 1));
                curCount++;
            }
        }

        preCount = curCount;
        curCount = 0;
        level++;
    }
}