前言
图的深度优先遍历(Depth-First Search,DFS))是一种用于遍历图中所有节点的算法。它从图中的一个起始节点开始,沿着路径尽可能深地访问图中的节点,直到无法继续前进。然后回溯到上一个节点,继续探索其他未访问的节点,直到所有节点都被访问过为止。
js代码实现
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 39 40 41 42 43 44 45 46
| const graph = { 1: [2, 3], 2: [4, 5], 3: [6, 7], 4: [8], 5: [9], 6: [10], };
const visited = new Set();
function dfs(n) { console.log(n) visited.add(n)
const neighbors = graph[n]; if (neighbors) { for (let i = 0; i < neighbors.length; i++) { if (!visited.has(neighbors[i])) { dfs(neighbors[i]) } } } }
function dfs2(start) { const stack = [start] const visited = new Set() while (stack.length) { const n = stack.pop() console.log(n) visited.add(n)
const neighbors = graph[n] if (neighbors) { for (let i = neighbors.length - 1; i >= 0; i--) { if (!visited.has(neighbors[i])) { stack.push(neighbors[i]) } } } } }
|
go代码实现
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| package main
import "fmt"
func dfs(n int, visited map[int]bool) { visited[n] = true fmt.Println(n) for _, c := range graph[n] { if !visited[c] { dfs(c, visited) } } }
func dfs2(n int) { visited := make(map[int]bool) stack := []int{n} for len(stack) > 0 { n := stack[len(stack)-1] stack = stack[:len(stack)-1] visited[n] = true fmt.Println(n)
neighbors := graph[n] for i := len(neighbors) - 1; i >= 0; i-- { if !visited[neighbors[i]] { stack = append(stack, neighbors[i]) } } } }
var graph = map[int][]int{ 1: {2, 3}, 2: {4, 5}, 3: {6, 7}, 4: {8}, 5: {9}, 6: {10}, }
func main() { visited := make(map[int]bool) dfs(1, visited)
fmt.Println("======") dfs2(1) }
|