代码随想录算法训练营
Day50 代码随想录算法训练营第 50 天 |98. 所有可达路径
目录
前言
LeetCode98. 所有可达路径
一、图论基础概念
1、图的种类
整体上一般分为 有向图 和 无向图
2、度
（1）无向图中有几条边连接该节点，该节点就有几度
（2）在有向图中，每个节点有出度和入度。
出度：从该节点出发的边的个数。
入度：指向该节点边的个数。
例如，该有向图中，节点3的入度为2，出度为1，节点1的入度为0，出度为2
3、连通性：节点的连通情况
（1）连通图
在无向图中，任何两个节点都是可以到达的的图为连通图
（如果有节点不能到达其他节点，则为非连通图）
（2）强连通图
在有向图中，任何两个节点是可以相互到达的为强连通图
（3）连通分量
在无向图中的极大连通子图称之为该图的一个连通分量
（4） 强连通分量
在有向图中极大强连通子图称之为该图的强连通分量
代码随想录-强连通分量
-
节点1、节点2、节点3、节点4、节点5 构成的子图是强连通分量，因为这是强连通图，也是极大图。
-
节点6、节点7、节点8 构成的子图 不是强连通分量，因为这不是强连通图，节点8 不能达到节点6。
-
节点1、节点2、节点5 构成的子图 也不是 强连通分量，因为这不是极大图-
4、图的构造
（1）邻接矩阵
邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组
例如：
有向图：grid[2][5] = 6 表示 节点2 指向 节点5，边的权值为6
无向图：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与 节点5 相互连通，权值为6
（2）邻接表
邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表
代码随想录-邻接表
- 节点1 指向 节点3 和 节点5
- 节点2 指向 节点4、节点3、节点5
- 节点3 指向 节点4
- 节点4指向节点1
5、图的遍历方式
（在邻接表或邻接矩阵上进行搜索）
（1）深度优先搜索（dfs）–递归实现
（2） 广度优先搜索（bfs）
二、深度优先搜索
1、深度优先搜索的三部曲
（1）确认递归函数，参数
深搜需要 二维数组数组结构保存所有路径，需要一维数组保存单一路径，可以定义一个全局变量，避免函数参数过多
（2）确认终止条件
（3） 处理目前搜索节点出发的路径
一个for循环的操作，去遍 目前搜索节点所能到的所有节点；
加入路径，递归调用，弹出
2、深度优先搜索框架
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
}
三、LeetCode98. 所有可达路径
1.题目链接
2.思路
（1）存图：
link[i][k]=1:指的是有i指向k的路径
（2）深度优先搜索
1）返回值：void
参数：终点，遍历到第几个点（当前点的下标），存图的数组
2）终止条件
当前遍历点下标等于终点下标
3）处理目前搜索节点出发的路径
① 遍历当前节点（下标i）对应的link[i]数组，如果link[i][k]等于1，那么i–>k路径存在
② k加入路径
③ k进行递归调用
④ k弹出路径
3.题解
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>ans ;
vector<int>path;
void dfs(int i,int n,vector<vector<int>>link)
{
if(i==n)
{
ans.push_back(path);
return ;
}
for(int k=1;k<=n;k++)
{
if(link[i][k])
{
path.push_back(k);
dfs(k,n,link);
path.pop_back();
}
}
}
int main()
{
int n;
int m;
int t1;
int t2;
cin>>n>>m;
vector<vector<int>>link(n+1,vector<int>(n+1,0));
//下标表示的点所连接的点的集合
for(int i=0;i<m;i++)
{
cin>>t1>>t2;
link[t1][t2]=1;//t1--->t2
}
path.push_back(1);
dfs(1,n,link);
int l=ans.size();
if(l==0)
{
cout<<-1<<"\n";
}else
{
for(int i=0;i<l;i++)
{
int r=ans[i].size();
for(int j=0;j<r;j++)
{
cout<<ans[i][j];
if(j<r-1)cout<<" ";
if(j==r-1)cout<<"\n";
}
}
}
return 0;
}