非常感謝你閱讀本文~
歡迎【?點(diǎn)贊】【?收藏】【?評(píng)論】~
放棄不難，但堅(jiān)持一定很酷~
希望我們大家都能每天進(jìn)步一點(diǎn)點(diǎn)~
本文由 二當(dāng)家的白帽子：https://le-yi.blog.csdn.net/ 博客原創(chuàng)~

劍指 Offer II 110. 所有路徑｜797. 所有可能的路徑：

給定一個(gè)有 n 個(gè)節(jié)點(diǎn)的有向無環(huán)圖，用二維數(shù)組 graph 表示，請(qǐng)找到所有從 0 到 n-1 的路徑并輸出（不要求按順序）。

graph 的第 i 個(gè)數(shù)組中的單元都表示有向圖中 i 號(hào)節(jié)點(diǎn)所能到達(dá)的下一些結(jié)點(diǎn)（譯者注：有向圖是有方向的，即規(guī)定了 a→b 你就不能從 b→a ），若為空，就是沒有下一個(gè)節(jié)點(diǎn)了。

樣例 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]]

提示：

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i
• 保證輸入為有向無環(huán)圖 (GAD)

分析

• 這道算法題幸好是 無環(huán)圖 ，要不然就沒那么簡(jiǎn)單了。
• 遍歷路徑，找到所有可以到達(dá)終點(diǎn)節(jié)點(diǎn)的路徑就是結(jié)果。
• 大部分語(yǔ)言的題解都是用的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，所以可以規(guī)避一個(gè)問題，那就是你要提前知道結(jié)果集的最大數(shù)量。
• C語(yǔ)言由于是手動(dòng)去申請(qǐng)內(nèi)存，所以需要知道結(jié)果集的最大數(shù)量，當(dāng)然去申請(qǐng)很大的內(nèi)存肯定就夠放，但是本著算法精神，我們應(yīng)該申請(qǐng)剛好夠用的內(nèi)存。
• 提示中說 保證輸入為有向無環(huán)圖 (GAD) ，所以我們可以認(rèn)為節(jié)點(diǎn)間一定有著某種排列的順序，從頭到尾怎樣可以有最多的路徑呢，那就是在保證沒有環(huán)路的情況下，所有節(jié)點(diǎn)都盡可能多的連接著其他節(jié)點(diǎn)。
• 開始節(jié)點(diǎn)可以直接到終點(diǎn)節(jié)點(diǎn)…途徑任何一個(gè)節(jié)點(diǎn)都能到終點(diǎn)…途徑任何二個(gè)節(jié)點(diǎn)都能到終點(diǎn)…以此類推，所以中間的節(jié)點(diǎn)就成了可以任意組合，一共多少種組合，每個(gè)節(jié)點(diǎn)都是經(jīng)過或者不經(jīng)過兩種可能，由于頭尾的節(jié)點(diǎn)是必經(jīng)經(jīng)過的，所以最多結(jié)果集的數(shù)量就是 (n - 2)² , 也就是 1 << n - 2。

題解

java

class Solution {    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {        List<List<Integer>> ans   = new ArrayList<>();        Deque<Integer>      stack = new ArrayDeque<>();        stack.offerLast(0);        dfs(graph, stack, ans);        return ans;    }    private void dfs(int[][] graph, Deque<Integer> stack, List<List<Integer>> ans) {        if (stack.peekLast() == graph.length - 1) {            ans.add(new ArrayList<>(stack));            return;        }        for (int to : graph[stack.peekLast()]) {            stack.offerLast(to);            dfs(graph, stack, ans);            stack.pollLast();        }    }}

c

void dfs(int **graph, int *graphColSize, int *returnSize, int **returnColumnSizes, int n, int *stack, int stackSize, int **ans) {    int last = stack[stackSize - 1];    if (last == n) {        int *row = malloc(sizeof(int) * stackSize);        memcpy(row, stack, sizeof(int) * stackSize);        ans[*returnSize] = row;        (*returnColumnSizes)[(*returnSize)++] = stackSize;        return;    }    for (int i = 0; i < graphColSize[last]; ++i) {        int to = graph[last][i];        stack[stackSize] = to;        dfs(graph, graphColSize, returnSize, returnColumnSizes, n, stack, stackSize + 1, ans);    }}/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes){    *returnSize = 0;    *returnColumnSizes = malloc(sizeof(int) * (1 << graphSize - 2));    int **ans = malloc(sizeof(int *) * (1 << graphSize - 2));    int *stack = malloc(sizeof(int) * graphSize);    stack[0] = 0;    dfs(graph, graphColSize, returnSize, returnColumnSizes, graphSize - 1, stack, 1, ans);    return ans;}

c++

class Solution {private:    void dfs(vector<vector<int>>& graph, vector<int>& stack, vector<vector<int>>& ans) {        if (stack.back() == graph.size() - 1) {            ans.push_back(stack);            return;        }        for (auto& to : graph[stack.back()]) {            stack.push_back(to);            dfs(graph, stack, ans);            stack.pop_back();        }    }public:    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {        vector<vector<int>> ans;        vector<int> stack;        stack.push_back(0);        dfs(graph, stack, ans);        return ans;    }};

python

class Solution:    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:        ans = list()        stack = list()        def dfs():            last = stack[len(stack) - 1]            if last == len(graph) - 1:                ans.append(stack[:])                return            for to in graph[last]:                stack.append(to)                dfs()                stack.pop()        stack.append(0)        dfs()        return ans        

go

func allPathsSourceTarget(graph [][]int) (ans [][]int) {	n := len(graph) - 1	stack := []int{0}	var dfs func()	dfs = func() {		last := stack[len(stack)-1]		if last == n {			ans = append(ans, append([]int{}, stack...))			return		}		for _, to := range graph[last] {			stack = append(stack, to)			dfs()			stack = stack[:len(stack)-1]		}	}	dfs()	return}

rust

impl Solution {    pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {        let mut ans: Vec<Vec<i32>> = Vec::new();        let mut stack: Vec<i32> = Vec::new();        stack.push(0);        Solution::dfs(&graph, graph.len() as i32 - 1, &mut stack, &mut ans);        ans    }    fn dfs(graph: &Vec<Vec<i32>>, n: i32, stack: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {        let last = stack[stack.len() - 1];        if last == n {            ans.push(stack.clone());            return;        }        graph[last as usize].iter().for_each(|to| {            stack.push(to.clone());            Solution::dfs(graph, n, stack, ans);            stack.pop();        });    }}

原題傳送門：https://leetcode-cn.com/problems/bP4bmD/

原題傳送門：https://leetcode-cn.com/problems/all-paths-from-source-to-target/