跳到主要内容

图论算法练习

图论（Graph）题目通常涉及搜索（DFS/BFS）、连通性判断、拓扑排序或特定的数据结构如字典树（Trie）。

200. 岛屿数量 (Number of Islands)​

题目描述​

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

解题思路​

遍历网格。遇到一个 '1' 就开始 DFS 或 BFS 将所有连通的 '1' 置为 '0'（或者 visited），每启动一次搜索岛屿数量加一。

Java 代码实现​

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j); count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') return;
        grid[r][c] = '0';
        dfs(grid, r + 1, c); dfs(grid, r - 1, c);
        dfs(grid, r, c + 1); dfs(grid, r, c - 1);
    }
}

994. 腐烂的橘子 (Rotting Oranges)​

题目描述​

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：0 代表空单元格；1 代表新鲜橘子；2 代表腐烂橘子。每分钟，腐烂的橘子周围四个方向的新鲜橘子都会腐烂。 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

解题思路​

典型的多源 BFS。

  1. 首先将所有初始腐烂的橘子坐标加入队列，并统计新鲜橘子的总数。
  2. 每一层 BFS 深度代表一分钟。
  3. 检查最后新鲜橘子是否清零。

Java 代码实现​

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length, fresh = 0;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) queue.add(new int[]{i, j});
                else if (grid[i][j] == 1) fresh++;
            }
        }
        if (fresh == 0) return 0;
        int time = 0;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!queue.isEmpty()) {
            time++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] p = queue.poll();
                for (int[] d : dirs) {
                    int nx = p[0] + d[0], ny = p[1] + d[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2; fresh--; queue.add(new int[]{nx, ny});
                    }
                }
            }
            if (fresh == 0) return time;
        }
        return -1;
    }
}

207. 课程表 (Course Schedule)​

题目描述​

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。有些课程在修前置课后才能修。请你判断是否可能完成所有课程的学习？

解题思路​

拓扑排序。

  1. 建立入度表（indegree）和邻接表。
  2. 将所有入度为 0 的节点放入队列。
  3. 遍历队列，每次取出一个节点，将其对应的邻居节点的入度减一。若某个邻居入度变为 0，加入队列。
  4. 如果最后被处理的课程数等于总门数，则说明没有环，可以完成。

Java 代码实现​

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        List<List<Integer>> adjacency = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adjacency.add(new ArrayList<>());
        for (int[] cp : prerequisites) {
            indegrees[cp[0]]++; adjacency.get(cp[1]).add(cp[0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indegrees[i] == 0) queue.add(i);
        while (!queue.isEmpty()) {
            int pre = queue.poll(); numCourses--;
            for (int cur : adjacency.get(pre)) {
                if (--indegrees[cur] == 0) queue.add(cur);
            }
        }
        return numCourses == 0;
    }
}

208. 实现 Trie (前缀树) (Implement Trie Prefix Tree)​

题目描述​

Trie（发音为 "try"）或前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

解题思路​

每个节点包含 26 个子节点的指针（对应小写字母）和一个 isEnd 布尔标签。

  • 插入时逐个遍历单词字符，沿树向下走，如没有对应子节点则创建。
  • 查找前缀或单词同理。

Java 代码实现​

class Trie {
    private Trie[] children;
    private boolean isEnd;
    public Trie() {
        children = new Trie[26]; isEnd = false;
    }
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) node.children[idx] = new Trie();
            node = node.children[idx];
        }
        node.isEnd = true;
    }
    public boolean search(String word) {
        Trie node = prefix(word);
        return node != null && node.isEnd;
    }
    public boolean startsWith(String prefix) {
        return prefix(prefix) != null;
    }
    private Trie prefix(String s) {
        Trie node = this;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
}