leetcode 图论专题——(dfs+bfs+并查集回顾)

DFS、BFS

回顾（C语言代码）
map[i][j]里记录的是i点和j点的连接关系

基本DFS：

int vis[101],n,map[101][101];
void dfs(int t)
{int i;vis[t]=1;for(i=0;i<n;i++)//找对t点所有有关联的点——“找路”{if(vis[i]!=0&&map[t][i]==1)//有连接边的点且没访问过{printf(" %d",i);dfs(i);}}
}
dfs(0);

通过BFS找从起点到终点的最短步数

int n;
int map[1001][1001],vis[1001];
int quee[1001];//用个队列存着与当前点有连接边的点
int num[1001];//bfs下起点到各个点的步数
void bfs(int t)
{memset(vis,0,sizeof(vis));memset(num,1061109567,sizeof(num));memset(quee,0,sizeof(quee));int k,kk,i;k=0;kk=0;num[t]=0;//n到n 为0步quee[k++]=t;//在队列中放入起点vis[t]=1;while(kk<k)//队列不为空{int now=quee[kk++];//依次拿出队列中的节点for(i=1; i<=n; i++)//找路{if(vis[i]==0&&map[now][i]==1)//当前结点与i结点连通 && 没有遍历过{quee[k++]=i;vis[i]=1;		if(num[now]<num[i])//当前now点到i点距离更短，那就在num[now]的基础上+1num[i]=num[now]+1;}}}if(num[n]==1061109567)//起点到终点距离是inf，说明到不了printf("NO\n");else printf("%d\n",num[n]);
}

在二维图迷宫里从起点到终点的路径数（dfs）

（这题需要注意的是，每次移动并不总是向着接近终点的放心走，可以在不重复的前提下乱窜，所以导致有很多条路）

