一道典型的DFS

Note swift algorithm leetcode DFS算法

Word count: 584Reading time: 2 min

 2021/08/25 

Leetcode 797.所有可能的路径，看这个名字就是DFS的味道…

题目描述：给你一个有 n 个节点的有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）。二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
示例：输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

很显然，这个题目需要在图中搜索出所有符合条件的路径，自然而然我们可以想到DFS，即深度优先搜索。并且题目已经规定2 <= n <= 15，所以不会超时。
我们从0号节点出发，遍历它能走到的节点，在示例中就是1和2。然后再深度优先搜索1和2所能走到的节点，如果走到了n-1号节点，说明我们找到了一条符合条件的路径，于是把这条路径加入到结果集中。需要注意的是，我们在swift中需要使用Array来记录走过的路径，而我们在操作路径时需要遵循尾进尾出的原则，所以需要使用append()和removeLast()

本题中已经指定为有向无环图，所以我们不需要再另外记录在本次搜索中已走过的节点，如果是有环，为避免反复经过同一个节点，需要记录当前搜索已走过的节点。

以下为实现代码

class Solution {
    var ans = [[Int]]()
    var stack = [Int]()

    func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
        stack.append(0)
        dfs(graph,0)
        return ans
    }

    func dfs(_ graph: [[Int]] , _ start: Int) {
        if start == graph.count - 1
        {
            ans.append(stack)
            return
        }

        for node in graph[start] {
            stack.append(node)
            dfs(graph,node)
            stack.removeLast()
        }
    }
}

总结

DFS和BFS在算法题中是非常高频出现的考点，这道题是比较典型的DFS。虽然说一看题目就有思路，但是代码写起来还是比较生涩，学习算法理论以及应用的时候也要注意训练怎么用代码来做具体实现，要多练习这个难度的中等题。

Next Post

找出链表的倒数第N个结点
Previous Post

最大回文子串(Leetcode no.5)

CATALOG

1. 总结