问题：
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:
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.
方法：
深度优先遍历，按照数组中存储的路径遍历，遍历所有的path即可得到结果。
具体实现：
class AllPathsFromSourceToTarget {
fun allPathsSourceTarget(graph: Array<IntArray>): List<List<Int>> {
val result = mutableListOf<List<Int>>()
val path = mutableListOf<Int>()
path.add(0)
dfsSearch(graph, path, result, 0)
path.remove(0)
return result
}
private fun dfsSearch(graph: Array<IntArray>, path: MutableList<Int>, result: MutableList<List<Int>>, node: Int) {
if (node == graph.lastIndex) {
result.add(ArrayList<Int>(path))
return
}
for (nextNode in graph[node]) {
path.add(nextNode)
dfsSearch(graph, path, result, nextNode)
path.remove(nextNode)
}
}
}
fun main(args: Array<String>) {
val arrays = arrayOf(intArrayOf(1,2), intArrayOf(3), intArrayOf(3), intArrayOf())
val allPathsFromSourceToTarget = AllPathsFromSourceToTarget()
val result = allPathsFromSourceToTarget.allPathsSourceTarget(arrays)
}
有问题随时沟通