int n,m,num;
int map[11][11],vis[11][11];
void dfs(int x,int y)
{int i,tx,ty;int next[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//下上右左 4种移动方式vis[x][y]=1;if(x==n&&y==m){num++;//每次到终点计数return ;}for(i=0;i<4;i++)//与for(0,n)一样都是去判断相连的点即“找路”{tx=x+next[i][0];//每次移动ty=y+next[i][1];if(tx<1||tx>n||ty<1||ty>m)//是否越界{continue;}if(vis[tx][ty]==0&&map[tx][ty]==0)//当前点可以走且没走过{vis[tx][ty]=1;dfs(tx,ty);vis[tx][ty]=0;//释放}}
}dfs(1,1);//起点(1,1) 终点(n,m)

在二维图里从起点到终点的最短步数（bfs）

struct node
{int x,y,time;
} quee[101],now,t;//队列要记录xy坐标和到这点的步数
char map[16][16];
int n,m,vis[16][16];
void bfs(int x0,int y0)
{int i,k,kk;int next[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};memset(quee,0,sizeof(quee));vis[x0][y0]=1;t.x=x0;t.y=y0;t.time=0;quee[0]=t;//起点信息放队列k=1;kk=0;while(kk<k){now=quee[kk++];if(map[now.x][now.y]=='Y')//到终点{printf("%d\n",now.time);return ;}for(i=0; i<4; i++)//二维找路{t.x=now.x+next[i][0];t.y=now.y+next[i][1];if(t.x<0||t.x>=n||t.y<0||t.y>=m){continue;}if(vis[t.x][t.y]==0&&map[t.x][t.y]!='#')//可以通行{t.time=now.time+1;quee[k++]=t;vis[t.x][t.y]=1;}}}printf("-1\n");
}bfs(i1,j1);//起点传进去

java-简单并查集类

单维点

class UnionFind {private int[] parent;//记录祖先节点是谁private int[] rank;//统计此节点做了几次祖先了public UnionFind(int n) {//初始化parent = new int[n];//new空间for (int i = 0; i < n; i++) {parent[i] = i;//先让所有点的祖先是自己}rank = new int[n];}public void union(int x, int y) {//合并int rootx = find(x);int rooty = find(y);if (rootx != rooty) {//谁rank大谁做祖先if (rank[rootx] > rank[rooty]) {parent[rooty] = rootx;} else if (rank[rootx] < rank[rooty]) {parent[rootx] = rooty;} else {parent[rooty] = rootx;rank[rootx]++;}}}public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);//找到并和祖先直接相连}return parent[x];//返回祖先}
}

二维图，点由（x,y）坐标组成

class UnionFind {int[] parent;int[] rank;public UnionFind(char[][] grid) {//初始化count = 0;int m = grid.length;int n = grid[0].length;parent = new int[m * n];rank = new int[m * n];for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == '1') {parent[i * n + j] = i * n + j;//将坐标(i,j)以数组下标的形式}rank[i * n + j] = 0;}}}public int find(int i) {if (parent[i] != i)parent[i] = find(parent[i]);return parent[i];}public void union(int x, int y) {int rootx = find(x);int rooty = find(y);if (rootx != rooty) {if (rank[rootx] > rank[rooty]) {parent[rooty] = rootx;} else if (rank[rootx] < rank[rooty]) {parent[rootx] = rooty;} else {parent[rooty] = rootx;rank[rootx]++;}}}}

leetcode

200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例：
输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3

关键：通过基础二维图dfs遍历图

class Solution {int[][] vis=new int[303][303];int n,m;void dfs(char[][] map,int x,int y){int i,tx,ty;int[][] next={{1,0},{-1,0},{0,1},{0,-1}};//下上右左 4种移动方式vis[x][y]=1;for(i=0;i<4;i++){tx=x+next[i][0];ty=y+next[i][1];if(tx<0||tx>=n||ty<0||ty>=m){continue;}if(vis[tx][ty]==0&&map[tx][ty]=='1'){vis[tx][ty]=1;dfs(map,tx,ty);}}}public int numIslands(char[][] grid) {n=grid.length;m=grid[0].length;int cnt=0;//对图中所有没访问过的点做dfsfor(int i=0;i<n;i++){for(int j=0;j<m;j++){if(vis[i][j]==0&&grid[i][j]=='1'){dfs(grid,i,j);cnt++;//每次从新起点开始dfs就是一个独立的岛屿}}}return cnt;}
}

还可以并查集，将相邻且为1的在并查集里合并，最后统计由几个祖先节点。

1559. 二维网格图中探测环

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在相同值形成的环。
一个环是一条开始和结束于同一个格子的长度大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有相同的值。
同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。
如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。
示例：
在这里插入图片描述
输入：grid = [[“c”,“c”,“c”,“a”],[“c”,“d”,“c”,“c”],[“c”,“c”,“e”,“c”],[“f”,“c”,“c”,“c”]]
输出：true

class Solution {int[][] vis = new int[505][505];int flag;int n,m;void dfs(char[][] map,int x,int y,int xx,int yy)//x,y是当前点坐标
{                                 //xx,yy是x,y,前一步点的坐标vis[x][y]=1;if(flag==1) return ;/* (x,y)向上下左右移动 */if(x-1>=0&&map[x-1][y]==map[x][y]) //向上存在且同色{if(vis[x-1][y]==1&&(x-1!=xx||y!=yy)) 通过下一步(x-1,y)不是上一步(xx,yy)，但这个下一步曾经走过，就说明成环了{                                  flag=1;}else if(vis[x-1][y]==0)  //没形成环就继续遍历dfs(map,x-1,y,x,y);}if(y+1<m&&map[x][y+1]==map[x][y])//向右存在且同色{if(vis[x][y+1]==1&&(x!=xx||y+1!=yy)){flag=1;}else if(vis[x][y+1]==0)dfs(map,x,y+1,x,y);}if(x+1<n&&map[x+1][y]==map[x][y])//向下存在且同色{if(vis[x+1][y]==1&&(x+1!=xx||y!=yy)){flag=1;}else if(vis[x+1][y]==0)dfs(map,x+1,y,x,y);}if(y-1>=0&&map[x][y-1]==map[x][y])//向左存在且同色{if(vis[x][y-1]==1&&(x!=xx||y-1!=yy)){flag=1;}else if(vis[x][y-1]==0)dfs(map,x,y-1,x,y);}
}public boolean containsCycle(char[][] grid) {flag=0;n=grid.length;m=grid[0].length;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(vis[i][j]==0)//对每个没访问过的点都进行成环dfs测试{dfs(grid,i,j,i,j);}if(flag==1)break;}if(flag==1) break;}if(flag==1)return true;else return false;}
}