代码随想录算法训练营第六十四天 | 图论理论基础、深搜理论基础、广搜理论基础、98. 所有可达路径

图论理论基础

我写在了个人语雀笔记中

https://www.yuque.com/yuqueyonghu8mml9e/bmbl71/ex473q4y0ebs0l3r?singleDoc# 

深搜理论基础

https://www.yuque.com/yuqueyonghu8mml9e/bmbl71/zamfikz08c2haptn?singleDoc#

98. 所有可达路径

题目链接：98. 所有可达路径 

文字讲解：98. 所有可达路径 | 代码随想录 

解题思路

邻接矩阵

1.确认递归函数和参数

首先dfs函数中，一定要有一个图，其次是我们当前遍历的节点，为x

其次还需要一个n，来表示终点，当x==n时则表示达到了终点

最后就是需要保存单一路径的path，和结果result了

2.确定终止条件

当我们的x==n时，则我们找到了从出发点到结束点的路径

3.处理目前搜索节点的路径

首先我们是要找到x节点指向了哪些节点？

for(int i = 1 ; i<=n ; i++)
{if(graph[x][i]==1){//找到x指向的节点，就是节点i//此时我们要将x指向的节点加入到path中path.push_back(i);//进入下一层递归dfs(graph,i,n);//回溯的过程path.pop_back();   }
}

4.打印结果

// 输出结果
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<bits/stdc++.h>
using namespace std;
vector<int> path;
vector<vector<int>> result;
void dfs(const 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();}}
}int main()
{int n,m,s,t;cin>> n >> m;//构造图vector<vector<int>> graph(n+1,vector<int>(n+1,0));while(m--){cin>>s>>t;graph[s][t] =1;}//开始搜索，因为是从节点1出发，因此先加入节点1path.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;    //最后一个元素单独打印}return 0;
}

邻接表（构造和遍历方式有所不同）

#include<bits/stdc++.h>
using namespace std;
vector<int> path;
vector<vector<int>> result;
void dfs(const vector<list<int>>& graph , int x, int n)
{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,s,t;cin>> n >> m;//构造图vector< list<int> > graph(n+1);while(m--){cin>>s>>t;graph[s].push_back(t);    //下标对应节点}//开始搜索，因为是从节点1出发，因此先加入节点1path.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;    //最后一个元素单独打印}return 0;
}

广搜理论基础

广搜理论基础