【代码随想录训练营第42期 Day50打卡 - dfs入门 - 卡码网 98. 所有可达路径

本文主要是介绍【代码随想录训练营第42期 Day50打卡 - dfs入门 - 卡码网 98. 所有可达路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、dfs基础

二、模板题

题目:98. 所有可达路径

题目链接

题解:dfs+邻接矩阵

 三、小结


一、dfs基础

dfs是按照一个方向搜索到尽头再搜索其他方向。怎样实现对其他方向的搜索呢?我们可以通过回溯,撤销最后一步,再选择其他路线。 -- 回溯过程某种程度上也是递归的体现。所以,实现 dfs 的一个关键就是递归。

之前有了回溯的基础,其实可以发现回溯算法其实就是依靠 dfs 来实现。

这样我们就能得出 dfs 函数的基本模板(参考代码随想录):

void dfs(参数) {if (终止条件) {存放结果;return;}for (选择:本节点所连接的其他节点) {处理节点;dfs(图,选择的节点); // 递归回溯,撤销处理结果}
}

对于得到不同路径的问题,我们一般会采用两个数组来记录,一个存放所有路径,一个存放当前遍历的路径。

vector<vector<int>> ans;     // 符合条件的所有路径
vector<int> path;         // 当前遍历的路径

二、模板题

题目:98. 所有可达路径

题目链接

98. 所有可达路径 (kamacoder.com)

题目描述

给定一个有 n 个节点的有向无环图,节点编号从 1 到 n。请编写一个函数,找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

输入描述

第一行包含两个整数 N,M,表示图中拥有 N 个节点,M 条边

后续 M 行,每行包含两个整数 s 和 t,表示图中的 s 节点与 t 节点中有一条路径

输出描述

输出所有的可达路径,路径中所有节点之间空格隔开,每条路径独占一行,存在多条路径,路径输出的顺序可任意。如果不存在任何一条路径,则输出 -1。

注意输出的序列中,最后一个节点后面没有空格! 例如正确的答案是 `1 3 5`,而不是 `1 3 5 `, 5后面没有空格!

输入示例

5 5
1 3
3 5
1 2
2 4
4 5

输出示例

1 3 5
1 2 4 5

提示信息

用例解释:

有五个节点,其中的从 1 到达 5 的路径有两个,分别是 1 -> 3 -> 5 和 1 -> 2 -> 4 -> 5。

因为拥有多条路径,所以输出结果为:

1 3 5
1 2 4 5

1 2 4 5
1 3 5
都算正确。

数据范围:

  • 图中不存在自环
  • 图中不存在平行边
  • 1 <= N <= 100
  • 1 <= M <= 500
题解:dfs+邻接矩阵

求不同路径的问题,一般通过 dfs 来实现。

这题出的很经典,我们需要的就是不断搜索找到不同的路径使得从起始位置到达中终止位置。

需要注意的是:

        1.这里用的节点 1 作为起始位置,那么初始化邻接矩阵,大小就应该为n+1;当然以节点 0 作为起始位置也可以,那么邻接矩阵大小就为 n ;

        2.标记相连的方式:邻接矩阵中 graph[s][t] = 1 -- 用 1 表示 s 与 t 相连。

深度优先搜索函数 dfs

        1.参数包括邻接矩阵 graph、当前节点 x 和目标节点 n。

        2.终止条件:如果当前节点 x 等于目标节点 n,则意味着找到了一条从起始节点到目标节点的路径。此时,将当前路径 path 添加到结果集 ans 中,并返回。

        3.遍历相邻节点:对于当前节点 x,遍历所有可能的相邻节点(从1到n)。

        4.如果节点 x 与节点 i 相连(即 graph[x][i] == 1),则执行以下步骤:

                将节点 i 添加到当前路径 path 中;

                递归调用 dfs 函数,从节点 i (与 x 相连接的节点)开始继续深度优先搜索;

                在递归返回后,将节点 i 从路径 path 中移除,以实现回溯。

代码如下(其实就是 dfs 模板的应用):

#include<bits/stdc++.h>
using namespace std;vector<vector<int>> ans;        // 存放符合条件的路径 -- 存放结果
vector<int> path;           // 起始位置(节点1)到终点的路径void dfs (const vector<vector<int>>& graph, int x, int n) { if (x == n) {       // 终止条件:当前遍历的节点 x 到达节点 n,说明找到符合条件的一条路径ans.push_back(path);        //当前路径存入 ansreturn;}for (int i = 1; i <= n; i++) {      // 遍历节点 x 连接的所有节点if (graph[x][i] == 1) {         // 找到 x 连接的节点path.push_back(i);      // 遍历到的节点加入到路径中来dfs(graph, i, n);       // 进入下一层递归 -- 从当前 x 连接的 i 开始path.pop_back();        // 回溯,撤销本节点}}
}int main() {int n, m, s, t;cin >> n >> m;vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));        // 初始化邻接矩阵,大小为n+1,因为节点编号从1开始while (m--) {cin >> s >> t;graph[s][t] = 1;    // 使用邻接矩阵表示无线图,1 表示 s 与 t 是相连的}path.push_back(1);         // 将起始节点1加入到路径中 -- 后续dfs操作并不添加起始节点1dfs(graph, 1, n);        // 从节点1开始深度优先搜索if (ans.size() == 0) {          // 没有找到任何路径cout<<"-1"<<endl;}for (const vector<int> &p : ans) {              // 这里的 p 用来遍历 ans 的各个元素 -- 每个元素都是一条路径 path,需单独将这些路径打印for (int i = 0; i < p.size() - 1; i++) {       // 注意:当前路径最后一个元素后无空格 -- 遍历范围 0 -- size-2cout << p[i] << " ";}cout << p[p.size() - 1]  << endl;        // 将每条路径最后一个元素单独提出来,从而防止最后结果多出一个空格}
}

 三、小结

