图

图的种类

• 有向图
• 无向图
• 加权图

度

• 度：一个顶点的度是与该顶点相关联的边的条数
• 入度：有向图中，有多少边指向该节点
• 出度：有向图中，该节点指向了多少边

图的存储

• 连通图：在无向图中，任何两个节点都是可以到达的，我们称之为连通图
• 强连通图：在有向图中，任何两个节点是可以相互到达的，我们称之为强连通图

图的表示

• 邻接矩阵：是图的另一种表示方式，它是一个二维数组，其中每个元素表示两个节点之间是否有边。

  • 表达方式简单，易于理解
  • 检查任意两个顶点间是否存在边的操作非常快
  • 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。
  • 遇到稀疏图，会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费

• 邻接表：是图的另一种表示方式，它是一个链表，其中每个节点表示一个顶点，每个节点包含一个指向其他节点的指针。

  • 对于稀疏图的存储，只需要存储边，空间利用率高
  • 遍历节点连接情况相对容易
  • 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
  • 实现相对复杂，不易理解

图的遍历

• 深度优先搜索
• 广度优先搜索

深度优先搜索

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

广度优先搜索

• 需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑。
• 需要一个visited数组防止重复访问，加入队列后立马标记为已访问。

public class Solution {
    // 四个方向：右、下、上、左
    private static final int[][] DIRECTIONS = {
        {0, 1}, {1, 0}, {-1, 0}, {0, -1}
    };

    public void bfs(char[][] grid, boolean[][] visited, int startX, int startY) {
        int m = grid.length; // 行
        int n = grid[0].length; // 列

        Queue<int[]> queue = new LinkedList<>(); // 队列 int[] 表示坐标
        queue.offer(new int[]{startX, startY}); // 起点坐标入队
        visited[startX][startY] = true; // 标记起点已访问

        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 取出当前节点并出队
            int curX = current[0]; // 当前节点x坐标
            int curY = current[1]; // 当前节点y坐标

            for (int[] dir : DIRECTIONS) {
                int nextX = curX + dir[0]; // 下一个节点x坐标
                int nextY = curY + dir[1]; // 下一个节点y坐标

                // 越界检查
                if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) continue; // 越界，跳过这次
                // 是否访问过
                if (!visited[nextX][nextY]) {
                    queue.offer(new int[]{nextX, nextY}); // 下一个节点入队
                    visited[nextX][nextY] = true; // 标记下一个节点已访问
                }
            }
        }
    }
}

岛屿问题

岛屿数量

DFS

• 如果没有访问过并且该节点为陆地，则以该节点为起点进行DFS，将该节点标记为已访问，并递归访问该节点的上下左右四个方向的节点。
• 在DFS过程中，遍历上下左右四个节点，如果没有被访问过并且是陆地，则继续DFS，直到所有陆地都被访问过。如果遇到边界或者水域，则跳过该次循环。

BFS

• 使用队列，参考广度优先搜索的代码，将当前节点加入队列，并标记为已访问。然后遍历当前节点的上下左右四个方向的节点，如果没有被访问过并且是陆地，则继续加入队列，并标记为已访问。直到所有陆地都被访问过。如果遇到边界或者水域，则跳过该次循环。

class Solution {
    public static int[][] dir = {{0,1}, {1,0}, {-1,0}, {0,-1}};

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n]; // 记录是否访问过
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == '1') { // 如果该节点没有访问过并且是陆地，则以该节点为起点进行DFS
                    dfs(grid, visited, i, j);
                    count++;
                }
            }
        }

        return count;
    }

    private void dfs(char[][] grid, boolean[][] visited, int x, int y) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) { // 遍历上下左右四个方向
            int nextX = x + dir[i][0]; // 下一个节点的x坐标
            int nextY = y + dir[i][1]; // 下一个节点的y坐标

            if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length) // 越界，跳过该次循环
                continue;

            if (!visited[nextX][nextY] && grid[nextX][nextY] == '1') { // 如果该节点没有访问过并且是陆地，则以该节点为起点进行DFS
                visited[nextX][nextY] = true; // 标记该节点为已访问
                dfs(grid, visited, nextX, nextY); // 递归访问该节点的上下左右四个方向的节点
            }
        }
    }

    private void bfs(char[][] grid, boolean[][] visited, int x, int y) {
        Queue<int[]> q = new LinkedList<>(); // 队列
        q.offer(new int[]{x,y}); // 起点入队
        visited[x][y] = true; // 标记起点为已访问

        while(!q.isEmpty()){
            int[] cur = q.poll(); // 取出当前节点并出队
            int curX = cur[0]; // 当前节点x坐标
            int curY = cur[1]; // 当前节点y坐标

            for(int[] d:dir){
                int nextX = curX + d[0]; // 下一个节点的x坐标
                int nextY = curY + d[1]; // 下一个节点的y坐标

                if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length){ // 越界，跳过该次循环
                    continue;
                }
                // 没访问过并且是陆地
                if(!visited[nextX][nextY] && grid[nextX][nextY] == '1'){
                    q.offer(new int[]{nextX, nextY}); // 下一个节点入队
                    visited[nextX][nextY] = true; // 标记下一个节点为已访问
                }

            }
        }
    }
}

