图论07

编程入门行业动态更新时间:2024-10-20 03:38:05

图论07

文章目录

二维数组映射一维数组
一维数组映射二维数组
四联通
- 例题-力扣695. 岛屿的最大面积
- - C++ - 不创建图
  - Java - 创建图，dfs的时候只需要传入顶点
  - Java - 不创建图，dfs传入当前坐标，并且需要各个方向进行遍历
  - 并查集 --待完善
八联通
- 例题-力扣1091. 二进制矩阵中的最短路径
- - C++解法
  - Java解法

二维数组映射一维数组

所有的索引都是从(0, 0)开始的，将二维的坐标映射到一维

(2, 1) --> 2 *列数+1
(x, y) --> x *列数+y

一维数组映射二维数组

假设列数有13列，求一维数组索引为27的数映射到二维数组中的位置

27-->行索引: 27/13=2-->列索引: 27%13=1v-->行索引: v/列数-->列索引: v%列数

四联通

设立4*2的二维数组directions,数字代表相对于当前坐标的位移。
第一维代表纵向，第二维代表横向。
向上和左均为负方向。向下和右均为负方向。

dirs = [[-1,0],  [0,1],[1,0],[0,-1]]
dirs = [   上 ,  右 ,  左 ,   下 ]

(0,0) | (0,1)| (0,2)
(1,0) |(1,1)| (1,2)
(2,0) |(2,1)| (2,2)

//对于x和y，d代表directions里的行数for(d=0; d<4: d++){next_x = x + dirs[d][0];next_y = y + dirs[d][1];
...
}

例题-力扣695. 岛屿的最大面积

C++ - 不创建图

class Solution {
public:const vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//设置变量记录整个图的陆地最大面积int res = 0;//全局变量当前联通分量的最大陆地面积int count = 0;//设置访问数组vector<vector<int>> visited;int maxAreaOfIsland(vector<vector<int>>& grid) {//定义并计算图的行数和列数int row = grid.size(), col = grid[0].size();//初始化visited数组visited.assign(row, vector<int>(col, 0));//遍历地图for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {//如果当前节点是陆地并且没有被访问过if (grid[i][j] && !visited[i][j]) {//当前联通分量的最大陆地面积count = 0; //每个联通分量重新计数，并跟全局的最大面积作比较dfs(grid, row, col, i, j);if (count > res) res = count;}}}return res;}void dfs(vector<vector<int>>& grid, int row, int col, int i, int j) {count++; //陆地面积+1visited[i][j] = 1;for (auto dir : dirs) {int x = i + dir[0];int y = j + dir[1];if (x >= 0 && x < row && y >= 0 && y < col && grid[x][y] && !visited[x][y]) {dfs(grid, row, col, x, y);}}}
};

Java - 创建图，dfs的时候只需要传入顶点

// Java-Leetcode 695
import java.util.HashSet;class Solution {private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};private int R, C; //计算行数和列数private int[][] grid;private HashSet<Integer>[] G;private boolean[] visited;public int maxAreaOfIsland(int[][] grid){if(grid == null) return 0;//计算行数R = grid.length;if(R == 0) return 0;//计算列数C = grid[0].length;if(C == 0) return 0;this.grid = grid;//建图G = constructGraph();//初始化返回值，记录最大的陆地值int res = 0; //初始化访问数组，记录访问过的顶点的信息visited = new boolean[G.length];//遍历图中的所有顶点，找到最大的陆地值for(int v = 0; v < G.length; v ++){//获取当前坐标信息int x = v / C, y = v % C;//是陆地，并且还未访问过；水的格子不用考虑if(grid[x][y] == 1 && !visited[v])//从当前顶点出发进行dfs，计算所有联通分量相连的所有顶点数的最大值res = Math.max(res, dfs(v));}return res;}private int dfs(int v){visited[v] = true;int res = 1; //遍历到当前顶点并且没有被遍历过，当前的顶点陆地面积为1for(int w: G[v])if(!visited[w])res += dfs(w);//迭代增加陆地面积return res;}//建图private HashSet<Integer>[] constructGraph(){//创建HashSet，HashSet是基于HashMap实现的一个单列存储的集合类HashSet<Integer>[] g = new HashSet[R * C];for(int i = 0; i < g.length; i ++)g[i] = new HashSet<>();//遍历图中的所有顶点for(int v = 0; v < g.length; v ++){//获取当前坐标int x = v / C, y = v % C;//如果当前坐标是1，表示当前是陆地if(grid[x][y] == 1){//判断上下左右是否跟陆地相连for(int d = 0; d < 4; d ++){//重新计算坐标int nextx = x + dirs[d][0];int nexty = y + dirs[d][1];//inArea(nextx, nexty) -- 边界判断if(inArea(nextx, nexty) && grid[nextx][nexty] == 1) {//获得在一维数组中的坐标int next = nextx * C + nexty;//无向图，把当前坐标添加到哈希set中，相互关联g[v].add(next);g[next].add(v);}}}}return g;}//判断二维索引的合法范围private boolean inArea(int x, int y){return x >= 0 && x < R && y >= 0 && y < C;}public static void main(String[] args){int[][] grid = {{0, 1}};System.out.println((new Solution()).maxAreaOfIsland(grid));}
}

