白筱汐

想都是问题，做都是答案

0%

图的广度优先遍历 (BFS)

发表于 更新于 分类于

前言

图的广度优先遍历（Breadth-First Search，BFS）是一种用于遍历或搜索图的算法。它从图中的某个节点开始，按照广度优先的顺序逐层遍历图的节点，直到遍历完所有可达节点为止。

本案例介绍的是”非加权图“的广度优先遍历。一般用来解决两类问题：

1、从节点A出发，有前往节点B的路径吗？

2、从节点A出发，前往节点B的哪条路径最短

队列是一种先进先出的数据结构（First In First Out,FIFO）,队列只有两种操作，入队和出队。

为了方便展示节点之间的关系，案例中使用“邻接表”的方式展示图。

1
2
3
4
5
6
7
8
9
// 示例图的邻接表
let graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

基本步骤

1.选择一个起始节点，并将其标记为已访问

2.将起始节点加入队列

3.重复以下步骤直到队列为空：

  • 从队列中取出一个节点，作为当前节点。
  • 遍历当前节点的所有相邻节点（未访问过的节点），并将它们标记为已访问。
  • 将这些相邻节点加入队列。

4.当队列为空时，遍历结束。

js代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bfs(graph, startNode) {
    let queue = [startNode]  // 使用队列保存待访问的节点
    let visited = new Set() // 使用 Set 数据结构记录已访问的节点
    visited.add(startNode)
    while (queue.length > 0) {
        const n = queue.shift()  // 出队一个节点
        graph[n].forEach(c => {
            // (未访问过的)将相邻节点设置为已访问并加入队列
            if (!visited.has(c)) {
                visited.add(c) 
                queue.push(c); 
            }
        })
    }
    return Array.from(visited)
}

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
54
55
56
package main

import "fmt"

// GraphNode 定义图的结构
type GraphNode struct {
	value    int
	adjacent []*GraphNode
	visited  bool
}

func NewGraphNode(value int) *GraphNode {
	return &GraphNode{
		value:    value,
		adjacent: make([]*GraphNode, 0),
		visited:  false,
	}
}

func BFS(startNode *GraphNode) {
	var queue []*GraphNode           // 待访问的节点队列
	queue = append(queue, startNode) // 将初始节点加入队列
	startNode.visited = true         // 将初始节点设置为已访问

	for len(queue) > 0 {
		node := queue[0] // 出队一个节点，作为当前节点
		queue = queue[1:]
		fmt.Println("当前节点:", node.value)
		for _, graphNode := range node.adjacent {
			// (未访问过的)将相邻节点设置为已访问并加入队列
			if !graphNode.visited {
				graphNode.visited = true
				queue = append(queue, graphNode)
			}
		}
	}
}

func main() {
	// 创建图节点
	node1 := NewGraphNode(1)
	node2 := NewGraphNode(2)
	node3 := NewGraphNode(3)
	node4 := NewGraphNode(4)
	node5 := NewGraphNode(5)

	// 构建图的邻接关系
	node1.adjacent = append(node1.adjacent, node2, node3)
	node2.adjacent = append(node2.adjacent, node1, node4, node5)
	node3.adjacent = append(node3.adjacent, node1)
	node4.adjacent = append(node4.adjacent, node2)
	node5.adjacent = append(node5.adjacent, node2)

	// 从节点1开始进行BFS
	BFS(node1)
}