【图论】图的遍历 - 构建领接表（无向图）

例题：受限条件下可到达节点的数目

题目链接：2368. 受限条件下可到达节点的数目

题目描述

代码与注释

func reachableNodes(n int, edges [][]int, restricted []int) (ans int) {
    r := make(map[int]bool, len(restricted))
    for _, v := range restricted {
        r[v] = true // 把受限的节点设置为 true
    }
    g := make([][]int, n)
    for _, v := range edges { // 建邻接表
        x, y := v[0], v[1]
        if r[x] == false && r[y] == false {
            g[x] = append(g[x], y)
            g[y] = append(g[y], x)
        }
    }
    var dfs func(int, int)
    dfs = func(x, father int) { // dfs 邻接表存储的图
        ans++
        for _, v := range g[x] {
            if v != father { // 避免回溯到父节点导致重复遍历
                dfs(v, x)
            }
        }
    }
    dfs(0, -1) // 从 0 1 开始
    return ans
}
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

模板抽象

建邻接表

for _, v := range edges { // 建邻接表
    x, y := v[0], v[1]
    g[x] = append(g[x], y)
    g[y] = append(g[y], x)
}
1
2
3
4
5

通过领接表 dfs 图

var dfs func(int, int)
dfs = func(x, father int) { // dfs 邻接表存储的图
    for _, v := range g[x] {
        if v != father { // 避免回溯到父节点导致重复遍历
            dfs(v, x)
        }
    }
}
dfs(0, -1) // 从 0 1 开始
1
2
3
4
5
6
7
8
9