【代码】图之广度优先搜索

发表于 更新于 阅读次数：

前言

图之广度优先搜索的Java版API实现

源代码

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
package com;

public class BreadthFirstSearch {

    private boolean[] marked;
    private int nodeCount;
    // 用来存储邻接表的顶点
    private Queue<Integer> waitSearch;

    BreadthFirstSearch(Graph graph, int node) {
        this.marked = new boolean[graph.getNodeLength()];
        this.nodeCount = 0;
        this.waitSearch = new Queue<>();

        bfs(graph, node);
    }

    // 获取与当前顶点相通的顶点的总数
    public int getCount() {
        return nodeCount;
    }

    // 使用广度优先搜索找出途中node的所有邻接顶点
    private void bfs(Graph graph, int node) {
        // 把当前顶点标记为已搜索
        marked[node] = true;
        // 让顶点node加入队列，待搜索
        waitSearch.enQueue(node);
        // 通过循环，如果队列不为空，则队列中弹出一个待搜索的定点
        while (!waitSearch.isEmpty()) {
            // 弹出一个待搜索的顶点
            Integer wait = waitSearch.deQueue();
            // 遍历wait顶点的邻接表
            for (Integer n : graph.adj(wait)) {
                if (!marked[n]) {
                    bfs(graph, n);
                }
            }
        }
        // 让想通的顶点自增
        nodeCount++;
    }

    // 判断node结点是否与当前结点相通
    public boolean marked(int node) {
        return marked[node];
    }

}

完成

参考文献

哔哩哔哩——黑马程序员