Java - 不创建图，dfs传入当前坐标，并且需要各个方向进行遍历

/// Leetcode 695class Solution2 {private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};private int R, C;private int[][] grid;private boolean[][] visited;public int maxAreaOfIsland(int[][] grid){if(grid == null) return 0;R = grid.length;if(R == 0) return 0;C = grid[0].length;if(C == 0) return 0;this.grid = grid;visited = new boolean[R][C];int res = 0;for(int i = 0; i < R; i ++)for(int j = 0; j < C; j ++)if(grid[i][j] == 1 && !visited[i][j])res = Math.max(res, dfs(i, j));return res;}private int dfs(int x, int y){visited[x][y] = true;int res = 1;for(int d = 0; d < 4; d ++){int nextx = x + dirs[d][0], nexty = y + dirs[d][1];if(inArea(nextx, nexty) && grid[nextx][nexty] == 1 && !visited[nextx][nexty])res += dfs(nextx, nexty);}return res;}private boolean inArea(int x, int y){return x >= 0 && x < R && y >= 0 && y < C;}
}

并查集 --待完善

八联通

设立4*2的二维数组directions,数字代表相对于当前坐标的位移。
第一维代表纵向，第二维代表横向。
向上和左均为负方向。向下和右均为负方向。

dirs = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};dirs = {{-1,0},  --上{1,0},   --下{0,-1},  --左{0,1},   --右{-1,-1}, --左上{-1,1},  --右上{1,-1},  --左下{1,1}};  --右下

(0,0) | (0,1)| (0,2)
(1,0) |(1,1)| (1,2)
(2,0) |(2,1)| (2,2)

//对于x和y，d代表directions里的行数for(d=0; d<8: d++){next_x = x + dirs[d][0];next_y = y + dirs[d][1];
...
}

例题-力扣1091. 二进制矩阵中的最短路径

C++解法

class Solution {public:const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};int shortestPathBinaryMatrix(vector<vector<int>>& grid) {// 特殊情况，只有一个格子并且阻塞if(grid[0][0] == 1) return -1;int col = grid.size(), row = grid[0].size();// 初始化visited向量vector<vector<int>> visited(col, vector<int>(row, 0));// 开始访问visited[0][0] = 1;        int path = 1;queue<int> q;q.push(0);while(!q.empty()){// sz控制队列中顶点数量，表示与当前顶点相邻的顶点数量int sz = q.size();// 遍历与当前顶点相邻的所有顶点，寻找出口for(int i = 0;i < sz;++i){// cur是顶底映射到一维数组的索引int cur = q.front(); // 对头出队，如果从当前队头找到了路径直接退出循环，否则添加完周围相邻的顶点后，继续遍历q.pop();// 出口：到达最后一个位置if(cur == col*row-1) return path;// 求当前顶点在二维数组中的坐标int cur_x = cur / col, cur_y = cur % row;// 遍历与当前顶点相邻的顶点，添加到队列中，重置szfor(int i = 0;i < 8;++i){                    int next_x = cur_x + dir[i][0];int next_y = cur_y + dir[i][1];// 边界合法 || 没有被访问过 || 这条路不能是阻塞的if(valid(next_x, next_y, col) && visited[next_x][next_y] == 0 && grid[next_x][next_y] == 0){// 添加周围相邻的顶点q.push(next_x * col + next_y);visited[next_x][next_y] = 1;}}}++path;}return -1;}    bool valid(int cur_col, int cur_row, int col){return cur_col >= 0 && cur_row >= 0 && cur_col < col && cur_row < col;}};

Java解法

/// Leetcode 1091
import java.util.Queue;
import java.util.LinkedList;class Solution {private int[][] dirs = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1},{1, 0}, {1, -1}, {0, -1}, {-1, -1}};private int R, C;public int shortestPathBinaryMatrix(int[][] grid) {R = grid.length;C = grid[0].length;boolean[][] visited = new boolean[R][C];int[][] dis = new int[R][C];if(grid[0][0] == 1) return -1;if(R == 0 && C == 0) return 1;// BFSQueue<Integer> queue = new LinkedList<>();queue.add(0);visited[0][0] = true;dis[0][0] = 1;while(!queue.isEmpty()){int cur = queue.remove();int curx = cur / C, cury = cur % C;for(int d = 0; d < 8; d ++){int nextx = curx + dirs[d][0];int nexty = cury + dirs[d][1];if(inArea(nextx, nexty) && !visited[nextx][nexty] && grid[nextx][nexty] == 0){queue.add(nextx * C + nexty);visited[nextx][nexty] = true;dis[nextx][nexty] = dis[curx][cury] + 1;if(nextx == R - 1 && nexty == C - 1)return dis[nextx][nexty];}}}return -1;}private boolean inArea(int x, int y){return x >= 0 && x < R && y >= 0 && y < C;}
}