图论Day3学习心得

今天继续看图论的题目：104. 建造最大岛屿

本题的一个暴力想法，应该是遍历地图尝试 将每一个 0 改成1，然后去搜索地图中的最大的岛屿面积。

计算地图的最大面积：遍历地图 + 深搜岛屿，时间复杂度为 n * n。

（其实使用深搜还是广搜都是可以的，其目的就是遍历岛屿做一个标记，相当于染色，那么使用哪个遍历方式都行，以下我用深搜来讲解）

每改变一个0的方格，都需要重新计算一个地图的最大面积，所以 整体时间复杂度为：n^4。

其实每次深搜遍历计算最大岛屿面积，都做了很多重复的工作。

只要用一次深搜把每个岛屿的面积记录下来就好。

第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积

第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。

也就是遍历每一个0的方格，并统计其相邻岛屿面积，最后取一个最大值。

这个过程的时间复杂度也为 n * n。

所以整个解法的时间复杂度，为 n * n + n * n 也就是 n^2。

当然这里还有一个优化的点，就是 可以不用 visited数组，因为有mark来标记，所以遍历过的grid[i][j]是不等于1的。

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int n, m;
int count;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark) {if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水visited[x][y] = true; // 标记访问过grid[x][y] = mark; // 给陆地标记新标签count++;for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;  // 越界了，直接跳过dfs(grid, visited, nextx, nexty, mark);}
}int main() {cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false)); // 标记访问过的点unordered_map<int ,int> gridNum;int mark = 2; // 记录每个岛屿的编号bool isAllGrid = true; // 标记是否整个地图都是陆地for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 0) isAllGrid = false;if (!visited[i][j] && grid[i][j] == 1) {count = 0;dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 truegridNum[mark] = count; // 记录每一个岛屿的面积mark++; // 记录下一个岛屿编号}}}if (isAllGrid) {cout << n * m << endl; // 如果都是陆地，返回全面积return 0; // 结束程序}// 以下逻辑是根据添加陆地的位置，计算周边岛屿面积之和int result = 0; // 记录最后结果unordered_set<int> visitedGrid; // 标记访问过的岛屿for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {count = 1; // 记录连接之后的岛屿数量visitedGrid.clear(); // 每次使用时，清空if (grid[i][j] == 0) {for (int k = 0; k < 4; k++) {int neari = i + dir[k][1]; // 计算相邻坐标int nearj = j + dir[k][0];if (neari < 0 || neari >= n || nearj < 0 || nearj >= m) continue;if (visitedGrid.count(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加// 把相邻四面的岛屿数量加起来count += gridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]); // 标记该岛屿已经添加过}}result = max(result, count);}}cout << result << endl;}

然后看下一道：106. 岛屿的周长

遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。

如果该陆地上下左右的空格是有水域，则说明是一条边，

陆地的右边空格是水域，则说明找到一条边。

如果该陆地上下左右的空格出界了，则说明是一条边，

