阿狗工具
算法-Graph图BFS广度优先与深度优先搜索
2024-04-09 16:50:04 阅读数 543
Graph
Graph 类似于LinkedList的概念，内存中不一定连续的数据，由各个节点的Reference串起来组成。
- 可能有环
- 分为无向图和有向图
- 没有固定入口
- 可能有多个入口
Graph Representation
图该以什么形式存储？最常用的两大类
- Adjacency Matrix
-
Adjacency List
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.length
n == grid[i].length
1 <= m, n <= 300
grid[i][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.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][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[i][j] == 0) {
queue.offer(new int[]{i, j});
seen[i][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[i][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[i], Integer.MAX_VALUE / 2);
}
// 如果 (i, j) 的元素为 0，那么距离为 0
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
dist[i][j] = 0;
}
}
}
// 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i - 1 >= 0) {
dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
}
if (j - 1 >= 0) {
dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
}
}
}
// 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序
for (int i = m - 1; i >= 0; --i) {
for (int j = 0; j < n; ++j) {
if (i + 1 < m) {
dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
}
if (j - 1 >= 0) {
dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
}
}
}
// 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序
for (int i = 0; i < m; ++i) {
for (int j = n - 1; j >= 0; --j) {
if (i - 1 >= 0) {
dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
}
if (j + 1 < n) {
dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
}
}
}
// 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (i + 1 < m) {
dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
}
if (j + 1 < n) {
dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
}
}
}
return dist;
}
}
}