Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[LeetCode] 797. All Paths From Source to Target #797

Open
grandyang opened this issue May 30, 2019 · 0 comments
Open

[LeetCode] 797. All Paths From Source to Target #797

grandyang opened this issue May 30, 2019 · 0 comments

Comments

@grandyang
Copy link
Owner

@grandyang grandyang commented May 30, 2019

 

Given a directed, acyclic graph of N nodes.  Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows:  the nodes are 0, 1, ..., graph.length - 1.  graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

  • The number of nodes in the graph will be in the range [2, 15].
  • You can print different paths in any order, but you should keep the order of nodes inside one path.

 

这道题给了我们一个无回路有向图,包含N个结点,然后让我们找出所有可能的从结点0到结点N-1的路径。这个图的数据是通过一个类似邻接链表的二维数组给的,最开始的时候博主没看懂输入数据的意思,其实很简单,我们来看例子中的input,[[1,2], [3], [3], []],这是一个二维数组,最外层的数组里面有四个小数组,每个小数组其实就是和当前结点相通的邻结点,由于是有向图,所以只能是当前结点到邻结点,反过来不一定行。那么结点0的邻结点就是结点1和2,结点1的邻结点就是结点3,结点2的邻结点也是3,结点3没有邻结点。那么其实这道题的本质就是遍历邻接链表,由于要列出所有路径情况,那么递归就是不二之选了。我们用cur来表示当前遍历到的结点,初始化为0,然后在递归函数中,先将其加入路径path,如果cur等于N-1了,那么说明到达结点N-1了,将path加入结果res。否则我们再遍历cur的邻接结点,调用递归函数即可,参见代码如下:

 

解法一:

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> res;
        helper(graph, 0, {}, res);
        return res;
    }
    void helper(vector<vector<int>>& graph, int cur, vector<int> path, vector<vector<int>>& res) {
        path.push_back(cur);
        if (cur == graph.size() - 1) res.push_back(path);
        else for (int neigh : graph[cur]) helper(graph, neigh, path, res);
    }
};

 

下面这种解法也是递归,不过写法稍有不同,递归函数直接返回结果,这样参数就少了许多,但是思路还是一样的,如果cur等于N-1了,直接将cur先装入数组,再装入结果res中返回。否则就遍历cur的邻接结点,对于每个邻接结点,先调用递归函数,然后遍历其返回的结果,对于每个遍历到的path,将cur加到数组首位置,然后将path加入结果res中即可,这有点像是回溯的思路,路径是从后往前组成的,参见代码如下:

 

解法二:

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        return helper(graph, 0);
    }
    vector<vector<int>> helper(vector<vector<int>>& graph, int cur) {
        if (cur == graph.size() - 1) {
            return {{graph.size() - 1}};
        }
        vector<vector<int>> res;
        for (int neigh : graph[cur]) {
            for (auto path : helper(graph, neigh)) {
                path.insert(path.begin(), cur);
                res.push_back(path);
            }
        }
        return res;
    }
};

 

类似题目:

https://leetcode.com/problems/all-paths-from-source-to-target/solution/

https://leetcode.com/problems/all-paths-from-source-to-target/discuss/121135/6-lines-C++-dfs

https://leetcode.com/problems/all-paths-from-source-to-target/discuss/118691/Easy-and-Concise-DFS-Solution-C++-2-line-Python

 

LeetCode All in One 题目讲解汇总(持续更新中...)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
1 participant
You can’t perform that action at this time.