代码随想录算法训练营第六十四天 | 图论理论基础、深搜理论基础、广搜理论基础、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出发，因此先加入节点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;    //最后一个元素单独打印
    }
    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出发，因此先加入节点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;    //最后一个元素单独打印
    }
    return 0;
}

广搜理论基础

广搜理论基础