難度：★★★☆☆
類型：圖
方法：深度優(yōu)先搜索
力扣鏈接請移步本題傳送門
更多力扣中等題的解決方案請移步力扣中等題目錄
題目
給一個有 n 個結(jié)點的有向無環(huán)圖饵隙，找到所有從 0 到 n-1 的路徑并輸出（不要求按順序）
二維數(shù)組的第 i 個數(shù)組中的單元都表示有向圖中 i 號結(jié)點所能到達的下一些結(jié)點（譯者注：有向圖是有方向的，即規(guī)定了 a→b 你就不能從 b→a ）空就是沒有下一個結(jié)點了闸氮。
示例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]]
示例 3：
輸入：graph = [[1],[]]
輸出：[[0,1]]
示例 4：
輸入：graph = [[1,2,3],[2],[3],[]]
輸出：[[0,1,2,3],[0,2,3],[0,3]]
示例 5：
輸入：graph = [[1,3],[2],[3],[]]
輸出：[[0,1,2,3],[0,3]]
提示：
結(jié)點的數(shù)量會在范圍 [2, 15] 內(nèi)蛉谜。
你可以把路徑以任意順序輸出国夜，但在路徑內(nèi)的結(jié)點的順序必須保證。
解答
這個題是圖遍歷的經(jīng)典題逼庞，可以使用深度優(yōu)先搜索方法實現(xiàn)俱诸。
定義深度優(yōu)先搜索函數(shù)get_paths_from()，函數(shù)的輸入是起始節(jié)點的編號node维雇，函數(shù)輸出是以node節(jié)點為起點淤刃，到達終止節(jié)點dst_node的所有可能的路徑，以嵌套列表的形式返回吱型。函數(shù)完成的功能即為路徑搜尋逸贾。
一般使用深度優(yōu)先搜索函數(shù)會在入口處添加終止條件作為遞歸終點，這道題的終止條件即為到達終點津滞。也就是說铝侵，當起點結(jié)點node即為終點結(jié)點dst_node時，說明成功到達終點触徐，返回這條唯一的路徑[[dst_node]]咪鲜，注意這里要嵌套兩層列表，因為內(nèi)部的列表表示一條路徑撞鹉。
當輸入節(jié)點node不滿足遞歸終點時（也是大多數(shù)情況）疟丙，我們就要搜尋node節(jié)點的下一跳結(jié)點，可能有多個鸟雏，然后遍歷這些下一跳結(jié)點next_node享郊，以next_node為起點進行遞歸調(diào)用，獲得以next_node為起點孝鹊，到達dst_node的所有路線炊琉，然后將這些路線加到當前結(jié)點node上。
這里不用擔(dān)心如果不存在node到dst_node的路線時的情況又活。因為如果不存在這些情況苔咪，路線列表是空的，不會進行遍歷皇钞。
其他變量說明：
src_node悼泌，dst_node：起點和終點結(jié)點編號。
nums：圖中結(jié)點總數(shù)夹界。
class Solution(object):
def allPathsSourceTarget(self, graph):
nums = len(graph)
src_node, dst_node = 0, nums - 1
def get_paths_from(node):
if node == dst_node:
return [[dst_node]]
ans = []
for next_node in graph[node]:
for path in get_paths_from(next_node):
ans.append([node] + path)
return ans
return get_paths_from(src_node)
如有疑問或建議馆里，歡迎評論區(qū)留言~
有關(guān)更多力扣中等題的python解決方案隘世，請移步力扣中等題解析
