算法总结——【图论】

九 图论

1 图论方法总结

考察频率比较其他的少一些。重点在于ACM模式下比较难处理

1.1 dfs深度优先搜索

dfs就是往一个方向去搜索，不到黄河不回头。类似于回溯，两个关键点：

• 搜索方向，是认准一个方向搜，直到碰壁之后再换方向
• 换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。

模板：

voiddfs(参数){if(终止条件){ 存放结果;return;}for(选择：本节点所连接的其他节点){ 处理节点;dfs(图，选择的节点);// 递归 回溯，撤销处理结果 // 关键点撤销操作}}

类似回溯：

voidbacktracking(参数){if(终止条件){ 存放结果;return;}for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){ 处理节点;backtracking(路径，选择列表);// 递归 回溯，撤销处理结果 }}

1.2 bfs广度优先搜索

最经典就是二叉树层序遍历，是哟个队列实现。

广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

需要使用到一个容器保存我们遍历的元素，那么用队列，还是用栈，甚至用数组，都是可以的。

用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。（最常用）

因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。

如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。

因为栈是先进后出，加入元素和弹出元素的顺序改变了。

模板：

int dir[4][2]={0,1,1,0,-1,0,0,-1};// 表示四个方向// grid 是地图，也就是一个二维数组// visited标记访问过的节点，不要重复访问// x,y 表示开始搜索节点的下标voidbfs(vector<vector<char>>& grid, vector<vector<bool>>& visited,int x,int y){ queue<pair<int,int>> que;// 定义队列 que.push({x, y});// 起始节点加入队列 visited[x][y]=true;// 只要加入队列，立刻标记为访问过的节点while(!que.empty()){// 开始遍历队列里的元素 pair<int,int> cur = que.front(); que.pop();// 从队列取元素int curx = cur.first;int cury = cur.second;// 当前节点坐标for(int i =0; i <4; i++){// 开始想当前节点的四个方向左右上下去遍历int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];// 获取周边四个方向的坐标if(nextx <0|| nextx >= grid.size()|| nexty <0|| nexty >= grid[0].size())continue;// 坐标越界了，直接跳过if(!visited[nextx][nexty]){// 如果节点没被访问过 que.push({nextx, nexty});// 队列添加该节点为下一轮要遍历的节点 visited[nextx][nexty]=true;// 只要加入队列立刻标记，避免重复访问}}}}

题目1——岛屿数量【294】

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

示例 2：

提示：m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] 的值为 '0' 或 '1'

关注acm模式：

遍历每一个节点bfs，每次找到一个可以bfs的地方就是一个岛屿

// bfspublicclassMain{privatestaticfinalint[][] dir ={{1,0},{0,1},{-1,0},{0,-1}};publicintnumIslands(char[][] grid){int m = grid.length;int n = grid[0].length;int count =0;boolean[][] visited =newboolean[m][n];for(int i =0; i < m; i++){for(int j =0; j < n; j++){ visited[i][j]=false;}}for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(!visited[i][j]&&grid[i][j]=='1'){ count++;bfs(grid, visited, i, j);}}}return count;}publicvoidbfs(char[][] grid,boolean[][] visited,int x,int y){Queue<int[]> queue =newArrayDeque<>(); queue.offer(newint[]{x, y}); visited[x][y]=true;while(!queue.isEmpty()){// 取出元素int[] cur = queue.poll();int curx = cur[0];int cury = cur[1];// 遍历现在节点的4个方向for(int i =0; i <4; i++){int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if(nextx <0|| nextx >= grid.length || nexty <0|| nexty >= grid[0].length){continue;}// 可以到达的点，没有被访问过，并且是陆地if(!visited[nextx][nexty]&& grid[nextx][nexty]=='1'){ queue.offer(newint[]{nextx, nexty}); visited[nextx][nexty]=true;}}}}publicstaticvoidmain(String[] args){// ACM模式，自己构造用例char[][] grid1 =newchar[][]{{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}};char[][] grid2 =newchar[][]{{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};Main main =newMain();System.out.println(main.numIslands(grid1));System.out.println(main.numIslands(grid2));}}

dfs:

使用dfs来进行沉岛，并且不用使用显式的容器，递归栈

主循环找岛屿：我们依然需要用两个 for 循环遍历整个二维网格。一旦遇到 '1'（陆地），说明我们发现了一个新岛屿，岛屿数量 count++。

DFS 负责“沉没”这片岛屿：为了防止这个岛屿在后续的遍历中被重复计算，我们在遇到 '1' 后，立刻召唤 DFS 函数。

DFS 的工作任务：

1. 把当前脚下的 '1' 变成 '0'（或者标记为已访问）。这就叫“沉岛”，把陆地淹没掉。
2. 向上下左右四个方向“蔓延”，递归调用自己。
3. 如果越界了，或者遇到了水（'0'），就立刻停下（return）。

publicclassSolution{publicintnumIslands(char[][] grid){int m = grid.length;int n = grid[0].length;int count =0;for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(grid[i][j]=='1'){ count++;dfs(grid, i, j);}}}return count;}publicvoiddfs(char[][] grid,int x,int y){// 使用dfs来递归的沉没岛屿if(x <0|| x >= grid.length || y <0|| y >= grid[0].length || grid[x][y]=='0'){return;} grid[x][y]='0';// 递归沉默dfs(grid, x -1, y);dfs(grid, x, y+1);dfs(grid, x+1, y);dfs(grid, x, y-1);}publicstaticvoidmain(String[] args){// ACM模式，自己构造用例char[][] grid1 =newchar[][]{{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}};char[][] grid2 =newchar[][]{{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};Solution main =newSolution();System.out.println(main.numIslands(grid1));System.out.println(main.numIslands(grid2));}}

题目2——腐烂的橘子【13低频】

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

**
**

示例 2：

示例 3：

提示：m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j] 仅为 0、1 或 2

思路：bfs的最小分钟数，将所有2都提前入队然后进行bfs,时间计数，多源bfs，然后需要每一次扩散，有新的腐烂发生就加时间

新鲜橘子数量：最后要看有没有全部腐烂

有没有腐烂：用来增加时间

多源bfs:

privatestaticfinalint[][] dir ={{-1,0},{0,1},{1,0},{0,-1}};publicintorangesRotting(int[][] grid){// 多源bfsint m = grid.length, n = grid[0].length;Queue<int[]> queue =newArrayDeque<>();int minuteCount =0;// 在队列中放置2int freshCount =0;for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(grid[i][j]==2){ queue.offer(newint[]{i, j});}elseif(grid[i][j]==1){ freshCount++;}}}// 开始bfswhile(!queue.isEmpty()){int size = queue.size();boolean isRotting =false;// 一定考虑到多源for(int i =0; i < size; i++){int[] cur = queue.poll();int curx = cur[0], cury = cur[1];// 四周开始腐烂for(int j =0; j <4; j++){int nextx = curx + dir[j][0];int nexty = cury + dir[j][1];if(nextx <0|| nextx >= m || nexty <0|| nexty >= n){continue;}if(grid[nextx][nexty]==1){ queue.offer(newint[]{nextx,nexty}); grid[nextx][nexty]=2; freshCount--; isRotting =true;}}}if(isRotting){ minuteCount++;}}return freshCount ==0? minuteCount :-1;}

题目3——课程表【59】

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

示例 2：

提示：1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i] 中的所有课程对 互不相同

思路：bfs和dfs,拓扑排序，看有没组成环，

使用链表，按照事情的先来后到构建结构，记录其实课程,使用邻接表去表示前序关系

bfs: 比较难的地方要想到用什么数据结构去存储

// 邻接表，使用链表privateList<List<Integer>> edges;// 记录课程的入度，好判断起点privateint[] indeg;publicbooleancanFinish(int numCourses,int[][] prerequisites){// 进行邻接表和入度初始化 edges =newArrayList<>(); indeg =newint[numCourses];for(int i =0; i < numCourses; i++){ edges.add(newArrayList<>());}// 记录入度,构建邻接表for(int i =0; i < prerequisites.length; i++){ edges.get(prerequisites[i][1]).add(prerequisites[i][0]); indeg[prerequisites[i][0]]++;}// 构建队列Queue<Integer> queue =newArrayDeque<>();for(int i =0; i < numCourses; i++){if(indeg[i]==0){ queue.offer(i);}}// 有环的情况就是总有节点的度数不会减到1，我们把度数减少到1作为入队条件int visited =0;while(!queue.isEmpty()){int u = queue.poll(); visited++;for(int v : edges.get(u)){ indeg[v]--;if(indeg[v]==0){ queue.offer(v);}}}return visited == numCourses;}

题目4——实现 Trie (前缀树)【37】

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

提示：1 <= word.length, prefix.length <= 2000word 和 prefix 仅由小写英文字母组成insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

思路：背吧，想是不好象的

思路就是不是二叉树了，是二十六叉树，进来一个字符串就一次遍历字符连接字母指针数组

/** * @author YinHang * @description 前缀树，使用26叉树实现 * @create 2026-02-28 17:32 */publicclassTrie{// 根节点privateTrieNode root;// 定义前缀树节点staticclassTrieNode{boolean isEnd;// 子节点指针,有26叉所有使用数组表示TrieNode[] children;// 初始化publicTrieNode(){ isEnd =false; children =newTrieNode[26];}}// 树初始化publicTrie(){ root =newTrieNode();}// 插入字符串publicvoidinsert(String word){TrieNode current = root;for(int i =0; i < word.length(); i++){// 找到索引char c = word.charAt(i);int index = c -'a';// 进行插入节点，这个节点为空就插入，对应的就是这个字母已经有word使用，这个是可以共用的if(current.children[index]==null){ current.children[index]=newTrieNode();}// 节点指针向下流转 current = current.children[index];}// 最后一个节点标志为结束节点 current.isEnd =true;}// 查找一个word存在于前缀树中publicbooleansearch(String word){TrieNode cur = root;for(int i =0; i < word.length(); i++){char c = word.charAt(i);int index = c -'a';if(cur.children[index]==null){returnfalse;} cur = cur.children[index];}return cur.isEnd;}// 查找前缀prefix是否存在publicbooleanstartsWith(String prefix){TrieNode cur = root;for(int i =0; i < prefix.length(); i++){char c = prefix.charAt(i);int index = c -'a';if(cur.children[index]==null){returnfalse;} cur = cur.children[index];}returntrue;}publicstaticvoidmain(String[] args){Trie trie =newTrie(); trie.insert("apple"); trie.search("apple");// 返回 True trie.search("app");// 返回 False trie.startsWith("app");// 返回 True trie.insert("app"); trie.search("app");// 返回 True}}