C++学习/复习补充记录 --- 图论(深搜，广搜)
图的度
无向图：
连接某节点的边数，即为该节点的【度】。
（无向图中，有5条边连接节点4，则节点4的度为5。）
有向图：
出度：从该节点出发的边的个数。
入度：指向该节点边的个数。
（有向图中，
从节点3出发的边的个数是2，则节点3的入度为2；
指向节点3的边的个数是5，则出度为5）
连通性
（无向图）
连通图：在无向图中，任何两个节点都是可以到达的图。
非连通图：在无向图中，存在有节点不能到达其他节点的图。
连通图 
非连通图（节点1 不能到达节点4） （有向图）
强连通图：在有向图中，任何两个节点是可以相互到达的图。
图的存储
邻接表
邻接矩阵
一、深搜 与 广搜
数据结构与算法 | 深搜（DFS）与广搜（BFS）_深搜广搜算法-CSDN博客
深度优先搜索理论基础
深搜和广搜的区别：
（通俗版）
广搜（bfs）是一圈一圈的搜索过程，
深搜（dfs）是一条路跑到黑然后再回溯。
- dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
- bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
二叉树的递归法，就是dfs。
二叉树的迭代法，就是bfs（广度优先搜索）。
所以dfs，bfs其实是基础搜索算法，也广泛应用与其他数据结构与算法中。
深度优先搜索（Depth First Search）
深搜dfs关键就两点：
- 搜索方向，是认准一个方向搜，直到碰壁之后再换方向
- 换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。
因为dfs搜索可一个方向，并需要回溯，所以用递归的方式来实现是最方便的。
回溯链接：C++学习/复习补充记录 --- 递归、回溯_c++中回溯是啥-CSDN博客
深搜三部曲
1、确认递归函数，参数
2、确认终止条件
3、处理目前搜索节点出发的路径
深搜代码模板：
//1、确认递归函数，参数 vector<vector<int>> result; // 保存符合条件的所有路径（存放结果组合的vector） vector<int> path; // 起点到终点的路径（单个组合结果）void dfs (图，目前搜索的节点) {if (剪枝条件) return;//剪枝//2、确认终止条件if (终止条件) {result.push_back(path);//存放结果;return;}//3、处理目前搜索节点出发的路径for (选择：本层节点所连接的其他节点) {处理节点;（做选择）dfs(图，选择的节点); // 递归回溯，撤销处理结果（撤销选择）} }（回溯撤销处理结果其实就是：撤回一步，回到上一步重新走另一个方向。）
广度优先搜索（Breadth First Search）
1、应用场景：
广搜的搜索方式就适合于解决两个点之间的最短路径问题。
因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路
2、实现方式：
用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。
因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。
如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。
因为栈是先进后出，加入元素和弹出元素的顺序改变了。
广搜不需要注意 转圈搜索的顺序 ！
广搜代码模板：
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; // 只要加入队列立刻标记，避免重复访问}}} }（该模板针对的是如下图的四方格地图）
实际应用
输入数据的含义：
例一：
输入：graph = [[1,2],[3],[3],[]]节点0可链接到的节点有：节点1，节点2；
节点1可链接到的节点有：节点3；
节点2可链接到的节点有：节点3；
节点3可链接到的节点有：无。
例二：
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]节点0可链接到的节点有：节点4，节点3，节点1；
节点1可链接到的节点有：节点3，节点2，节点4；
节点2可链接到的节点有：节点3；
节点3可链接到的节点有：节点4；
节点4可链接到的节点有：无。
1.1 所有可能的路径 (深搜)
给你一个有
n个节点的 有向无环图（DAG），请你找出所有从节点0到节点n-1的路径并输出（不要求按特定顺序）
graph[i]是一个从节点i可以访问的所有节点的列表（即从节点i到节点graph[i][j]存在一条有向边）。
class Solution {vector<vector<int>> result;//符合条件的路径集合vector<int> path;//0节点到终点的路径void dfs(vector<vector<int>>& graph, int cur) {//cur为当前遍历到的节点if (cur == graph.size() - 1) {//要求从节点0到节点n-1的路径并输出，所以是 graph.size() - 1result.push_back(path);return;//已找到一条符合条件的路径}for (int i = 0; i < graph[cur].size(); i++) {//遍历当前节点可链接到的所有节点path.push_back(graph[cur][i]);//当前选择的链接节点尝试加入dfs(graph, graph[cur][i]);//加入下一层递归path.pop_back();//当前选择的链接节点走不通，不带上玩，腾出位置尝试另一个}}
public:vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {path.push_back(0);//所有路径皆是从节点0出发dfs(graph, 0);//开始遍历return result;}
};