笔记：代码随想录算法训练营day56:图论理论基础、深搜理论基础、98. 所有可达路径、广搜理论基础

学习资料：代码随想录

连通图是给无向图的定义，强连通图是给有向图的定义

朴素存储：二维数组

邻接矩阵

邻接表：list基础知识：C++ 容器类 <list> | 菜鸟教程

深搜是沿着一个方向搜到头再不断回溯，转向；广搜是每一次搜索要把当前能够得到的方向搜个遍

深搜三部曲：传入参数、终止条件、处理节点+递推+回溯

98. 所有可达路径

卡码网题目链接（ACM模式）

先是用邻接矩阵，矩阵的x,y表示从x到y有一条边

主要还是用回溯方法遍历整个数组的思想

#include <iostream>
#include <vector>
using namespace std;vector<vector<int>> result;
vector<int> path;void dfs(const vector<vector<int>>& graph,int x,int n){  //dfs() 必须在 main() 之前声明，否则编译器找不到它if(x==n){result.push_back(path);return;}for(int i=1;i<=n;i++){if(graph[x][i]==1){        //x是有可能连接到任意节点的，而不是在数值上只能向前遍历path.push_back(i);dfs(graph,i,n);path.pop_back();}}
}int main(){int N,M;cin>>N>>M;vector<vector<int>> graph(N+1,vector<int>(N+1,0));   //这两个声明在main里也不行   int s,t;for(int i=0;i<M;i++){cin>>s>>t;graph[s][t]=1;}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;}}

然后是邻接表：

#include <iostream>
#include <vector>
#include <list>
using namespace std;vector<vector<int>> result;
vector<int> path;void dfs(const vector<list<int>>& graph,int x,int n){  //dfs() 必须在 main() 之前声明，否则编译器找不到它if(x==n){result.push_back(path);return;}for(int i:graph[x]){     path.push_back(i);dfs(graph,i,n);path.pop_back();}
}int main(){int N,M;cin>>N>>M;vector<list<int>> graph(N+1);   //这两个声明在main里也不行   int s,t;for(int i=0;i<M;i++){cin>>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;}}

对于list的处理我还需要适应一下

例如for(int i:graph[x])

graph[s].push_back(t);

广搜大致思路为建立一个队列，每次处理一个位置将其指向的其他方向入栈，然后将该位置弹出，一直这样处理到队列为空了就是都处理完了