代码随想录二刷|图论2

图论

基础知识

1 无向图

（1）度：一个顶点连n条边就度为n

（2）权

加权无向图：有边长的无向图

（3）通道：两个顶点之间有一些边和点，并且没有重复的边

路：两个顶点之间有一些边和点，并且没有重复的边和点

（4）连通性

1）连通图：任意两点之间都有路相连

2）连通分量：极大连通子图

（连通子图，并且没有包含这个连通子图的连通图）

2 有向图

（1）度

入度：n条边指向顶点则入度为n

出度：从顶点发出n条边则出度为n

（2）权

加权有向图：有边长的无向图

（3）连通性

1）强连通：任意2个点可以相互到达。也就是任意两个点之间都有相互指向的有向路（任何一个点，都有到剩下所有点的有向路）

2）强连通分量：极大强连通子图

（强连通子图，并且没有包含这个强连通子图的强连通图）

3 图的构造

邻接表、邻接矩阵 或者用类

（1）邻接表

1）邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表

// 节点编号从1到n，所以申请 n+1 这么大的数组
vector<list<int>> graph(n + 1); // 邻接表，list为C++里的链表
graph[1].push_back(3)  表示5--->3

• 节点1 指向 节点3 和 节点5
• 节点2 指向 节点4、节点3、节点5
• 节点3 指向 节点4
• 节点4指向节点1

2）邻接表的优点：

• 对于稀疏图的存储，只需要存储边，空间利用率高
• 遍历节点连接情况相对容易

3）邻接表的缺点：

• 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
• 实现相对复杂，不易理解

（2）邻接矩阵

1）邻接矩阵 使用 二维数组 来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组

grid[i][j] = 6，表示 节点 i 指向 节点j ，边的权值为6

如果想表示无向图，即：grid[i][j] = 6，grid[j][i] = 6，表示节点i 与 节点j相互连通，权值为6

2）邻接矩阵的优点：

• 表达方式简单，易于理解
• 检查任意两个顶点间是否存在边的操作非常快
• 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

3）邻接矩阵的缺点：

• 遇到稀疏图，会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费

（3）类

4 图的遍历方式

• 深度优先搜索（dfs）
• 广度优先搜索（bfs）

深度优先搜索

1、dfs要点

（1）搜索方向，是认准一个方向搜，直到碰壁之后再换方向

（2）换方向是撤销原路径，回退一步，改为节点链接的下一个路径（回溯的过程）

2、dfs的举例

假设默认路径

那么接下来考虑下一个方向，先回溯退回5,遍历5的下一步选择接下来就选择5—4

在节点4这里，先选择6,到达终点，再回溯退回4,遍历4的下一步选择，接下来就选择4–3

3、dfs代码(也就是回溯)

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

4、深度优先搜索的三步走

（1）确定递归返回值和参数

（2）确定终止条件，以及终止条件处做什么

（3）遍历当前节点可以选择的下一个点（遍历递归树的一个层）

5、模板题：所有可达路径

题目描述

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

输入描述

第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

输出描述

输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出 -1。

注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 1 3 5,而不是 1 3 5 ， 5后面没有空格！

#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<int> path;
vector<vector<int>> res;
void dfs(int point, int n, vector<vector<int>>& graph) {if (point == n) {res.push_back(path);return;}for (int i = 1; i < graph[point].size(); i++) {if (graph[point][i]) {path.push_back(i);dfs(i, n, graph);path.pop_back();}}
}
int main() {int n;int m;cin >> n >> m;vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));for (int i = 0; i < m; i++) {int start;int end;cin >> start >> end;graph[start][end] = 1;}path.push_back(1);dfs(1, n, graph);if (res.size() == 0) {cout << -1 ;return 0;}for (int i = 0; i < res.size(); i++) {for (int j = 0; j < res[i].size(); j++) {cout << res[i][j];if (j < res[i].size()-1)cout << " ";}if (i < res.size()-1)cout << "\n";}return 0;
}

广度优先搜索

1、特点

广搜（bfs）是一圈一圈的搜索过程，和深搜（dfs）是一条路跑到黑然后再回溯

2、只要BFS只要搜到终点一定是一条最短路径

3、代码框架

（1）如何保存遍历到的点：

仅仅需要一个容器，能保存我们要遍历过的元素就行，用队列，用栈，用数组，都是可以的

这里选择用队列

（2）要点

1）用队列进行遍历，每次把队首拿出来，弹出，将队首可以走到的后面的点放进队尾，一直到队空

2）在入队的时候标记visit，因为如果在弹出的时候再标记就会导致一个点重复的加入队列

（3）举例

用一个方格地图，假如每次搜索的方向为 上下左右（不包含斜上方），那么给出一个start起始位置，那么BFS就是从四个方向走出第一步

