剑指 Offer II 110. 所有路径

dfs

 func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
    
        var tempArray = [Int]()
        var res = [[Int]]()
        let target = graph.count - 1
        dfs(0,graph,target,&tempArray,&res)
        return res
    }
    
    func dfs(_ v:Int,_ graph: [[Int]],_ target:Int,_ tempArray: inout [Int],_ res:inout [[Int]]){
        tempArray.append(v)
        if v == target {
            res.append(tempArray)
            return
        }
        for g in graph[v] {
            dfs(g,graph,target,&tempArray,&res)
            tempArray.removeLast()
        }
  
    }

bfs 没想到是用的二维数组来记录的路径。。每次都基于之前的创建新的数组。感觉性能上没有dfs好
而且找到了目标数组之后。。是在下一步进行的出队= =。。

func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {

        var res = [[Int]]()
        //当前队列
        var q = [[Int]]()
        //最后顶点的编号
        let target = graph.count - 1
        var tempArray = [Int]()
        tempArray.append(0)
        q.append(tempArray)
        while q.count > 0 {
            let p = q.removeLast()
            let lastNode = p.last
            if lastNode == target{
                res.append(p)
                continue
            }
            
            if let lastNode = lastNode{
                
                for g in graph[lastNode]{
                    var nextPath = Array.init(p)
                    nextPath.append(g)
                    q.insert(nextPath, at: 0)
                }
                
            }
            


        }



        return res

    }