0 结果

1 题目

2 思路

• 使用深度搜索（DFS）图，从0开始出发，一边遍历一边把顶点存入到临时路径中，如果遍历到目的点n-1,则把临时路径存入到答案路径ans中；
• 如果从0开始遍历到产生递归回退的时候（即退栈的时候，在图中的含义就是该顶点所连的顶点都已被访问过），每回退一次（每弹出一个顶点），把该顶点重新置为未访问，以便后面其他路径访问。

3 代码

class Solution {
public:
    vector> allPathsSourceTarget(vector>& graph) {
        int n = graph.size();
        vector G[n];
        for(int i = 0; i < n;i++){
            for(int j = 0;j < graph[i].size();j++){
                G[i].push_back(graph[i][j]);
            }
        }

//        for(auto i:G){//打印邻接表
//            for(auto j:i){
//                cout<> ans;
        vector path;
        bool vis[16] = {false};
        auto DFS = [&](int u, int depth){
            auto f = [&](auto&& self, int u, int depth)->void {
                vis[u] = true;
                path.push_back(u);
                if(u == n - 1){
                    ans.push_back(path);
                }
                for(int i = 0; i < G[u].size();i++){
                    int v = G[u][i];
                    if(vis[v] == false){
                        self(self, v, depth + 1);
                    }
                }
                vis[u] = false;
                path.pop_back();
            };
            return f(f, u, depth);
        };
        DFS(0, 0);
        return ans;
    }
};

测试代码：

    //[[1,2],[3],[3],[]]
    //[[4,3,1],[3,2,4],[3],[4],[]]
    //vector>edgs {{1,2}, {3},{3},{}};
    vector>edgs {{4,3,1}, {3,2,4},{3},{4},{}};

    Solution s;
    vector>ans = s.allPathsSourceTarget(edgs);

    cout<