go 图的深度遍历 leetcode797

letterbeezps · · 720 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

# 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] } ```

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

720 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传