代码随想录算法训练营
—day56
文章目录
前言
今天是算法营的第56天，希望自己能够坚持下来！
今天开始是图论章节！今日任务：
● 图论理论基础
● 深搜理论基础
● 98. 所有可达路径
● 广搜理论基础
一、图论理论基础
图的种类
有向图：
无向图：
加权有向图，图中边的有权值：
度
无向图：有几条边连接该节点，该节点就有几度。
有向图：每个节点有出度和入度。
出度：从该节点出发的边的个数。
入度：指向该节点边的个数
连通图
无向图中，任何两个节点都是可以到达的，我们称之为连通图。
非连通图
有节点不能到达其他节点：
节点1 不能到达节点4。
强连通图
有向图中，任何两个节点是可以相互到达的，我们称之为 强连通图。
连通分量
在无向图中的极大连通子图称之为该图的一个连通分量。
该无向图中 节点1、2、5 构成的子图就是 该无向图中的一个连通分量，该子图所有节点都是相互可达到的。同理，节点3、4、6 构成的子图 也是该无向图中的一个连通分量。节点3 、4 构成的子图 不是该无向图的联通分量，必须是极大联通子图才是。
图的构造
邻接矩阵，使用二维数组来表示图结构。有多少节点就申请多大的二维数组。
例如： grid[2][5] = 6，表示 节点 2 连接 节点5 为有向图，节点2 指向 节点5，边的权值为6。
如果想表示无向图，即：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与 节点5 相互连通，权值为6。
在一个 n （节点数）为8 的图中，就需要申请 8 * 8 这么大的空间。
图中有一条双向边，即：grid[2][5] = 6，grid[5][2] = 6。邻接表：使用 数组 + 链表的方式来表示。有多少边 才会申请对应大小的链表。
这里表达的图是：
节点1 指向 节点3 和 节点5
节点2 指向 节点4、节点3、节点5
节点3 指向 节点4
节点4指向节点1
图的遍历方式
- 深度优先搜索（dfs）
- 广度优先搜索（bfs）
二、深搜理论基础
dfs 搜索过程
一条路走到黑，到达尽头再回头（回溯）
要从1走到6，深度搜索先找到1->5->6然后回溯到5的时候，重新向4出发
此时找到了第二条路，1->5->4->6，然后再回溯到4的时候，重新向3出发…
深搜三部曲
- 确认递归函数，参数
一般情况，深搜需要 二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局变量，避免让我们的函数参数过多。函数的参数根据实际情况再边写边添加。
vector<vector<int>> result; // 保存符合条件的所有路径
vector<int> path; // 起点到终点的路径
void dfs (图，目前搜索的节点)
- 确认终止条件
if (终止条件) {
存放结果;
return;
}
- 处理目前搜索节点出发的路径
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
三、98. 所有可达路径
领接矩阵
思路：
- 本题有n 个节点，因为节点标号是从1开始的，为了节点标号和下标对齐，我们申请 n + 1 * n + 1 这么大的二维数组。输入m个边，构造方式如下：
vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
while (m--) {
cin >> s >> t;
// 使用邻接矩阵 ，1 表示 节点s 指向 节点t
graph[s][t] = 1;
}
- 因为是需要找一条条完整的路径，最后求所有路径的集合，所以适合使用深度优先搜索，定义一个path表示一条路径，result表示path的结果集。
- 每条路径都需要从节点1开始，所以先把节点1放入path中，再用dfs递归找完整的路径。
- 深搜三部曲：
①函数参数：本题只需要保存地图的容器和起点，终点（用于终止条件）
②终止条件：当起点=终点的时候表示找到了一条路径，将path加入结果集。
③处理目前搜索节点出发的路径：遍历当前节点所连接的所有节点，找到当前起点的下一个节点，加入path中，继续递归。 - 打印结果，需要注意最后一个元素后面不带空格
代码如下：
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> result; //收集符合条件的所有路径
vector<int> path; //1节点到终点的单个路径
//深度优先搜索
void dfs(vector<vector<int>> graph, int x, int n) {
if (x == n) { //当前遍历的节点x到达节点n，说明找到了符合条件的一条路径
result.push_back(path);
return;
}
for (int i = 1; i <= n; i++) { //遍历当前节点x所连接的所有节点
if (graph[x][i] == 1) {
path.push_back(i); //添加i到当前路径中
dfs(graph, i, n); //寻找从i到n的路径
path.pop_back(); //回溯
}
}
}
int main() {
int n, m, s, t;
cin >> n >> m;
//节点编号从1到n，所以申请n+1这么大的数组
vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
while (m--) {
cin >> s >> t;
//使用邻接矩阵 表示无线图 1表示s与t是相连的
graph[s][t] = 1;
}
path.push_back(1); //无论什么路径，都是从第一个节点出发
dfs(graph, 1, n); //寻找从节点1到节点n的路径
//打印结果
if (result.size() == 0) cout << -1 << endl;
for (const vector<int> &pa: result) {
for (int i = 0; i < pa.size() - 1; i++) {
cout << pa[i] << " ";
}
cout << pa[pa.size()-1] << endl;
}
}
邻接表
用数组和列表来表示地图：
// 节点编号从1到n，所以申请 n+1 这么大的数组
vector<list<int>> graph(n + 1); // 邻接表，list为C++里的链表
while (m--) {
cin >> s >> t;
// 使用邻接表 ，表示 s -> t 是相连的
graph[s].push_back(t); //将t放入s行的列表中
}
代码如下：
#include <iostream>
#include <vector>
#include <list>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void dfs(vector<list<int>> graph, int x, int n) {
if (x == n) {
result.push_back(path);
return;
}
for (int i: graph[x]) { //遍历x可以连接到的下一个节点
path.push_back(i); //遍历到的节点加入到路径中来
dfs(graph, i, n);
path.pop_back();
}
}
int main() {
int n, m, s, t;
cin >> n >> m;
vector<list<int>> graph(n + 1);
while (m--) {
cin >> s >> t;
//使用邻接表， 表示s-》t是相连的
graph[s].push_back(t);
}
path.push_back(1);
dfs(graph, 1, n);
if (result.size() == 0) cout << -1 << endl;
for (const vector<int>& pa:result) {
for (int i = 0; i < pa.size() - 1; i++) {
cout << pa[i] << " ";
}
cout << pa[pa.size() - 1] << endl;
}
}
四、广度优先搜索理论基础
广搜的使用场景
深度优先搜索是一条路走到黑，而广度优先搜索则是一圈圈的往外扩加粗样式。
广搜的搜索方式就适合于解决两个点之间的最短路径问题。
也有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。
广搜的过程
从start位置开始，每次循环都是遍历每一个方向的下一步。
正是因为一圈一圈的遍历方式，所以一旦遇到终止点，那么一定是一条最短路径。
代码框架
这种一圈圈的搜索方式，需要有一个容器来存储遍历的路径，通常用队列（其实用其他的也可以）
dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; 是用于计算下一步的坐标，例如向下移动一个单位，就是y坐标+1。
ps：这种只有一对花括号的初始化方式也是合法的，一般会自动将连续的数字分配到二维数组的正确位置，但有些编译器不支持。
模版代码如下：
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; // 只要加入队列立刻标记，避免重复访问
}
}
}
}
总结
图论有些复杂，还需要多多练习。
深度优先搜索dfs，是一条路走到黑，到达尽头再回头（回溯）。
广度优先搜索bfs，是一圈圈往外扩展。
明天继续加油！