[TOC]

图篇的内容：

图的表示
BFS
DFS
最小生成树问题
最短路径问题
图的连通性

最短路

多源最短路

题目描述

在一个大城市中，环卫工人小C和他的团队负责清理城市的生活垃圾。整个城市被分为了若干个区域，每个区域被划分为m行n列的网格。环卫工人需要将每个居民区的垃圾运输到最近的垃圾回收站。这个任务要求计算所有居民区垃圾送到回收站的最小总距离。

输入

第一行为两个整数m和n，表示网格的行数和列数，其中m和n的范围均为[1,300)。接下来m行表示区域的矩阵布局，每行元素间以空格分隔。网格元素为以下几种：

-1 表示该区域有障碍物，不可通行。
0 表示垃圾回收站。
1 表示居民区，需要收集垃圾。
2 表示空白区域，可以自由通行。

输出

输出一个整数，表示将所有居民区的垃圾送到最近的垃圾回收站所需的最小距离和。如果无法到达垃圾回收站的居民区将被忽略。

样例

输入：
4 4
1 2 -1 1
2 0 2 0
2 2 -1 2
1 2 1 1

输出：
11

说明：
位于坐标(0, 0)、(0, 3)、(3, 0)、(3, 3)的是小区，位置(1, 1)、(1, 3)的是垃圾站，位置(0, 2)、(2, 2)的是障碍物，无法通行。图中共有5个小区和2个垃圾站。小区到垃圾站的最小路径长度是2+3+1+3+2=11。对于位于(3, 2)的小区，垃圾可以运送到(1, 1)或(1, 3)两个垃圾站，两者的距离相同。

输入：
2 3
0 -1 1
1 -1 2

输出：
1

解答

以所有的回收站为起点，所有的小区为终点进行搜索。搜索完成后将所有最短路的距离相加即可。如果到达不了就忽略这个小区。

初始化距离数组用来存储从最近的垃圾回收站到每个点的最短距离，初始值为-1表示未访问。

创建队列用于BFS。将所有起点的位置加入队列，并初始化这些位置的距离为0。加入队列是因为需要作为起点来进行BFS。

部分核心代码：

from collections import deque

d = [[-1 for _ in range(m)] for _ in range(n)]
# 读取网格布局
mp = [list(map(int, input().split())) for _ in range(n)]
q = deque()

# BFS
while q:
    sx, sy = q.popleft()
    for dx, dy in dirs: #四个方向的检查
        x, y = sx + dx, sy + dy
        if 0<=x<n and 0<=y<m and d[x][y] == -1 and mp[x][y] != -1:
        d[x][y] = d[sx][sy] + 1
        q.append((x,y))

BFS

数组搜索

跳跃游戏 Ⅲ

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的任一下标处。

注意，不管是什么情况下，你都无法跳到数组之外。

示例 1：

输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3

示例 2：

输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true 
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 0 -> 下标 4 -> 下标 1 -> 下标 3

示例 3：

1
2
3

输入：arr = [3,0,2,1,2], start = 2
输出：false
解释：无法到达值为 0 的下标 1 处。

提示：

1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int cur = q.poll();
                if (cur < 0 || cur >= arr.length) continue;
                if (visited[cur]) continue;
                if (arr[cur] == 0) {
                    return true;
                } 
                visited[cur] = true;
                q.offer(cur + arr[cur]);
                q.offer(cur - arr[cur]);
            }
        }
        return false;
    }
}

BFS的精髓就在于维护一个队列，保存将要进行BFS的节点，还有一个访问数组，记录节点是否被访问过。

Java中的Queue:

具有队列特性的接口，具有先进先出的特点。所有新元素都插入队列的末尾，移除元素都移除队列的头部

public interface Queue<E> extends Collection<E> {
    //往队列插入元素，如果出现异常会抛出异常
    boolean add(E e);
    //往队列插入元素，如果出现异常则返回false
    boolean offer(E e);
    //移除队列元素，如果出现异常会抛出异常
    E remove();
    //移除队列元素，如果出现异常则返回null
    E poll();
    //获取队列头部元素，如果出现异常会抛出异常
    E element();
    //获取队列头部元素，如果出现异常则返回null
    E peek();
}

