当前位置：首页 > news >正文

Hot100中的：图论专题

news 2026/5/12 0:24:21

图模板

图分为有向图和无向图，入度是指向当前节点的边数，出度是当前节点指向其他节点的边数

200.岛屿数量

关键信息一句话总结：

遍历网格，遇到陆地就用 DFS / BFS 把整块连通陆地淹掉，并计数

方法1：BFS

classSolution{publicintnumIslands(char[][]grid){// bfs是这样的 联想我们之前的二叉树// bfs一层一层是左右节点延申出去的// 而这里的图是上下左右四个方向表示一层，所以bfs可以一层一层intm=grid.length;intn=grid[0].length;intcount=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]=='1'){bfs(grid,i,j);count++;}}}returncount;}privatevoidbfs(char[][]grid,inti,intj){intm=grid.length;intn=grid[0].length;Queue<int[]>queue=newLinkedList<>();queue.offer(newint[]{i,j});grid[i][j]='0';while(!queue.isEmpty()){int[]cur=queue.poll();intx=cur[0];inty=cur[1];int[][]dirs={{1,0},{-1,0},{0,1},{0,-1}};for(int[]d:dirs){intnx=x+d[0];intny=y+d[1];if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]=='1'){queue.offer(newint[]{nx,ny});grid[nx][ny]='0';}}}}}

方法2：DFS

classSolution{publicintnumIslands(char[][]grid){intcount=0;intm=grid.length;intn=grid[0].length;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]=='1'){dfs(grid,i,j);count++;}}}returncount;}privatevoiddfs(char[][]grid,inti,intj){intm=grid.length;intn=grid[0].length;if(i>=m||i<0||j>=n||j<0||grid[i][j]=='0'){return;}// 把当前陆地淹没grid[i][j]='0';// 四个方向搜索dfs(grid,i-1,j);dfs(grid,i,j+1);dfs(grid,i+1,j);dfs(grid,i,j-1);}}

方法3：并查集

1.什么是并查集

并查集 = 用来判断两个东西是不是在同一个集合里，它解决了判断这两个点是不是连在一起的问题

classSolution{publicintnumIslands(char[][]grid){intm=grid.length;intn=grid[0].length;UnionFinduf=newUnionFind(m*n);intcount=0;// 1.统计所有'1'for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]=='1'){count++;}}}// 2.合并相邻的'1'for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]=='1'){// 有i行 每行n个 所以 i * n 在j列 所以 i * n + j 二维变一维intindex=i*n+j;// 向下和向右已经包括了所有的覆盖情况 因为我们是从高到低 从左到右遍历的 联想八皇后!// 向下if(i+1<m&&grid[i+1][j]=='1'){// 将这个index所在的数 与它下面一个数进行合并if(uf.union(index,(i+1)*n+j)){count--;}}// 向右if(j+1<n&&grid[i][j+1]=='1'){if(uf.union(index,i*n+j+1)){count--;}}}}}returncount;}classUnionFind{// parent的index表示本身的值 value表示指向父集合 其实就是 index 最终属于 valueint[]parent;publicUnionFind(intn){parent=newint[n];for(inti=0;i<n;i++){parent[i]=i;}}// 找到最终的父集合并且把路径全部指向最终的父集合publicintfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);}returnparent[x];}// 合并两个集合publicbooleanunion(intx,inty){introotX=find(x);introotY=find(y);if(rootX==rootY){returnfalse;}parent[rootX]=parent[rootY];returntrue;}}}

反思：我没有想到图的遍历需要用dfs和bfs进行搜索，连通性问题、集合合并问题可以用并查集

994.腐烂的橘子

关键信息一句话总结：

多源 BFS，扩散一层就是一分钟

classSolution{publicintorangesRotting(int[][]grid){// 多源bfs 区别于岛屿对时间无要求 每个都bfs就好了intcount=-1;intm=grid.length;intn=grid[0].length;Queue<int[]>queue=newLinkedList<>();intfresh=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]==2){queue.offer(newint[]{i,j});}if(grid[i][j]==1){fresh++;}}}if(fresh==0){return0;}while(!queue.isEmpty()){intsize=queue.size();// 每一层算1分钟 刚开始不算 从0分钟开始count++;for(inti=0;i<size;i++){int[]cur=queue.poll();intx=cur[0];inty=cur[1];int[][]dirs={{1,0},{-1,0},{0,1},{0,-1}};for(int[]d:dirs){intnx=x+d[0];intny=y+d[1];if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]==1){grid[nx][ny]=2;fresh--;queue.offer(newint[]{nx,ny});}}}}if(fresh>0){return-1;}returncount;}}

反思：我没有抓住它对时间的要求，需要同时多源进行bfs，而200题不需要多源进行，只需要延申就行了

207.课程表

关键信息一句话总结：

用拓扑排序判断有向图中是否存在环

classSolution{publicbooleancanFinish(intnumCourses,int[][]prerequisites){// 本质：判断有向图是否存在环// 1.建图List<List<Integer>>graph=newArrayList<>();for(inti=0;i<numCourses;i++){graph.add(newArrayList<>());}// 2.入度数组int[]indegree=newint[numCourses];// 3.构建邻接表和入度for(int[]p:prerequisites){inta=p[0];intb=p[1];// b这个节点是a的前置graph.get(b).add(a);// a的前置(入度: 指向该节点的边的数量) +1indegree[a]++;}// 4.把所有入度为0的课程入队Queue<Integer>queue=newLinkedList<>();for(inti=0;i<numCourses;i++){if(indegree[i]==0){queue.offer(i);}}// 5.拓扑排序intcount=0;while(!queue.isEmpty()){intcur=queue.poll();count++;for(intnext:graph.get(cur)){indegree[next]--;if(indegree[next]==0){queue.offer(next);}}}returncount==numCourses;}}

反思：我没有建模成功，建模成判断图中是否存在环，应该用拓扑排序

208.实现Trie前缀树

关键信息一句话总结：

把字符串拆成路径存进树里，用共享前缀实现高效查找与前缀匹配

分析：isEnd用来标记是否是单词的结尾，因为app和apple有共享前缀

classTrie{classNode{Node[]children=newNode[26];booleanisEnd;}privateNoderoot;publicTrie(){root=newNode();}publicvoidinsert(Stringword){Nodenode=root;for(charc:word.toCharArray()){intindex=c-'a';// 只要 new 过一次 这个 if 以后永远是 falseif(node.children[index]==null){node.children[index]=newNode();}node=node.children[index];}node.isEnd=true;}publicbooleansearch(Stringword){Nodenode=find(word);if(node!=null&&node.isEnd){returntrue;}returnfalse;}publicbooleanstartsWith(Stringprefix){if(find(prefix)!=null){returntrue;}returnfalse;}privateNodefind(Strings){Nodenode=root;for(charc:s.toCharArray()){intindex=c-'a';if(node.children[index]==null){returnnull;}node=node.children[index];}returnnode;}}/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */