深度优先搜索热身，使用深度优先搜索标记无向图中连通的顶点

搜索 API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Search {

    /**
     * 找到和起点 s 连通的所有顶点
     */
    public Search(Graph graph, int s);

    /**
     * 检测 v 和 s 是否连通
     */
    public boolean marked(int v);

    /**
     * 与 s 连通的顶点总数
     */
    public int count();
}

深度优先搜索实现

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
public class DepthFirstSearch {

    private boolean[] marked;

    private int count;

    /**
     * 找到和起点 s 连通的所有顶点
     */
    public DepthFirstSearch(Graph graph, int s) {
        marked = new boolean[graph.v()];

    }

    /**
     * 深度优先搜索实现
     */
    private void dfs(Graph graph, int v) {
        marked[v] = true;
        count++;
        for (int w : graph.adj(v)) {
            if (!marked[w]) {
                dfs(graph, w);
            }
        }
    }

    /**
     * 检测 v 和 s 是否连通
     */
    public boolean marked(int v) {
        return marked[v];
    }

    /**
     * 与 s 连通的顶点总数
     */
    public int count() {
        return count;
    }
}

测试

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
public static void main(String[] args) {
    Graph graph = new Graph(13);
    graph.addEdge(0, 5);
    graph.addEdge(4, 3);
    graph.addEdge(0, 1);
    graph.addEdge(9, 12);
    graph.addEdge(6, 4);
    graph.addEdge(5, 4);
    graph.addEdge(0, 2);
    graph.addEdge(11, 12);
    graph.addEdge(9, 10);
    graph.addEdge(0, 6);
    graph.addEdge(7, 8);
    graph.addEdge(9, 11);
    graph.addEdge(5, 3);

    DepthFirstSearch depthFirstSearch = new DepthFirstSearch(graph, 0);
    System.out.println(depthFirstSearch.count()); // 输出 7，包含自身

    System.out.println(depthFirstSearch.marked(6)); // true
    System.out.println(depthFirstSearch.marked(2)); // true
    System.out.println(depthFirstSearch.marked(1)); // true
    System.out.println(depthFirstSearch.marked(5)); // true
    System.out.println(depthFirstSearch.marked(3)); // true
    System.out.println(depthFirstSearch.marked(4)); // true
    System.out.println(depthFirstSearch.marked(0)); // true

    System.out.println(depthFirstSearch.marked(7)); // false
    System.out.println(depthFirstSearch.marked(8)); // false
}