岛屿最大面积

• 面积是指陆地数量
• 使用DFS，在DFS过程中，记录当前陆地数量，并更新最大面积。最后取max(当前陆地数量, 最大面积)

class Solution {
    int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
    int res = 0;

    public int maxAreaOfIsland(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];

        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                if(!visited[i][j] && grid[i][j] == 1){
                    int area = dfs(grid, visited, i, j);
                    res = Math.max(res, area);
                }
            }
        }
        return res;
    }
    
    private int dfs(int[][] grid, boolean[][] visited, int x, int y){
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) return 0;
        if (visited[x][y] || grid[x][y] == 0) return 0;

        visited[x][y] = true;
        int area = 1; // 当前格子面积
        for(int[] dir : dirs){
            area += dfs(grid, visited, x + dir[0], y + dir[1]);
        }
        return area;
    }
}

岛屿周长

• 两次for循环遍历，不需要DFS和BFS
• 陆地周边是水或者边界，则周长加1

class Solution {
    public int islandPerimeter(int[][] grid) {
        int[][] dir = {{0,1}, {1,0}, {-1,0}, {0,-1}};
        int res = 0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j] == 1){
                    for (int[] d:dir){
                        int nextI = i+d[0];
                        int nextJ = j+d[1];
                        if(nextI<0 || nextJ<0 || nextI>=grid.length || nextJ>=grid[0].length || grid[nextI][nextJ] == 0){ // 越界或者水域，则周长加1
                            res++;
                        } 
                    }
                }
            }
        }
        return res;
    }
}

孤岛总面积

• 四周都是水才算孤岛，如果四周有边界，则不算孤岛
• 思路：
  • 把地图边缘的陆地，以及他们相邻的陆地，全部变成水域0
  • 然后遍历地图，计算陆地数量

沉没孤岛

• 把孤岛变成水域，四周都是水才算孤岛
• 地图边缘的陆地不是孤岛
• 返回整个grid
• 思路：
  • 标记地图边缘的陆地，以及他们相邻的陆地，全部变成2
  • 遍历地图，把所有非0的地方减去1。2变成1，1变成0，0不变
  • 这样孤岛就变成了水域

水流问题 Pacific Atlantic Water Flow

• 从第一组边界上的节点 逆流而上，将遍历过的节点都标记上。
• 同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记上。
• 然后两方都标记过的节点就是既可以流向第一组边界也可以流向第二组边界的节点。

建造最大岛屿

• 把一块水变成陆地，然后计算出最大的可能的岛屿面积
• 思路：
  • 可以记录下所有岛屿的情况，用map
  • 在遍历的时候不需要重复计算，直接从map中获取

