Graph
Graph 类似于LinkedList的概念，内存中不一定连续的数据，由各个节点的Reference串起来构成。
- 大概有环
- 分为无向图和有向图
- 没有固定入口
- 大概有多个入口
Graph Representation
图该以什么情势存储？最常用的两大类
- Adjacency Matrix
- Adjacency List
BFS(Breadth-First Search)
以层为概念的搜索方式。由于是程度睁开全部的nodes，以是得当寻找最短路径图大概有环，必要查重。
BFS模板
1，init a Queue with all starting points, a HashSet to record visited nodes
2，While queue is not empy
a. Retrieve current queue size as number of nodes in the current level
b. for each node in current level
> poll out one node
> if this is the node we want, return it
> Offer all its neighbor to the queue if not visited and valid
c. Increase level
实例
/*给你一个由'1'（陆地）和 '0'（水）构成的的二维网格，请你盘算网格中岛屿的数量。岛屿总是被水困绕，而且每座岛屿只能由程度方向和/或竖直方向上相邻的陆地毗连形成。别的，你可以假设该网格的四条边均被水困绕。示例 1：输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]输出：1示例 2：输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]]输出：3提示：m == grid.lengthn == grid.length1 <= m, n <= 300grid[j] 的值为 '0' 或 '1' */public class LeetCode200 { public static void main(String[] args) { char[][] grid = { {'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'} }; Solution solution = new Solution(); System.out.println(solution.numIslands(grid)); } /* 广度优先搜索同样地，我们也可以使用广度优先搜索代替深度优先搜索。为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则将其加入队列，开始举行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。直到队列为空，搜索竣事。最终岛屿的数量就是我们举行广度优先搜索的次数。 */ static class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int nr = grid.length; int nc = grid[0].length; int num_islands = 0; for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { ++num_islands; grid[r][c] = '0'; Queue<Integer> neighbors = new LinkedList<>(); neighbors.add(r * nc + c); while (!neighbors.isEmpty()) { int id = neighbors.remove(); int row = id / nc; int col = id % nc; if (row - 1 >= 0 && grid[row - 1][col] == '1') { neighbors.add((row - 1) * nc + col); grid[row - 1][col] = '0'; } if (row + 1 < nr && grid[row + 1][col] == '1') { neighbors.add((row + 1) * nc + col); grid[row + 1][col] = '0'; } if (col - 1 >= 0 && grid[row][col - 1] == '1') { neighbors.add(row * nc + col - 1); grid[row][col - 1] = '0'; } if (col + 1 < nc && grid[row][col + 1] == '1') { neighbors.add(row * nc + col + 1); grid[row][col + 1] = '0'; } } } } } return num_islands; } }}深度优先
static class Solution2 { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int nr = grid.length; int nc = grid[0].length; int num_islands = 0; for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { ++num_islands; dfs(grid, r, c); } } } return num_islands; } /* 深度优先 */ void dfs(char[][] grid, int r, int c) { int nr = grid.length; int nc = grid[0].length; if (r < 0 || c < 0 || r >= nr || c >= nc || 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); } }/*给定一个由 0 和 1 构成的矩阵 mat，请输出一个巨细类似的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的距离为 1 。示例 1：输入：mat = [[0,0,0],[0,1,0],[0,0,0]]输出：[[0,0,0],[0,1,0],[0,0,0]]示例 2：输入：mat = [[0,0,0],[0,1,0],[1,1,1]]输出：[[0,0,0],[0,1,0],[1,2,1]]提示：m == mat.lengthn == mat.length1 <= m, n <= 1041 <= m * n <= 104mat[j] is either 0 or 1.mat 中至少有一个 0 */public class LeetCode542 { public static void main(String[] args) { System.out.println(Arrays.deepToString(new Solution().updateMatrix(new int[][]{{0, 0, 0}, {0, 1, 0}, {1, 1, 1}}))); System.out.println(Arrays.deepToString(new Solution2().updateMatrix(new int[][]{{0, 0, 0}, {0, 1, 0}, {1, 1, 1}}))); } /* 广度优先 */ static class Solution { int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public int[][] updateMatrix(int[][] matrix) { int m = matrix.length, n = matrix[0].length; int[][] dist = new int[m][n]; boolean[][] seen = new boolean[m][n]; Queue<int[]> queue = new LinkedList<int[]>(); // 将全部的 0 添加进初始队列中 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[j] == 0) { queue.offer(new int[]{i, j}); seen[j] = true; } } } // 广度优先搜索 while (!queue.isEmpty()) { int[] cell = queue.poll(); int i = cell[0], j = cell[1]; for (int d = 0; d < 4; ++d) { int ni = i + dirs[d][0]; int nj = j + dirs[d][1]; if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) { dist[ni][nj] = dist[j] + 1; queue.offer(new int[]{ni, nj}); seen[ni][nj] = true; } } } return dist; } } /* 动态规划 */ static class Solution2 { public int[][] updateMatrix(int[][] matrix) { int m = matrix.length, n = matrix[0].length; // 初始化动态规划的数组，全部的距离值都设置为一个很大的数 int[][] dist = new int[m][n]; for (int i = 0; i < m; ++i) { Arrays.fill(dist, Integer.MAX_VALUE / 2); } // 如果 (i, j) 的元素为 0，那么距离为 0 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[j] == 0) { dist[j] = 0; } } } // 只有 程度向左移动 和 竖直向上移动，留意动态规划的盘算次序 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (i - 1 >= 0) { dist[j] = Math.min(dist[j], dist[i - 1][j] + 1); } if (j - 1 >= 0) { dist[j] = Math.min(dist[j], dist[j - 1] + 1); } } } // 只有 程度向左移动 和 竖直向下移动，留意动态规划的盘算次序 for (int i = m - 1; i >= 0; --i) { for (int j = 0; j < n; ++j) { if (i + 1 < m) { dist[j] = Math.min(dist[j], dist[i + 1][j] + 1); } if (j - 1 >= 0) { dist[j] = Math.min(dist[j], dist[j - 1] + 1); } } } // 只有 程度向右移动 和 竖直向上移动，留意动态规划的盘算次序 for (int i = 0; i < m; ++i) { for (int j = n - 1; j >= 0; --j) { if (i - 1 >= 0) { dist[j] = Math.min(dist[j], dist[i - 1][j] + 1); } if (j + 1 < n) { dist[j] = Math.min(dist[j], dist[j + 1] + 1); } } } // 只有 程度向右移动 和 竖直向下移动，留意动态规划的盘算次序 for (int i = m - 1; i >= 0; --i) { for (int j = n - 1; j >= 0; --j) { if (i + 1 < m) { dist[j] = Math.min(dist[j], dist[i + 1][j] + 1); } if (j + 1 < n) { dist[j] = Math.min(dist[j], dist[j + 1] + 1); } } } return dist; } }} |
