文章目录
  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没有指向任何节点.
  题目规定给的图是有向图不循环图,所以不需要害怕访问到已经访问的节点.如果是循环的图,就需要加入节点标志,别重复访问变成死循环了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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)

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