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

发表于 更新于 阅读次数：

前言

图之深度优先搜索的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
package com;

public class DepthFirstSearch {

    // 索引表示顶点，值表示当前顶点是否已被搜索
    private boolean[] marked;
    // 与当前结点相通的结点的个数
    private int nodeCount;

    DepthFirstSearch(Graph graph, int node) {
        // 初始化marked数组
        this.marked = new boolean[graph.getNodeLength()];
        // 初始化跟node顶点想通的所有相邻顶点
        this.nodeCount = 0;
        dfs(graph, node);
    }

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

    // 找出所有与node结点想通的结点
    private void dfs(Graph graph, int node) {
        marked[node] = true;
        for (Integer n : graph.adj(node)) {
            // 判断当前n顶点有没有被搜索，如果没有被搜索过，则通过dfs方法进行递归深度搜索
            if (!marked[n]) {
                dfs(graph, n);
            }
        }
        // 想通顶点数量自增
        nodeCount++;
    }

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

}

完成

参考文献

哔哩哔哩——黑马程序员