LetCode in Swift (797-All Paths From Source to Target)

文章目录

1. 1. 文档更新说明
2. 2. 前言
3. 3. 796. Rotate String
   1. 3.1. Example
   2. 3.2. Note
   3. 3.3. Solution
4. 4. 阅读推荐

文档更新说明

• 最后更新 2018年03月14日
• 首次更新 2018年03月14日

前言

　　使用Swift语言完成LetCode题目,中等难度,是一道关于图的题目,很好的题目.
　　正所谓做题5分钟,学习2小时.趁做这道题之前,我还是学习了一下图的DFS和BFS算法,学太久都不记得了.文章最后推荐一下学习链接.

796. Rotate String

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

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.

Solution

　　这是一道图论算法题.目标就是找到从节点0到节点n-1的所有路径.
　　图存储在二维数组graph里面, graph[i]表示节点i到所有节点们j的边. 例如例子中的图,graph[0]=[1,2],所以graph[0]表示节点0一共有两条边, 分别指向节点1和节点2.graph[3]=[],说明节点3没有指向任何节点.
　　题目规定给的图是有向图不循环图,所以不需要害怕访问到已经访问的节点.如果是循环的图,就需要加入节点标志,别重复访问变成死循环了.

import Foundation

class Solution_All_Paths_From_Source_to_Target {
    
    var allPaths = [[Int]]()
    var graphCount: Int = 0
    
    func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
        graphCount = graph.count
        dfs(graph: graph, node: 0, path: [Int]())
        return allPaths
    }
    
    func dfs(graph: [[Int]], node: Int, path: [Int]) {
        var path = path
        
        //到达终点(n-1)时,结束递归
        if node == graphCount - 1 {
            path.append(node)
            allPaths.append(path)
            return
        }
        //依次访问和node节点相连通的节点
        for e in graph[node] {
            //图的深度搜索算法, 每一个节点依次递归寻找与其相连通的节点
            //递归之前先将当前节点放入path中,若在递归的最后一层发现可以到达终点(n-1),则将path加入allPaths中
            path.append(node)
            dfs(graph: graph, node: e, path: path)
            //这个地方说明一下,递归回退到这儿的时候,需要把上面加入path的节点去掉!
            //因为如果graph[node]还有其他边,那么for循环会继续并且回到上两行代码,node会重新加入path
            path.removeLast()
        }
    }
}

let s = Solution()
let paths = s.allPathsSourceTarget([[1,2,5], [3], [], [4], [6], [6,7], [], []])
print(paths)

阅读推荐

图的遍历（搜索）算法（深度优先算法DFS和广度优先算法BFS）
广度/宽度优先搜索(BFS)
深度优先搜索(DFS)