class Solution {
    // 定义全局变量
    // 记录每次每个岛屿的面积
    static int count;
    // 对每个岛屿进行标记
    static int mark;
    // 定义二维数组表示四个方位
    static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    // DFS 进行搜索，将每个岛屿标记为不同的数字
    public int largestIsland(int[][] grid) {
        // 初始化mark变量，从2开始（区别于0水，1岛屿）
        int m = grid.length;
        int n = grid[0].length;

        // 定义二位boolean数组记录该位置是否被访问
        boolean[][] visited = new boolean[m][n];

        // 定义一个HashMap，记录某片岛屿的标记号和面积
        HashMap<Integer, Integer> getSize = new HashMap<>();

        // 定义一个HashSet，用来判断某一位置水四周是否存在不同标记编号的岛屿
        HashSet<Integer> set = new HashSet<>();

        // 定义一个boolean变量，看看DFS之后，是否全是岛屿
        boolean isAllIsland = true;

        // 遍历二维数组进行DFS搜索，标记每片岛屿的编号，记录对应的面积
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) isAllIsland = false;
                if (grid[i][j] == 1) {
                    count = 0;
                    dfs(grid, i, j, visited);
                    getSize.put(mark, count);
                    mark++;
                }
            }
        }

        int result = 0;
        if (isAllIsland) result =  m * n;

        // 对标记完的grid继续遍历，判断每个水位置四周是否有岛屿，并记录下四周不同相邻岛屿面积之和
        // 每次计算完一个水位置周围可能存在的岛屿面积之和，更新下result变量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    set.clear();
                    // 当前水位置变更为岛屿，所以初始化为1
                    int curSize = 1;

                    for (int[] dir : dirs) {
                        int curRow = i + dir[0];
                        int curCol = j + dir[1];

                        if (curRow < 0 || curRow >= m || curCol < 0 || curCol >= n) continue;
                        int curMark = grid[curRow][curCol];
                        // 如果当前相邻的岛屿已经遍历过或者HashMap中不存在这个编号，继续搜索
                        if (set.contains(curMark) || !getSize.containsKey(curMark)) continue;
                        set.add(curMark);
                        curSize += getSize.get(curMark);
                    }

                    result = Math.max(result, curSize);
                }
            }
        }
        return result;
    }

    // DFS 进行搜索，将每个岛屿标记为不同的数字
    public static void dfs(int[][] grid, int x, int y, boolean[][] visited) {
        // 当遇到边界，直接return
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return;
        // 遇到已经访问过的或者遇到海水，直接返回
        if (visited[x][y] || grid[x][y] == 0) return;

        visited[x][y] = true;
        count++;
        grid[x][y] = mark;

        // 继续向下层搜索
        dfs(grid, x, y + 1, visited);
        dfs(grid, x, y - 1, visited);
        dfs(grid, x + 1, y, visited);
        dfs(grid, x - 1, y, visited);
    }
}

单词接龙

• 枚举替换一个字母，判断是否在字典中，如果在的话，连接两个节点。最后生成一个无权图
• 使用bfs找到短路径的长度就可以了，不用找出具体路径

class Solution {
    public int ladderLength(String beginStr, String endStr, List<String> wordList) {
        int len = 1;
        Set<String> set = new HashSet<>(wordList); // 使用set判断是否在字典中
        Set<String> visited = new HashSet<>(); // 使用set判断是否访问过
        Queue<String> q = new LinkedList<>();
        visited.add(beginStr);
        q.add(beginStr);
        q.add(null); // 使用null作为分隔符，表示一层结束，下一层开始
        while (!q.isEmpty()) {
            String node = q.remove();
            //上一层结束，若下一层还有节点进入下一层
            if (node == null) {
                if (!q.isEmpty()) {
                    len++;
                    q.add(null);
                }
                continue;
            }
            char[] charArray = node.toCharArray();
            //寻找邻接节点
            for (int i = 0; i < charArray.length; i++) {
                //记录旧值，用于回滚修改
                char old = charArray[i];
                for (char j = 'a'; j <= 'z'; j++) {
                    charArray[i] = j;
                    String newWord = new String(charArray);
                    if (set.contains(newWord) && !visited.contains(newWord)) {
                        q.add(newWord);
                        visited.add(newWord);
                        //找到结尾
                        if (newWord.equals(endStr)) return len + 1;
                    }
                }
                charArray[i] = old;
            }
        }
        return 0;
    }
}

并查集

"并查集" (Union-Find 或 Disjoint Set Union) 是一种数据结构，用来处理一些不相交集合的合并及查询问题。

核心概念

并查集主要支持两个操作：

1. Find（查找）：确定某个元素属于哪个集合
2. Union（合并）：将两个集合合并成一个集合

基本实现

class UnionFind {
    private int[] parent;  // 父节点数组
    private int[] rank;    // 秩（树的高度）
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        // 初始化：每个元素都是自己的父节点
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    // 查找根节点（带路径压缩）
    public int find(int x) {
        if (parent[x] != x) { // 如果父节点不是自己，则递归查找父节点
            parent[x] = find(parent[x]);  // 路径压缩, 防止树的高度过高递归过深, 不需要
        }
        return parent[x]; // 父节点是自己的话直接返回
    }
    
    // 合并两个集合
    public void union(int x, int y) {
        int rootX = find(x); // 找到x的根节点
        int rootY = find(y); // 找到y的根节点
        // 按秩合并
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;           // 矮树连到高树
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;           // 矮树连到高树
        } else {
            parent[rootY] = rootX;           // 同高度时任选一个作根
            rank[rootX]++;                   // 新根高度+1
        }
    }
    
    // 判断两个元素是否在同一集合, 最终父节点相同则说明在同一集合
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

执行示例

假设有5个元素 {0, 1, 2, 3, 4}：

初始状态：
0  1  2  3  4
↑  ↑  ↑  ↑  ↑
每个元素都指向自己

