Go语言实现广度优先搜索（Breadth-First Search，BFS）算法

Go语言实现广度优先搜索（Breadth-First Search，BFS）算法

下面是用 Go 语言实现广度优先搜索（Breadth-First Search，BFS）算法的代码示例。此示例假设我们在一个无向图中搜索，从一个起始节点开始遍历图的所有节点。

package main

import (
	"fmt"
)

// Graph 表示一个图，其中键是节点，值是相邻节点的切片
type Graph map[string][]string

// BFS 实现广度优先搜索算法
func BFS(graph Graph, start string) {
	// 创建一个队列，用来存储将要访问的节点
	queue := []string{start}
	
	// 创建一个集合，用来存储已访问的节点
	visited := make(map[string]bool)
	visited[start] = true
	
	for len(queue) > 0 {
		// 从队列中取出第一个节点
		node := queue[0]
		queue = queue[1:]
		
		// 访问当前节点
		fmt.Println(node)
		
		// 将当前节点的所有未访问过的邻居节点加入队列
		for _, neighbor := range graph[node] {
			if !visited[neighbor] {
				queue = append(queue, neighbor)
				visited[neighbor] = true
			}
		}
	}
}

func main() {
	// 定义一个图
	graph := Graph{
		"A": {"B", "C"},
		"B": {"A", "D", "E"},
		"C": {"A", "F"},
		"D": {"B"},
		"E": {"B", "F"},
		"F": {"C", "E"},
	}

	// 从节点 "A" 开始进行广度优先搜索
	BFS(graph, "A")
}

代码说明

1. Graph 类型定义：使用 map[string][]string 定义一个图的数据结构，其中键是节点，值是相邻节点的切片。
2. BFS 函数：实现广度优先搜索算法。
   • 初始化一个队列，将起始节点加入队列。
   • 初始化一个已访问节点的集合，将起始节点标记为已访问。
   • 循环处理队列中的节点，直到队列为空。
   • 对于每个节点，打印该节点并将其未访问过的邻居节点加入队列，并标记为已访问。
3. main 函数：定义一个图并调用 BFS 函数，从节点 "A" 开始进行广度优先搜索。

这个实现假设图是无向且连通的。如果图是有向或不连通的，则需要对相应的数据结构和逻辑进行调整。