（例子、图和代码来自代码随想录）

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(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（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

3

思路：每次遇到第一个没有访问过的陆地，就给结果+1,然后把与这个陆地相连的陆地全都标记为isited

无论是dfs还是bfs，都是为了找到与这个陆地相连的陆地

1、深度优先搜索

（1）版本1

没有明确的终止条件，用for循环内的判断条件排除

include <iostream>
#include <vector>
using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的visited[nextx][nexty] = true;dfs(grid, visited, nextx, nexty);}}
}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];}}vector<vector<bool>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {visited[i][j] = true;result++; // 遇到没访问过的陆地，+1dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}cout << result << endl;
}

（2）版本2

1）无返回值，参数包括图、visited、当前坐标，n和m

然后标记当前点visited[i][j] = 1

2）终止条件：

再判断一个点之前，先判断他是不是要考虑的

水域–不考虑

已经访问—不考虑

越界—不考虑

3）从当前点（i，j）出发，遍历上下左右，因为一开始判断有效性，所以所有点都递归

#include <bits/stdc++.h>
#include <vector>
using namespace std;int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
void dfs(vector<vector<int>> &visited, vector<vector<int>> &graph, int i, int j,int n, int m) {if (i < 0 || i >= n || j < 0 || j >= m)return;if (visited[i][j])return;if (graph[i][j] == 0)return;visited[i][j] = 1;for (int k = 0; k < 4; k++) {int x = directioni[k] + i;int y = directionj[k] + j;dfs(visited, graph, x, y, n, m);}
}int main() {int n;int m;int sum = 0;cin>>n>>m;vector<vector<int>> graph(n, vector<int>(m, 0));vector<vector<int>> visited(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> graph[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && graph[i][j]) {sum++;dfs(visited, graph, i, j, n, m);}}}cout << sum;return 0;
}

2、广度优先搜索

（1）把当前找到的第一次出现的陆地作为起点，bfs遍历与他相邻的陆地

每次把队首拿出来，弹出，队首可以走到的后面的点如果是没有访问过的陆地就放进队尾并且标记，一直到队空

（2）在入队的时候标记visit，因为如果在弹出的时候再标记就会导致一个点重复的加入队列

#include <bits/stdc++.h>
#include <vector>
using namespace std;int n;
int m;
int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
void bfs(vector<vector<int>> graph, vector<vector<int>> &visited, int startx,int starty) {queue<pair<int, int>> q;q.push(make_pair(startx, starty));visited[startx][starty] = 1;while (!q.empty()) {pair<int, int> now = q.front();q.pop();for (int i = 0; i < 4; i++) {int x = now.first + directioni[i];int y = now.second + directionj[i];if (x < 0 || x >= n || y < 0 || y >= m)continue;if (!visited[x][y] && graph[x][y]) {q.push(make_pair(x, y));visited[x][y] = 1;}}}
}
int main() {int sum = 0;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m, 0));vector<vector<int>> visited(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> graph[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && graph[i][j]) {sum++;bfs(graph, visited, i, j);}}}cout << sum;return 0;
}

岛屿的最大面积

题干

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

4

思路

每次遇到第一个没有访问过的陆地，就给结果+1,然后把与这个陆地相连的陆地全都标记为visited并且面积+1

遇到第一个没有访问过的陆地就是遇到新的岛屿

无论是dfs还是bfs，都是为了找到与这个陆地相连的陆地，并且记录这个岛屿的面积

dfs

#include <bits/stdc++.h>
#include <vector>
using namespace std;int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
void dfs(vector<vector<int>> &visited, vector<vector<int>> &graph, int i, int j,int n, int m, int &area) {if (i < 0 || i >= n || j < 0 || j >= m)return;if (visited[i][j])return;if (graph[i][j] == 0)return;visited[i][j] = 1;area++;for (int k = 0; k < 4; k++) {int x = directioni[k] + i;int y = directionj[k] + j;dfs(visited, graph, x, y, n, m,area);}
}int main() {int n;int m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m, 0));vector<vector<int>> visited(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> graph[i][j];}}int res = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && graph[i][j]) {int area = 0;dfs(visited, graph, i, j, n, m, area);res = max(res, area);}}}cout << res;return 0;
}

bfs

#include <bits/stdc++.h>
#include <vector>
using namespace std;int n;
int m;
int directioni[4] = {0, 1, 0, -1};
int directionj[4] = {1, 0, -1, 0};
int bfs(vector<vector<int>> graph, vector<vector<int>> &visited, int startx,int starty) {queue<pair<int, int>> q;q.push(make_pair(startx, starty));int area = 1;visited[startx][starty] = 1;while (!q.empty()) {pair<int, int> now = q.front();q.pop();for (int i = 0; i < 4; i++) {int x = now.first + directioni[i];int y = now.second + directionj[i];if (x < 0 || x >= n || y < 0 || y >= m)continue;if (!visited[x][y] && graph[x][y]) {q.push(make_pair(x, y));visited[x][y] = 1;area++;}}}return area;
}
int main() {int res = 0;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m, 0));vector<vector<int>> visited(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> graph[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && graph[i][j]) {int t = bfs(graph, visited, i, j);res = max(res, t);}}}cout << res;return 0;
}