【代码随想录训练营第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

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

Java 创建图形用户界面(GUI)入门指南(Swing库 JFrame 类)概述

概述 基本概念 Java Swing 的架构 Java Swing 是一个为 Java 设计的 GUI 工具包,是 JAVA 基础类的一部分,基于 Java AWT 构建,提供了一系列轻量级、可定制的图形用户界面(GUI)组件。 与 AWT 相比,Swing 提供了许多比 AWT 更好的屏幕显示元素,更加灵活和可定制,具有更好的跨平台性能。 组件和容器 Java Swing 提供了许多

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站,手机流量可以访问IPV6网络的服务,为什么不在电脑搭建Home Assistant(hass),来控制你的设备呢?@智能家居 @万物互联

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm