深度优先搜索(所有可达路径)

参考题目:所有可达路径

题目描述

        给定一个有 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(深度优先搜索)的框架代码,什么叫做深度优先搜索算法呢?就是一路走到底,直到无路可走的时候,就回退,寻找其它的出路,存储的数据结构可以使用邻接表、邻接矩阵的等等,如果还是不太理解:代码随想录

n, m = map(int, input().split())
Map = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    Map[a].append(b)
stack = []  
ans = []
def dfs(start, target):
    stack.append(start)
    if start == target:
        ans.append(stack[:])
    else:
        for next in Map[start]:
            dfs(next, target)
    stack.pop()
dfs(1, n)
if len(ans):
    for path in ans:
        path_len = len(path)
        for i in range(path_len):
            if i != path_len - 1:  # 换不换行
                print(f"{path[i]} ", end='')
            else:
                print(f"{path[i]}")
else:
    print(-1)

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-11 00:22:04       4 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-11 00:22:04       5 阅读
  3. 在Django里面运行非项目文件

    2024-07-11 00:22:04       4 阅读
  4. Python语言-面向对象

    2024-07-11 00:22:04       4 阅读

热门阅读

  1. vue详解

    vue详解

    2024-07-11 00:22:04      8 阅读
  2. 深度学习与浅层学习:技术变革下的竞争态势

    2024-07-11 00:22:04       13 阅读
  3. 大数据面试题之ElasticSearch(1)

    2024-07-11 00:22:04       8 阅读
  4. 基于深度学习的异常行为检测

    2024-07-11 00:22:04       6 阅读
  5. 深入解析 MySQL 的 SHOW FULL PROCESSLIST

    2024-07-11 00:22:04       8 阅读
  6. 使用conda安装openturns

    2024-07-11 00:22:04       8 阅读
  7. c++的constexpr和constvalue的区别

    2024-07-11 00:22:04       9 阅读
  8. LASA数据集

    2024-07-11 00:22:04       11 阅读
  9. MySQL 条件函数/加密函数/转换函数

    2024-07-11 00:22:04       11 阅读
  10. Unity Addressable魔改

    2024-07-11 00:22:04       9 阅读
  11. Android关闭SLinux

    2024-07-11 00:22:04       11 阅读