今天来到图论章节打卡的第一天,这一类问题并不简单,后边会继续进行相关内容的练习和打卡,希望终能有所收获。

这篇关于【代码随想录训练营第42期 Day50打卡 - dfs入门 - 卡码网 98. 所有可达路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

通过C#获取PDF中指定文本或所有文本的字体信息

《通过C#获取PDF中指定文本或所有文本的字体信息》在设计和出版行业中,字体的选择和使用对最终作品的质量有着重要影响,然而,有时我们可能会遇到包含未知字体的PDF文件,这使得我们无法准确地复制或修改文... 目录引言C# 获取PDF中指定文本的字体信息C# 获取PDF文档中用到的所有字体信息引言在设计和出

python多进程实现数据共享的示例代码

《python多进程实现数据共享的示例代码》本文介绍了Python中多进程实现数据共享的方法,包括使用multiprocessing模块和manager模块这两种方法,具有一定的参考价值,感兴趣的可以... 目录背景进程、进程创建进程间通信 进程间共享数据共享list实践背景 安卓ui自动化框架,使用的是

SpringBoot生成和操作PDF的代码详解

《SpringBoot生成和操作PDF的代码详解》本文主要介绍了在SpringBoot项目下,通过代码和操作步骤,详细的介绍了如何操作PDF,希望可以帮助到准备通过JAVA操作PDF的你,项目框架用的... 目录本文简介PDF文件简介代码实现PDF操作基于PDF模板生成,并下载完全基于代码生成,并保存合并P

SpringBoot基于MyBatis-Plus实现Lambda Query查询的示例代码

《SpringBoot基于MyBatis-Plus实现LambdaQuery查询的示例代码》MyBatis-Plus是MyBatis的增强工具,简化了数据库操作,并提高了开发效率,它提供了多种查询方... 目录引言基础环境配置依赖配置(Maven)application.yml 配置表结构设计demo_st

SpringCloud集成AlloyDB的示例代码

《SpringCloud集成AlloyDB的示例代码》AlloyDB是GoogleCloud提供的一种高度可扩展、强性能的关系型数据库服务,它兼容PostgreSQL,并提供了更快的查询性能... 目录1.AlloyDBjavascript是什么?AlloyDB 的工作原理2.搭建测试环境3.代码工程1.

Java调用Python代码的几种方法小结

《Java调用Python代码的几种方法小结》Python语言有丰富的系统管理、数据处理、统计类软件包,因此从java应用中调用Python代码的需求很常见、实用,本文介绍几种方法从java调用Pyt... 目录引言Java core使用ProcessBuilder使用Java脚本引擎总结引言python

Java中ArrayList的8种浅拷贝方式示例代码

《Java中ArrayList的8种浅拷贝方式示例代码》:本文主要介绍Java中ArrayList的8种浅拷贝方式的相关资料,讲解了Java中ArrayList的浅拷贝概念,并详细分享了八种实现浅... 目录引言什么是浅拷贝?ArrayList 浅拷贝的重要性方法一:使用构造函数方法二:使用 addAll(

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,:本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一:“杨辉三角”题目链接二:题解代码:三:题解思路:总结一:“杨辉三角”题目链接题目链接:点击这里