执行 union(0, 1)：
1  1  2  3  4
↑  ↑  ↑  ↑  ↑
0→1

执行 union(2, 3)：
1  1  3  3  4
↑  ↑  ↑  ↑  ↑
0→1    2→3

执行 union(1, 3)：
1  1  3  3  4
↑  ↑  ↑  ↑  ↑
0→1→3  2→3

主要应用场景

1. 连通性问题：判断图中两点是否连通
2. 最小生成树：Kruskal算法中判断是否形成环
3. 朋友圈问题：统计有多少个朋友圈
4. 岛屿数量：统计二维网格中岛屿的数量
5. 账户合并：合并同一人的多个账户

时间复杂度

• 路径压缩 + 按秩合并：几乎是 O(1)
• 准确地说是 O(α(n))，其中 α 是阿克曼函数的反函数，在实际应用中可以认为是常数

经典例题

朋友圈问题：

// 有n个人，friends[i][j] = 1表示i和j是朋友
// 求有多少个朋友圈
public int findCircleNum(int[][] friends) {
    int n = friends.length;
    UnionFind uf = new UnionFind(n);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (friends[i][j] == 1) {
                uf.union(i, j);
            }
        }
    }
    
    // 统计有多少个不同的根节点
    Set<Integer> roots = new HashSet<>();
    for (int i = 0; i < n; i++) {
        roots.add(uf.find(i));
    }
    return roots.size();
}

被围绕的区域

class Solution {
    private static final int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
    private int m, n;

    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        m = board.length;
        n = board[0].length;

        // 标记与边界相连的'O'
        for (int i = 0; i < m; i++) {
            dfs(board, i, 0); // 第一列
            dfs(board, i, n - 1); // 最后一列
        }
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j); // 第一行
            dfs(board, m - 1, j); // 最后一行
        }

        // 替换
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X'; // 被包围的'O'替换
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O'; // 边界连通的'O'恢复
                }
            }
        }
    }

    private void dfs(char[][] board, int x, int y) {
        if (x < 0 || y < 0 || x >= m || y >= n || board[x][y] != 'O') {
            return;
        }
        board[x][y] = '#'; // 标记为临时字符，表示边界或可达边界
        for (int[] d : dir) {
            dfs(board, x + d[0], y + d[1]);
        }
    }
}

克隆图

• DFS+哈希表（如果不对访问过的节点做标记，则会陷入死循环中） | 拷贝方式 | 说明 | 影响 | | ------- | ---------------------------------- | ---------------- | | 浅拷贝 | 复制对象本身，但引用的内部结构（如邻居列表）不复制，而是共享 | 会导致原图和新图互相影响 | | 深拷贝 | 复制对象本身，并且递归地复制对象内部引用的所有对象 | 新旧图完全独立 |

class Solution {
    private HashMap <Node, Node> visited = new HashMap <> (); // key是原图节点，value是克隆图节点
    public Node cloneGraph(Node node) {
        if (node == null) return node;

        // 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表，所以用new ArrayList()
        Node cloneNode = new Node(node.val, new ArrayList<Node>());
        // 哈希表存储
        visited.put(node, cloneNode);

        // 遍历该节点的邻居并更新克隆节点的邻居列表
        for (Node neighbor: node.neighbors) { // 遍历邻居
            cloneNode.neighbors.add(cloneGraph(neighbor)); // 递归克隆邻居
        }
        return cloneNode;
    }
}

课程表

class Solution {
    List<List<Integer>> edges; // 邻接表表示有向图
    int[] visited;             // 标记每个节点访问状态：0=未访问，1=访问中，2=已访问
    boolean valid = true;      // 表示整个图是否有效（无环）

    public boolean canFinish(int numCourses, int[][] prerequisites) { 
        edges = new ArrayList<>(); // 初始化邻接表
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses]; // 初始化访问状态数组
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]); // 建边 先修课 → 目标课（b 指向 a）每个 prerequisites[i] = [a, b] 表示：学 a 之前必须学 b
        }
        // 遍历每个节点，如果未访问，则进行深度优先搜索
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }

    public void dfs(int u) {
        visited[u] = 1; // 标记为访问中
        for (int v: edges.get(u)) {
            if (visited[v] == 0) {
                dfs(v); // 没访问过，继续递归
                if (!valid) { // 检测到图中有环后，后续搜索已经没必要继续了 不会影响结果，但浪费性能
                    return;
                }
            } else if (visited[v] == 1) {
                valid = false; // 如果已经在路径中再次遇到，说明有环
                return;
            }
        }
        visited[u] = 2; // 标记为已访问
    }
}