###### tags: `Leetcode` `medium` `graph` `bfs` `backtracking` `python` `c++`

# 797. All Paths From Source to Target

## [題目連結:] https://leetcode.com/problems/all-paths-from-source-to-target/description/

## 題目:

## 解題想法:
* 此題為給一graph:
* 共有n點，為0~(n-1)
* graph[i]=[j,k]表示:
* i連到j
* i連到k
* 求所有從0走到(n-1)的路徑

* 使用bfs遍歷
* 初始需要:
* res=[]: 紀錄最終結果
* que=[[0]]:
* 使用queue裝path，起點為節點0
* while que:
* 每次pop出路徑: curPath
* **curLast紀錄curPath最後一點**
* 若curLast已經為節點(n-1)，表示curPath已經從頭到尾了，可加入到res
* for neighber in graph[curLast]: **拜訪鄰居**
* 從curLast的鄰居繼續做延伸
* 創建新list加入queue

            tmpPath=list(curPath)
            tmpPath.append(neighber)
            que.append(tmpPath)

## Python:

class Solution(object):
    def allPathsSourceTarget(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[List[int]]
        """
        #bfs
        n=len(graph)
        res=[]
        que=[[0]]
        while que:
            curPath=que.pop(0)
            curLast=curPath[-1]
            #若該curPath最後一點為節點(n-1)，表示為該path已經從頭到尾了
            if curLast==(n-1):
                res.append(curPath)
            #從curPath最後一點的鄰居繼續做延伸
            for neighber in graph[curLast]:
                #create new list
                tmpPath=list(curPath)
                tmpPath.append(neighber)
                que.append(tmpPath)
        return res
    
result=Solution()
ans=result.allPathsSourceTarget(graph = [[4,3,1],[3,2,4],[3],[4],[]])
print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<vector<int>> res;
        queue<vector<int>> que;
        que.push({0});
        while (!que.empty()){
            vector<int> curPath=que.front(); que.pop();
            int curLast=curPath.back();
            if (curLast==n-1) res.push_back(curPath);
            for (auto neighber: graph[curLast]){
                //copy curPath
                vector<int> tmp(curPath);
                tmp.push_back(neighber);
                que.push(tmp);
            }
        }
        return res;
    }
};