宽度优先搜索与图论入门
摘要
- 宽度优先搜索的适用场景
- 宽度优先搜索的三种实现方法
- 两个队列的实现方法
- DummyNode的实现方法
- 一个队列的实现方法
- 无向图和有向图的存储方法
BFS 的适用场景
- 分层遍历
- 一层一层的遍历一个图、树、矩阵
- 简单图最短路径
- 简单图的定义是，图中所有的边长都一样
- 连通块问题
- 通过图中一个点找到其他所有连通的点
- 找到所有方案问题的一种非递归实现方式
- 拓扑排序
- 实现容易度远超过 DFS
BFS 的三种实现方法
69 · 二叉树的层次遍历
给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）
单队列实现方法
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func LevelOrder1(root *TreeNode) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
q := []*TreeNode{root}
for len(q) > 0 {
var level []int
len := len(q)
for i := 0; i < len; i++ {
node := q[i]
level = append(level, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
res = append(res, level)
q = q[len:]
}
return res
}
双队列的实现方法
func LevelOrder2(root *TreeNode) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
q := []*TreeNode{root}
for len(q) > 0 {
var level []int
var nq []*TreeNode
for _, node := range q {
level = append(level, node.Val)
if node.Left != nil {
nq = append(nq, node.Left)
}
if node.Right != nil {
nq = append(nq, node.Right)
}
}
res = append(res, level)
q = nq
}
return res
}
DummyNode 的实现方法
空指针 nil 用来区分层级
func LevelOrder3(root *TreeNode) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
q := []*TreeNode{root, nil}
var level []int
for len(q) > 0 {
node := q[0]
q = q[1:]
if node == nil {
res = append(res, level)
level = nil
if len(q) > 0 {
q = append(q, nil)
}
continue
}
level = append(level, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
return res
}
无向图和有向图的存储方法
邻接矩阵 (Adjacency Matrix)
邻接矩阵是一种二维数组或切片，用来表示图中节点之间的连接。对于无向图，矩阵是对称的；对于有向图，矩阵不一定对称。
无向图的邻接矩阵
package main
import "fmt"
func main() {
// 假设有 4 个节点
n := 4
// 初始化邻接矩阵
adjMatrix := make([][]int, n)
for i := range adjMatrix {
adjMatrix[i] = make([]int, n)
}
// 添加边 0-1，1-2，2-3，3-0
adjMatrix[0][1] = 1
adjMatrix[1][0] = 1
adjMatrix[1][2] = 1
adjMatrix[2][1] = 1
adjMatrix[2][3] = 1
adjMatrix[3][2] = 1
adjMatrix[3][0] = 1
adjMatrix[0][3] = 1
fmt.Println("无向图的邻接矩阵:")
for _, row := range adjMatrix {
fmt.Println(row)
}
}
无向图的邻接矩阵:
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]
有向图的邻接矩阵
package main
import "fmt"
func main() {
// 假设有 4 个节点
n := 4
// 初始化邻接矩阵
adjMatrix := make([][]int, n)
for i := range adjMatrix {
adjMatrix[i] = make([]int, n)
}
// 添加有向边 0->1, 1->2, 2->3, 3->0
adjMatrix[0][1] = 1
adjMatrix[1][2] = 1
adjMatrix[2][3] = 1
adjMatrix[3][0] = 1
fmt.Println("有向图的邻接矩阵:")
for _, row := range adjMatrix {
fmt.Println(row)
}
}
有向图的邻接矩阵:
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 0 0 0]
邻接表 (Adjacency List)
邻接表使用切片的切片或字典来存储图中节点之间的连接。每个节点对应一个切片，其中包含所有连接的节点。
无向图的邻接表
package main
import "fmt"
func main() {
// 假设有 4 个节点
n := 4
// 初始化邻接表
adjList := make([][]int, n)
// 添加边 0-1，1-2，2-3，3-0
adjList[0] = append(adjList[0], 1)
adjList[1] = append(adjList[1], 0)
adjList[1] = append(adjList[1], 2)
adjList[2] = append(adjList[2], 1)
adjList[2] = append(adjList[2], 3)
adjList[3] = append(adjList[3], 2)
adjList[3] = append(adjList[3], 0)
adjList[0] = append(adjList[0], 3)
fmt.Println("无向图的邻接表:")
for i, neighbors := range adjList {
fmt.Printf("%d: %v\n", i, neighbors)
}
}
无向图的邻接表:
0: [1 3]
1: [0 2]
2: [1 3]
3: [2 0]
有向图的邻接表
package main
import "fmt"
func main() {
// 假设有 4 个节点
n := 4
// 初始化邻接表
adjList := make([][]int, n)
// 添加有向边 0->1, 1->2, 2->3, 3->0
adjList[0] = append(adjList[0], 1)
adjList[1] = append(adjList[1], 2)
adjList[2] = append(adjList[2], 3)
adjList[3] = append(adjList[3], 0)
fmt.Println("有向图的邻接表:")
for i, neighbors := range adjList {
fmt.Printf("%d: %v\n", i, neighbors)
}
}
有向图的邻接表:
0: [1]
1: [2]
2: [3]
3: [0]
总结
- 邻接矩阵: 使用二维数组表示图，适用于节点较少且图比较稠密的情况。
- 邻接表: 使用切片的切片或字典表示图，适用于节点较多且图比较稀疏的情况。
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。