【代码】图之路径查找

发表于 更新于 阅读次数：

前言

在深度优先查找的基础上，实现图之路径查找的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
50
51
52
53
54
55
56
57
58
59
package com;

public class DeepFirstPath {

    private boolean[] marked;
    // 起点
    private int start;
    // 索引表示定点，值表示路径中的上一个顶点
    private int[] edgeTo;

    public DeepFirstPath(Graph graph, int start) {
        // 初始化marked数组
        this.marked = new boolean[graph.getNodeLength()];
        // 初始化起点
        this.start = start;
        // 初始化edgeTo数组
        this.edgeTo = new int[graph.getNodeLength()];

        dfs(graph, start);
    }

    // 使用深度优先搜索，找到所有与node相邻的结点
    private void dfs(Graph graph, int node) {
        // 把当前结点标记为已搜索
        marked[node] = true;
        // 遍历当前结点的邻接表，获取每一个相邻的顶点，继续递归搜索
        for (Integer n : graph.adj(node)) {
            // 如果结点n没有被搜索，就继续递归搜索
            if (!marked[n]) {
                // 到达当前结点的路径上最后一个结点是node
                edgeTo[n] = node;
                dfs(graph, node);
            }
        }

    }

    // 判断起点与当前结点是否存在路径
    public boolean hasPathTo(int node) {
        return marked[node];
    }

    // 找出起点到node结点所有经过的结点
    public Stack<Integer> pathTo(int node) {
        if (!hasPathTo(node)) {
            return null;
        }
        // 创建一个栈，保存路径中的所有结点
        Stack<Integer> path = new Stack<>();
        // 通过循环，从node结点开始，一直找到起点为止
        for (int i = node; i != start; i = edgeTo[i]) {
            path.push(i);
        }
        // 把起点放到栈中
        path.push(start);
        return path;
    }

}

完成

哔哩哔哩——黑马程序员