白筱汐

想都是问题,做都是答案

0%

图的深度优先遍历(DFS)

前言

图的深度优先遍历(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"

// 图的深度优先遍历(Depth-First Search,DFS)

// 递归
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) // 1 2 4 8 5 9 3 6 10 7

fmt.Println("======")
dfs2(1) // 1 2 4 8 5 9 3 6 10 7
}