DFS版供学习：

class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        boolean[] visited = new boolean[n];
        return dfs(arr, start, n, visited);
    }
    public boolean dfs(int[] num, int idx, int n, boolean[] visited) {
        if (idx < 0 || idx >= num.length || visited[idx]) {
            return false;
        }
        if (num[idx] == 0) {
            return true;
        }
        int step = num[idx];
        visited[idx] = true;
        return dfs(num, idx + step, n, visited) || dfs(num, idx - step, n, visited);
    }
}

网格图

网格结构比二叉树结构稍微复杂一些，其实是一种简化的图结构。

在二叉树DFS遍历：

void traverse(TreeNode root){
    if (root == null){
        return;
    }
    //访问两个相邻结点：左子结点、右子结点
    traverse(root.left);
    traverse(root.right);
}

二叉树的DFS：访问相邻节点、判断base case

root == null 表示root指向的子树为空，不需要再往下遍历了，另一方面可以让后面的root.left和root.right操作不会出现空指针异常。

而对于网格上的格子，将会有四个相邻节点。而网格中DFS的base case就是网格中不需要继续遍历、超出网格范围的格子。

避免重复遍历

网格结构和二叉树最大的不同就在于遍历中可能会遇到遍历过的节点，因为网格结构本质上是一个图，并且是双向的。所以DFS有可能会死循环。

所以就需要标记已经遍历过的格子。

一般用0，1，2来区分。

DFS

主要应用：找连通块、判断是否有环

dfs函数的形参：保存图信息的数组，保存访问信息的数组，开始dfs的行、列

boolean[] visited = new boolean[节点个数];

1971.寻找图中是否存在路径

这里给出的是双向边数组，为了方便进行dfs，一开始考虑创建一个数组存放各边的连接关系。但题解提供的是ArrayList

List<Integer>[] adj = new List[n];
for(int i = 0;i<n;i++){
    //对每一个节点创建一个新的ArrayList，用于存储与节点i相邻的其他节点的编号
    adj[i] = new ArrayList<Integer>();
}

与其他数据结构比较：

如果使用简单的数组来表示邻接关系，可能会面临以下问题：

数组的大小需要预先确定，并且在图的大小动态变化时不太方便。

对于稀疏图（即大多数节点之间没有连接），使用数组会浪费大量的空间。

使用Map<Integer, List<Integer>>也可以表示邻接关系，但可能会稍微复杂一些：

在代码实现上可能会更繁琐，需要处理键值对的操作。

对于简单的图遍历问题，使用数组的方式可能更加直观和高效。

所以对于边(x,y)，只需要 adj[x].add(y)即可。

797.所有可能的路径

List<List<Integer>> list = new ArrayList<>();//保存全部路径
List<Integer> innerlist = new ArrayList<>();//保存单条路径
//上面两个都设置为了全局变量
list.add(new ArrayList<>(innerlist));

开始的理解是直接 list.add(innerlist);，但这样会得到错误答案。原因：Java中的对象是通过引用进行传递的，当执行这行代码时，实际上是将innerList的引用添加到了外层的list中。这意味着如果后续对innerList进行修改，那么外层列表中存储的这个引用的对象也会发生变化。所以，我们希望添加到外层列表中的是一个独立的副本，而不是原始列表的引用，这样可以确保在后续对原始列表进行修改时，不会影响已经添加到外层列表中的内容。

因为需要查找的是所有可能的路径，那么就需要进行回溯。

dfs(graph, graph[n][i]);
//ArrayList的remove()方法传入整数会被作为下标
innerlist.remove(innerlist.size() - 1);
//删除刚刚加入的最后一个节点

移除最后一个节点，以便从另一个相邻节点开始探索。

Miraisen

LeetCode图篇

最短路