图论题总结

hot100

岛屿数量

题目链接：
200.岛屿数量
代码：

class Solution {boolean[][] visited;int[][] move = {{0,1},{0,-1},{1,0},{-1,0}};public void bfs(char[][] grid, int i, int j){Queue<int[]> deque = new LinkedList<>();deque.offer(new int[]{i,j});visited[i][j] = true;while(!deque.isEmpty()){int[] curr = deque.poll();int m = curr[0];int n = curr[1];for (int index = 0; index < 4; index ++){int nexti = m + move[index][0];int nextj = n + move[index][1];if (nexti < 0 || nexti >= grid.length || nextj < 0 || nextj >= grid[0].length) continue;if (!visited[nexti][nextj] && grid[nexti][nextj] == '1'){deque.offer(new int[]{nexti,nextj});visited[nexti][nextj] = true;}}} }public int numIslands(char[][] grid) {int res = 0;visited = new boolean[grid.length][grid[0].length];for (int i = 0; i < grid.length; i ++){for (int j = 0; j < grid[0].length; j ++){if (grid[i][j] == '1' && !visited[i][j]){res ++;bfs(grid,i,j);}}}return res;}
}

腐烂的橘子

题目链接：
994.腐烂的橘子
代码：

class Solution {int[][] move = {{0,1},{0,-1},{1,0},{-1,0}};public int orangesRotting(int[][] grid) {int row = grid.length, col = grid[0].length;Queue<int[]> queue = new LinkedList<>();Map<int[], Integer> depth = new HashMap<>();for (int r = 0; r < row; r ++) {for (int c = 0; c < col; c ++) {if (grid[r][c] == 2) {int[] code = new int[]{r,c};queue.offer(code);depth.put(code, 0);}}}int ans = 0;while (!queue.isEmpty()) {int[] curr = queue.poll();int m = curr[0];int n = curr[1];for (int k = 0; k < 4; k ++) {int next_m = m + move[k][0];int next_n = n + move[k][1];if (0 <= next_m && next_m < row && 0 <= next_n && next_n < col && grid[next_m][next_n] == 1) {grid[next_m][next_n] = 2;int[] next_code = new int[]{next_m,next_n};queue.offer(next_code);depth.put(next_code, depth.get(curr) + 1);ans = depth.get(next_code);}}}for (int r = 0; r < row; r ++) {for (int c = 0; c < col; c ++) {if (grid[r][c] == 1) {return -1;}}}return ans;}
}

课程表

题目链接：
207.课程表
代码：

class Solution {List<List<Integer>> edges;boolean valid = true;int[] visited;public void dfs(int i){visited[i] = 1;for (int edge:edges.get(i)){if (visited[edge] == 0){dfs(edge);if (! valid) return;}else if (visited[edge] == 1){valid = false;return;}}visited[i] = 2;}public boolean canFinish(int numCourses, int[][] prerequisites) {edges = new ArrayList<>();for (int i = 0; i < numCourses; i ++){edges.add(new ArrayList<>());}for (int[] item : prerequisites){edges.get(item[1]).add(item[0]);}visited = new int[numCourses];for (int i = 0; i < numCourses; i ++){if (visited[i] == 0){dfs(i);}}return valid;}
}

实现 Trie (前缀树)

题目链接：
208.实现 Trie (前缀树)
代码：

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