AllPathsFromSourceToTarget [source code]
public class AllPathsFromSourceToTarget {
static
/******************************************************************************/
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
int N = graph.length;
List<List<Integer>> lss = new ArrayList<> ();
Deque<Edge> stack = new ArrayDeque<> ();
Deque<Integer> path = new ArrayDeque<> ();
stack.push (new Edge (-1, 0));
while (!stack.isEmpty ()) {
Edge cur = stack.pop ();
while (!path.isEmpty () && path.peekLast() != cur.parent)
path.removeLast ();
path.addLast (cur.val);
if (cur.val == N - 1 || graph[cur.val].length == 0) {
if (cur.val == N - 1)
lss.add (new ArrayList<> (path));
path.removeLast ();
} else {
for (int num : graph[cur.val])
stack.push (new Edge (cur.val, num));
}
}
return lss;
}
static class Edge {
int parent, val;
Edge (int p, int v) {
this.parent = p;
this.val = v;
}
public String toString () {
return String.format ("[%d->%d]", parent, val);
}
}
}
/******************************************************************************/
public static void main(String[] args) {
AllPathsFromSourceToTarget.Solution tester = new AllPathsFromSourceToTarget.Solution();
int[][][] inputs = {
{{1,2}, {3}, {3}, {}}, {{0,1,3},{0,2,3}},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int[][] graph = inputs[i];
Set<List<Integer>> output = new HashSet<> (tester.allPathsSourceTarget (graph));
Set<List<Integer>> ans = new HashSet<> ();
for (int[] ar : inputs[2 * i + 1]) {
List<Integer> ls = new ArrayList<> ();
for (int k : ar)
ls.add (k);
ans.add (ls);
}
System.out.printf ("%s -> %s, expected: %s\n",
Arrays.deepToString (graph), Printer.wrap (output.toString (), output.equals (ans) ? 92 : 91), ans
);
}
}
}
先画了一下给的这个例子, 发现是一个directed的情形; 这个自己写的时候也要问一下, graph问题, 是不是directed, 区别还是挺大的;
找all path好像没有什么幺蛾子, 直接BFS搜行不行? 暂时想不到why not, 先这样谢谢看; 因为没有overlapping, 所以BFS没有什么特别的难度;
不对, 这个题是有可能有overlapping的; 那么mark的时候就要稍微注意一下顺序, 应该是enqueue的时候就mark; 不对, enqueue的时候mark有问题: 这里是找all path; 所以enqueue的时候mark就会导致如果一个node有多个parent, 有一个parent对应的path就被排除掉了;
事实上, 这题整个就不应该用visited, 就算Poll出来的时候mark, 还是有问题, 上面描述的情况还是会被排除;
另外, 这题为了维护path, 我感觉DFS好一些;
当然实际上肯定是用recursion好一点, 但是这题很蛋疼的是, 我最后还是希望自己用iterative的做法做做看;
但是没有想到的是, 这题的iterative的做法, 完全就不好写, 超时花了不少时间之后, 还算是写出来了, 速度是25ms (NA).
注意, Stack的DFS做法, 虽然可以达到正确的DFS的traversal的顺序, 但是没有recursion的DFS那种很方便的, 完成一个child的探索之后, 会自动返回parent的操作, 而是直接就跳到下一个需要走的位置了; 这个在需要维护的path类的backtrack问题当中, 会造成相当的麻烦; 最后解决的办法是, 我让每一个node都维护自己的parent, 这样每次走到一个新的node的时候, 就知道path里面应该剩下的是多少: 多余的全都pop掉;
我自己对于复杂度的解释:
The complexity can be a little tricky to think about. The stack only contributes O(N) complexity obviously. Does the popping of path in the beginning of the iteration adds overhead to the complexity? Note that each node is popped only once from path, so path also only contributes O(N) complexity.
editorial
Approach #1: Recursion [Accepted]
Intuition
Since the graph is a directed, acyclic graph, any path from A to B is going to be composed of A plus a path from any neighbor of A to B. We can use a recursion to return the answer.
Algorithm
Let N be the number of nodes in the graph. If we are at node N-1, the answer is just the path {N-1}. Otherwise, if we are at node node, the answer is {node} + {path from nei to N-1} for each neighbor nei of node. This is a natural setting to use a recursion to form the answer.
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
return solve(graph, 0);
}
public List<List<Integer>> solve(int[][] graph, int node) {
int N = graph.length;
List<List<Integer>> ans = new ArrayList();
if (node == N - 1) {
List<Integer> path = new ArrayList();
path.add(N-1);
ans.add(path);
return ans;
}
for (int nei: graph[node]) {
for (List<Integer> path: solve(graph, nei)) {
path.add(0, node);
ans.add(path);
}
}
return ans;
}
}
还是比较聪明的, 一个returned recursion完成, 而不是用backtracking; 不过我感觉这题backtracking应该也是不难写的;
void dfs(vector<vector<int>>& graph, vector<vector<int>>& result, vector<int> path, int src, int dst) {
path.push_back(src);
if(src == dst) {
result.push_back(path);
return;
}
for(auto it = graph[src].begin(); it != graph[src].end(); it++)
dfs(graph, result, path, *it, dst);
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> paths; vector<int> path;
int nodes = graph.size();
if(nodes == 0) return paths;
dfs(graph, paths, path, 0, nodes - 1);
return paths;
}
所以这题(上行返回上来之后), 是不需要undo的, 因为只是单纯的想要完成一个搜索行为而已; 不对, 有点奇怪;
这个是正常的backtrack做法:
void recordPaths(vector<vector<int>>& graph, int node, vector<int>& path, vector<vector<int>>& results) {
if (node == graph.size()-1) {
results.push_back(path);
return;
}
for (int other : graph[node]) {
path.push_back(other);
recordPaths(graph, other, path, results);
path.pop_back();
}
return;
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> results;
vector<int> path(1, 0);
recordPaths(graph, 0, path, results);
return results;
}
难怪, 原来OP用的是c++的pass by value:
@nickyh You are avoiding a copy of path variable on every call to recordPaths at expense of one pop_back operation. There is space-time trade-off. :)
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(0);
dfsSearch(graph, 0, res, path);
return res;
}
private void dfsSearch(int[][] graph, int node, List<List<Integer>> res, List<Integer> path) {
if (node == graph.length - 1) {
res.add(new ArrayList<Integer>(path));
return;
}
for (int nextNode : graph[node]) {
path.add(nextNode);
dfsSearch(graph, nextNode, res, path);
path.remove(path.size() - 1);
}
}
}
一本正经的java的backtracking做法;
uwi:
class Solution {
List<List<Integer>> ret;
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
ret = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(0, graph, path);
return ret;
}
void dfs(int cur, int[][] g, List<Integer> path)
{
path.add(cur);
if(cur == g.length-1){
ret.add(new ArrayList<>(path));
}else{
for(int e : g[cur]){
dfs(e, g, path);
}
}
path.remove(path.size()-1);
}
}
简单的backtrack;
Problem Description
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.
Difficulty:Medium
Total Accepted:2.5K
Total Submissions:3.6K
Contributor:awice