算法模板--图

1.邻接表存图

    // 图中共有n个节点
    List<Integer>[] graph = new LinkedList[n];
    for (int i = 0; i < n; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : edges) {
        int from = edge[0], to = edge[1];
        // 添加一条从 from 指向 to 的有向边
        graph[from].add(to);
    }

2.邻接矩阵存图

    int[][] graph = new int[n][n];
    for (int[] edge : edges) {
        int from = edge[0];
        int to = edge[1];
        graph[from][to] = 1; 
    }

3.遍历二维矩阵

// 方向数组，分别代表上、下、左、右
int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
boolean[][] visited;
void dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (visited[i][j]) {
        // 已遍历过 (i, j)
        return;
    }

    // 进入节点 (i, j)
    visited[i][j] = true;
    // 递归遍历上下左右的节点
    for (int[] d : dirs) {
        int next_i = i + d[0];
        int next_j = j + d[1];
        dfs(grid, next_i, next_j);
    }
    // 离开节点 (i, j)
}

4.BFS

应用场景：问题的本质是在一幅「图」中找到从起点 start 到终点 target 的最近距离

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路，遍历树不需要
    
    q.offer(start); // 将起点加入队列
    visited.add(start); 

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散，逐层遍历*/
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj()) {
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
        step++;
    }
    // 如果走到这里，说明在图中没有找到目标节点
}

5.判断有向无环图

1. 拓扑排序

    // 构建入度数组
    int[] indegree = new int[n];
    for (int[] edge : edges) {
        int from = edge[0], to = edge[1];
        // 节点 to 的入度加一
        indegree[to]++;
    }

    // 根据入度初始化队列中的节点
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            // 节点 i 没有入度，即没有依赖的节点
            // 可以作为拓扑排序的起点，加入队列
            q.offer(i);
        }
    }

    // 记录遍历的节点个数
    int count = 0;
    // 开始执行 BFS 循环
    while (!q.isEmpty()) {
        // 弹出节点 cur，并将它指向的节点的入度减一
        int cur = q.poll();
        count++;
        for (int next : graph[cur]) {
            indegree[next]--;
            if (indegree[next] == 0) {
                // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                q.offer(next);
            }
        }
    }

    // 如果所有节点都被遍历过，说明不成环
    return count == n;

2. DFS实现

    // 记录一次 traverse 递归经过的节点
    boolean[] onPath;
    // 记录遍历过的节点，防止走回头路
    boolean[] visited;
    // 记录图中是否有环
    boolean hasCycle = false;

    public boolean canFinish(int n, int[][] edges) {
        List<Integer>[] graph = buildGraph(n, edges);
        onPath = new boolean[n];
        visited = new boolean[n];
        // 遍历图中的所有节点
        for (int i = 0; i < n; i++){
            traverse(graph, i);
        }
        return !hasCycle;
    }

    // dfs
    void traverse(List<Integer>[] graph, int s) {
        // 如果已经找到了环，也不用再遍历了
        if (hasCycle || visited[s])
            return;
        if (onPath[s]){
            // 出现环
            hasCycle = true;
        }
        // 选择
        visited[s] = true;
        onPath[s] = true;

        // 遍历
        for (int i : graph[s]){
            traverse(graph, i);
        }
        // 取消选择
        onPath[s] = false;
            
    }