算法篇四 图与BFS/DFS

public class LeetCode {
    public static void main(String[] args) {
        // 搜索从s节点到t节点的可达路径
        Graph graph = new Graph(8);
        graph.bfs(0, 6);
    }
}

class Graph {
    // 顶点个数
    private int v;
    // 邻接表
    private LinkedList<Integer>[] adj;

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
        // 创建关联
        adj[0].offer(1);
        adj[0].offer(3);
        adj[1].offer(0);
        adj[1].offer(4);
        adj[1].offer(2);
        adj[2].offer(1);
        adj[2].offer(5);
        adj[3].offer(0);
        adj[3].offer(4);
        adj[4].offer(1);
        adj[4].offer(3);
        adj[4].offer(5);
        adj[4].offer(6);
        adj[5].offer(2);
        adj[5].offer(4);
        adj[5].offer(7);
        adj[6].offer(4);
        adj[6].offer(7);
        adj[7].offer(5);
        adj[7].offer(6);
    }

    public void bfs(int s, int t) {
        if (s == t) {
            return;
        }
        // visited存储的是每个节点的访问状态, true表示已经访问过
        boolean[] visited = new boolean[v];
        visited[s] = true;
        // queue 存储的是访问过的节点, 但是还没有访问过相邻节点
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(s);
        // prev存储的是搜索路径, 比如prev[2] = 1的话, 就代表2这个节点是由1搜索过来的
        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }
        while (queue.size() != 0) {
            // 从队列里取出一个节点
            int w = queue.poll();
            // 依次访问这个节点的相邻可达节点
            for (int i = 0; i < adj[w].size(); i++) {
                int q = adj[w].get(i);
                // 如果q节点没被访问, 则记录q节点的前驱节点w
                if (!visited[q]) {
                    prev[q] = w;
                    // 如果当前节点q等于要寻找的节点t, 则打印搜索路径
                    if (q == t) {
                        print(prev, s, t);
                        return;
                    }
                    // 否则标记节点已经访问, 并且把当前节点加入队列
                    visited[q] = true;
                    queue.offer(q);
                }
            }
        }
    }

    // dfs要用, 表示有没有找到t
    boolean found = false;

    public void dfs(int s, int t) {
        boolean[] visited = new boolean[v];
        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }
        recurDfs(s, t, visited, prev);
        print(prev, s, t);
    }

    private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
        if (found) {
            return;
        }
        visited[w] = true;
        if (w == t) {
            found = true;
            return;
        }
        for (int i = 0; i < adj[w].size(); i++) {
            int q = adj[w].get(i);
            if (!visited[q]) {
                prev[q] = w;
                // 递归深度查找, 直到q==t
                recurDfs(q, t, visited, prev);
            }
        }
    }

    private void print(int[] prev, int s, int t) {
        // 如果t节点是可达的, 并且 初始节点不等于可达节点(递归的边界条件)
        if (prev[t] != -1 && t != s) {
            // 因为路径是逆向存储的, 所以先递归到初始节点, prev[t] 代表目标节点的前一个节点的前驱节点
            print(prev, s, prev[t]);
        }
        System.out.println(t + "");
    }
}