# go 图的深度遍历 leetcode797
图的表示有邻接表与邻接矩阵,若没有特殊要求,笔者习惯用邻接表
[leetcode797](https://leetcode-cn.com/problems/all-paths-from-source-to-target/)
## code
```go
// 返回值
var res [][]int
func allPathsSourceTarget(rawGraph [][]int) [][]int {
// 每次都要清空
res = res[0:0]
// 生成邻接表
graph := make(map[int][]int)
for i, v := range rawGraph {
graph[i] = append(graph[i], v...)
}
res := allPath(graph)
return res
}
func allPath(graph map[int][]int) [][]int {
var path []int
nums := len(graph) - 1
// 基础参数准备完毕,开始深度遍历
dfs(0, nums, graph, path)
return res
}
func dfs(start, nums int, graph map[int][]int, path []int) {
path = append(path, start)
// dfs需要出口,必须
if start == nums {
// 这部分取决于题目要求 visited(node)
path1 := make([]int, len(path))
copy(path1, path)
res = append(res, path1)
// 状态回滚
path = path[:len(path)-1]
return
}
// dfs 当前结点的所有子节点
for _, newStart := range graph[start] {
dfs(newStart, nums, graph, path)
}
path = path[:len(path)-1]
}
```
有疑问加站长微信联系(非本文作者))
![](https://static.golangjob.cn/static/img/footer.png?imageView2/2/w/280)