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

本文主要是介绍代码随想录算法训练营第六十四天 | 图论理论基础、深搜理论基础、广搜理论基础、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;
}

广搜理论基础

广搜理论基础

这篇关于代码随想录算法训练营第六十四天 | 图论理论基础、深搜理论基础、广搜理论基础、98. 所有可达路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1076311

相关文章

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使