day50 图论基础 卡码网98. 所有可达路径

图论基础：

图的基本概念：

二维坐标中，两点可以连成线，多个点连成的线就构成了图。

当然图也可以就一个节点，甚至没有节点（空图）。

图的种类：有向图；无向图。

有向图：两个节点之间通过→连接。

无向图：两个节点仅连接，而没有箭头。

权值：表示路径的值。

度：有多少边连接该节点，这个节点就有几度。

出度：有多少条边从该节点支出，那就有多少出度。

入度：有多少条边指向该节点，那就有多少入度。

（出度和入度都只在有向图中）

连通图：从某一个节点出发，可以达到任意一个其他的节点。（无向图）

强连通图：同上，但是是在有向图中。

连通分量：即极大连通子图，就是无向图并是连通图，但是可以分成几部分，每一部分都是连通图，那么每一部分就叫连通分量。（无向图）

强联通分量：同上，但是是在有向图中。

图的构造：

朴素存储：构造一个n*2的数组，每一行的第一个元素是出发点，第二个元素是箭头指向节点。但这种数组不便于遍历。

邻接矩阵：构造一个n*n的grad数组，第i行第j列表示第i个节点指向第j个节点，权值为该元素的大小。如果是无向图，那就把第j行第i列的位置元素大小也设为该权值。缺点：如果节点很多，就会很浪费空间。（适用于节点少，但边多的情况）

邻接表：左侧一个n大小的数组，右边一个链表，数组中节点以箭头指向方向指向链表，不需要在意链表中节点的顺序，只是这一串链表的节点都可以从数组的那一个节点直接指向。开辟空间的大小在于边的多少。（适合用于节点多，边少的情况）

图的遍历：

深度优先搜索（DFS）和广度优先搜索（BFS）。

相对应的就是二叉树中的递归遍历和层序遍历。

深度优先搜索：

可以理解为：从出发点开始，一直朝着一个方向进行，直接到达终点或者是曾经访问过的节点，然后撤销最近的一次移动，再朝另一个方向进行，不断反复。

深搜三部曲：

1.确定函数和参数

2.确定终止条件

3.处理节点

vector<vector<int>> result; //结果集vector<int> path; //单条路径void dfs(图,目前搜索的节点){if(终止条件){存放结果;return;}for(){处理节点;dfs(图，选择的节点);回溯，撤销处理结果;}}

广度优先搜索：

适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

从start起点开始，是一圈一圈，向外搜索，方格编号1为第一步遍历的节点，方格编号2为第二步遍历的节点，第四步的时候我们找到终止点end。

正是因为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; // 只要加入队列立刻标记，避免重复访问}}}}

所有可达路径

题目描述

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

输入描述

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

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

输出描述

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

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

输入示例

5 5
1 3
3 5
1 2
2 4
4 5

输出示例

1 3 5
1 2 4 5

提示信息

用例解释：

有五个节点，其中的从 1 到达 5 的路径有两个，分别是 1 -> 3 -> 5 和 1 -> 2 -> 4 -> 5。

因为拥有多条路径，所以输出结果为：

1 3 5
1 2 4 5

或

1 2 4 5
1 3 5
都算正确。

数据范围：

• 图中不存在自环
• 图中不存在平行边
• 1 <= N <= 100
• 1 <= M <= 500

首先就是如何存图的问题。两种方式，一种是邻接矩阵，一种是邻接表。

邻接矩阵：首先要定义一个大小为n+1 * n+1的graph二维数组，全初始化为0。然后把每条边存入这个数组中，让每个graph[s][t]=1。

深搜三部曲：

确定函数和参数：函数类型是void，参数有图（二维数组），当前节点位置，终止节点。

确定终止条件：如果当前节点等于终止节点了，就把path加进result里，然后返回。

处理当前节点：如何去找到当前节点指向哪个节点的，循环遍历，判断从该节点出发到其他所有节点的graph是否==1。如果==1，就把这个节点放入path，然后递归dfs(graph,x,n),再回溯，即撤销这个节点。

注意输出的时候要考虑每行最后不能再加空格。

#include <iostream>
#include <vector>
using namespace std;
vector<int> path;
vector<vector<int>> result;
void dfs(vector<vector<int>>& graph,int x,int n);
int main()
{int n,m;cin>>n>>m;vector<vector<int>> graph(n+1,vector<int>(n+1,0));int s,t;for(int i = 1;i<=m;i++){cin>>s>>t;graph[s][t] = 1;    }path.push_back(1);dfs(graph,1,n);if(result.size()==0) cout<<"-1";for(const vector<int>& pa:result){ for(int i = 0;i<pa.size();i++){cout<<pa[i];if(i!=pa.size()-1) cout<<" ";}cout<<endl;}
}
void dfs(vector<vector<int>>& graph,int x,int n)
{if(x==n){result.push_back(path);return;}for(int i = 1;i<=n;i++){if(graph[x][i]==1){path.push_back(i);dfs(graph,i,n);path.pop_back();}}
}

再给出邻接表的写法（来自代码随想录,自己有点懒了···），不给解释了，关键是看看邻接表如何存图。

#include <iostream>
#include <vector>
#include <list>
using namespace std;vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径void dfs (const 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;// 节点编号从1到n，所以申请 n+1 这么大的数组vector<list<int>> graph(n + 1); // 邻接表while (m--) {cin >> s >> t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);}path.push_back(1); // 无论什么路径已经是从0节点出发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;}
}