#include <iostream>
#include <vector>
using namespace std;
int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}int direction[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) {for (int k = 0; k < 4; k++) {       // 上下左右四个方向int x = i + direction[k][0];int y = j + direction[k][1];    // 计算周边坐标x,yif (x < 0                       // x在边界上|| x >= grid.size()     // x在边界上|| y < 0                // y在边界上|| y >= grid[0].size()  // y在边界上|| grid[x][y] == 0) {   // x,y位置是水域result++;}}}}}cout << result << endl;}

然后看下一道：110. 字符串接龙

本题只需要求出最短路径的长度就可以了，不用找出具体路径。

所以这道题要解决两个问题：

1、图中的线是如何连在一起的

在搜索的过程中，可以枚举，用26个字母替换当前字符串的每一个字符，在看替换后是否在 strList里出现过，就可以判断 两个字符串 是否是链接的。

2、起点和终点的最短路径长度

首先题目中并没有给出点与点之间的连线，而是要自己去连，条件是字符只能差一个。

所以判断点与点之间的关系，需要判断是不是差一个字符，如果差一个字符，那就是有链接。

然后就是求起点和终点的最短路径长度，在无权图中，求最短路，用深搜或者广搜就行，没必要用最短路算法。

在无权图中，用广搜求最短路最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。

本题如果用深搜，会比较麻烦，要在到达终点的不同路径中选则一条最短路。

而广搜只要达到终点，一定是最短路。

另外需要有一个注意点：

• 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
• 使用set来检查字符串是否出现在字符串集合里更快一些

C++代码如下：（详细注释）

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;
int main() {string beginStr, endStr, str;int n;cin >> n;unordered_set<string> strSet;cin >> beginStr >> endStr;for (int i = 0; i < n; i++) {cin >> str;strSet.insert(str);}// 记录strSet里的字符串是否被访问过，同时记录路径长度unordered_map<string, int> visitMap; // <记录的字符串，路径长度>// 初始化队列queue<string> que;que.push(beginStr);// 初始化visitMapvisitMap.insert(pair<string, int>(beginStr, 1));while(!que.empty()) {string word = que.front();que.pop();int path = visitMap[word]; // 这个字符串在路径中的长度// 开始在这个str中，挨个字符去替换for (int i = 0; i < word.size(); i++) {string newWord = word; // 用一个新字符串替换str，因为每次要置换一个字符// 遍历26的字母for (int j = 0 ; j < 26; j++) {newWord[i] = j + 'a';if (newWord == endStr) { // 发现替换字母后，字符串与终点字符串相同cout <<  path + 1 << endl; // 找到了路径 return 0;}// 字符串集合里出现了newWord，并且newWord没有被访问过if (strSet.find(newWord) != strSet.end()&& visitMap.find(newWord) == visitMap.end()) {// 添加访问信息，并将新字符串放到队列中visitMap.insert(pair<string, int>(newWord, path + 1));que.push(newWord);}}}}// 没找到输出0cout << 0 << endl;}

然后继续看下一道：105. 有向图的完全联通

本题是一个有向图搜索全路径的问题。 只能用深搜（DFS）或者广搜（BFS）来搜。

深搜三部曲：

1. 确认递归函数，参数

需要传入地图，需要知道当前我们拿到的key，以至于去下一个房间。

同时还需要一个数组，用来记录我们都走过了哪些房间，这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。

所以 递归函数参数如下：

// key 当前得到的可以 
// visited 记录访问过的房间 
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {

1. 确认终止条件

遍历的时候，什么时候终止呢？

这里有一个很重要的逻辑，就是在递归中，我们是处理当前访问的节点，还是处理下一个要访问的节点。

这决定 终止条件怎么写。

首先明确，本题中什么叫做处理，就是 visited数组来记录访问过的节点，该节点默认 数组里元素都是false，把元素标记为true就是处理 本节点了。

如果我们是处理当前访问的节点，当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。

代码就是这样：

// 写法一：处理当前访问的节点
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {if (visited[key]) {return;}visited[key] = true;list<int> keys = graph[key];for (int key : keys) {// 深度优先搜索遍历dfs(graph, key, visited);}
}

如果我们是处理下一层访问的节点，而不是当前层。那么就要在 深搜三部曲中第三步：处理目前搜索节点出发的路径的时候对 节点进行处理。

这样的话，就不需要终止条件，而是在 搜索下一个节点的时候，直接判断 下一个节点是否是我们要搜的节点。

代码就是这样的：

// 写法二：处理下一个要访问的节点
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {list<int> keys = graph[key];for (int key : keys) {if (visited[key] == false) { // 确认下一个是没访问过的节点visited[key] = true;dfs(graph, key, visited);}}
}

可以看出，如何看待 我们要访问的节点，直接决定了两种不一样的写法，很多录友对这一块很模糊，可能做过这道题，但没有思考到这个维度上。

1. 处理目前搜索节点出发的路径

其实在上面，深搜三部曲 第二部，就已经讲了，因为终止条件的两种写法， 直接决定了两种不一样的递归写法。

这里还有细节：

看上面两个版本的写法中， 好像没有发现回溯的逻辑。

我们都知道，有递归就有回溯，回溯就在递归函数的下面， 那么之前我们做的dfs题目，都需要回溯操作，例如：0098.所有可达路径， 为什么本题就没有回溯呢？

代码中可以看到dfs函数下面并没有回溯的操作。

此时就要在思考本题的要求了，本题是需要判断 1节点 是否能到所有节点，那么我们就没有必要回溯去撤销操作了，只要遍历过的节点一律都标记上。

那什么时候需要回溯操作呢？

当我们需要搜索一条可行路径的时候，就需要回溯操作了，因为没有回溯，就没法“调头”， 如果不理解的话，去看我写的 0098.所有可达路径 的题解。

以上分析完毕，DFS整体实现C++代码如下：

// 写法一：dfs 处理当前访问的节点
#include <iostream>
#include <vector>
#include <list>
using namespace std;void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {if (visited[key]) {return;}visited[key] = true;list<int> keys = graph[key];for (int key : keys) {// 深度优先搜索遍历dfs(graph, key, visited);}
}int main() {int n, m, s, t;cin >> n >> m;// 节点编号从1到n，所以申请 n+1 这么大的数组vector<list<int>> graph(n + 1); // 邻接表while (m--) {cin >> s >> t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);}vector<bool> visited(n + 1, false);dfs(graph, 1, visited);//检查是否都访问到了for (int i = 1; i <= n; i++) {if (visited[i] == false) {cout << -1 << endl;return 0;}}cout << 1 << endl;
}

OK，今天就到这，明天看一下并查集。