這是基于代碼隨想錄的每日打卡

所有可達路徑

題目描述

? 給定一個有 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[:])returnfor 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]=1res=[]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. 所有可能的路徑

輸入：graph = [[1,2],[3],[3],[]]
輸出：[[0,1,3],[0,2,3]]
解釋：有兩條路徑 0 -> 1 -> 3 和 0 -> 2 -> 3

輸入：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