Day55卡玛笔记

这是基于代码随想录的每日打卡

所有可达路径 题目描述

​ 给定一个有 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

---

邻接矩阵法

def dfs(matrices,path,res,node,n): if node==n: res.append(path[:]) return for i in range(1,n+1): # 每层有n个叶子节点 if matrices[node][i]==1: path.append(i) dfs(matrices,path,res,i,n) path.pop() # 回溯 def main(): n,m=map(int,input().split()) # 创建邻接矩阵 matrices=[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(m): start,end=map(int,input().split()) matrices[start][end]=1 res=[] dfs(matrices,[1],res,1,n) if len(res)==0: print(-1) else: for path in res: print(' '.join(map(str,path))) if __name__=='__main__': main()

运行结果

---

邻接表法

from collections import defaultdict def dfs(graph,res,path,node,n): if node==n: res.append(path[:]) return for i in graph[node]: # 遍历每层叶子节点 path.append(i) dfs(graph,res,path,i,n) path.pop() # 回溯 def main(): n,m=map(int,input().split()) # 创建邻接表 graph=defaultdict(list) for _ in range(m): start,end=map(int,input().split()) graph[start].append(end) res=[] dfs(graph,res,[1],1,n) if not res: print(-1) else: for path in res: print(' '.join(map(str,path))) if __name__=='__main__': main()

运行结果

---

797. 所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 1：

输入：graph = [[1,2],[3],[3],[]] 输出：[[0,1,3],[0,2,3]] 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2：

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]] 输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

---

class Solution: def __init__(self): self.path=[] self.res=[] def dfs(self,graph,node,n): if node==n-1: self.res.append(self.path[:]) return for node in graph[node]: self.path.append(node) self.dfs(graph,node,n) self.path.pop() def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: self.path.append(0) self.dfs(graph, 0, len(graph)) return self.res

运行结果