首页 / 算法 / 用golang实现广度优先搜索算法
用golang实现广度优先搜索算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了用golang实现广度优先搜索算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4337字，纯文字阅读大概需要7分钟。
内容图文
广度优先搜索算法（Breadth First Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，广度优先搜索算法是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。借助广度优先搜索算法，可以让你找出两样东西之间的最短距离。
迷宫文件maze.in 文件
6 5
0 1 0 0 0
0 0 0 1 0
0 1 0 1 0
1 1 1 0 0
0 1 0 0 1
0 1 0 0 0我来解释一下这个迷宫maze.in文件
1是墙壁，不可以走，0是未探索的点
现在是要通过走0一直走到终点，起始坐标是（0,0）终点坐标是（5,4）
我们需要走到每一个点，然后探索周围的点是不是一堵墙，也就是1，如果不是，就要在探索的点中+1
左图为迷宫图，右图为最终执行结果
上代码
maze.go 文件，这里的i是行（竖的），j是列（横的）
package main
import (
"fmt"
"os"
)
func readMaze(filename string) [][] int {
file, err := os.Open(filename)// 打开这个文件
if err != nil {
panic(err)
}
var row, col int// 定义行和列,
// row 是行 竖下去的那种是行
fmt.Fscanf(file, "%d %d", &row, &col)// 设置row,col，首先要知道几行几列， 值是 6 和 5，因为文件第一行写好了
//fmt.Println(row, col)// 6, 5
maze := make([][]int, row)
//fmt.Println(maze)// // [[],[],[],[],[],[],[]]
for i := range maze {// 循环第一个slice
maze[i] = make([]int, col)
for j := range maze[i] {// 循环第一个slice里面的小slice ，也就是说要做横向遍历
// maze.in中的行和列弄到file这个变量中
// 第一行（竖）第一列（横）是0 所以是0
// 第二行是0，第二列是0 所以是0
// 第三行是0，第三列是0 所以是0
// 第四行是1，第四列是1 所以是1
// ...
fmt.Fscanf(file, "%d", &maze[i][j])// maze.in 中以列的形式放到变量中（横向遍历）
}
}
return maze
}
type point struct {
i, j int // 行，列（横）
}
// 执行到这些坐标，说明不可继续往下走
// maze at next is 0
// and steps at next is 0
// and next != start 走过了
var dirs = [4]point{
{-1, 0},// 开始的上边
{0, -1},// 开始的左边
{1, 0},// 开始的第二步
{0, 1},// 墙壁
}
func (p point) add(r point) point {
return point{p.i + r.i, p.j + r.j}
}
func (p point) at(grid [][]int) (int, bool) {
if p.i < 0 || p.i >= len(grid) {// 行 p.i < 0 说明越界了 p.i >= len(grid) 说明撞墙了，遇到了1，要等于0才能走
return 0, false
}
if p.j < 0 || p.j >= len(grid[p.i]) {// 列（横） p.j < 0 说明越界了 p.j >= len(grid[p.i]) 说明撞墙了，遇到了1，要等于0才能走
return 0, false
}
//fmt.Println("grid", grid)
return grid[p.i][p.j], true// 第一个值当前走的值，第二个是是否越界了
}
// maze 内容, start 开始;end 结束的行和列
func walk(maze [][]int, start, end point) [][]int {
steps := make([][]int, len(maze))
for i := range steps {
steps[i] = make([]int, len(maze[i]))
}
Q := []point{start}
// fmt.Println("这里是Q队列", Q)
for len(Q) > 0 {
cur := Q[0]
Q = Q[1:]
if cur == end {// 开始==结束
break
}
//fmt.Println(cur)
//{0 0}
//{1 0}
//{2 0}
//{1 1}
//{1 2}
//{0 2}
//{2 2}
//{0 3}
//{0 4}
//{1 4}
//{2 4}
//{3 4}
//{3 3}
//{4 3}
//{4 2}
//{5 3}
//{5 2}
for _, dir := range dirs {
next := cur.add(dir)
//fmt.Println(next)
//{-1 0}
//{0 -1}
//{1 0}
//{0 1}
//{0 0}
//{1 -1}
//{2 0}
//{1 1}
//{1 0}
//{2 -1}
//{3 0}
//{2 1}
//{0 1}
//{1 0}
//{2 1}
//{1 2}
//{0 2}
//{1 1}
//{2 2}
//{1 3}
//{-1 2}
//{0 1}
//{1 2}
//{0 3}
//{1 2}
//{2 1}
//{3 2}
//{2 3}
//{-1 3}
//{0 2}
//{1 3}
//{0 4}
//{-1 4}
//{0 3}
//{1 4}
//{0 5}
//{0 4}
//{1 3}
//{2 4}
//{1 5}
//{1 4}
//{2 3}
//{3 4}
//{2 5}
//{2 4}
//{3 3}
//{4 4}
//{3 5}
//{2 3}
//{3 2}
//{4 3}
//{3 4}
//{3 3}
//{4 2}
//{5 3}
//{4 4}
//{3 2}
//{4 1}
//{5 2}
//{4 3}
//{4 3}
//{5 2}
//{6 3}
//{5 4}
//{4 2}
//{5 1}
//{6 2}
//{5 3}
// maze at next is 0
// and steps at next is 0
// and next != start 走过了
val, ok := next.at(maze)
if !ok || val == 1 {
continue
}
val, ok = next.at(steps)
if !ok || val != 0 {
continue
}
if next == start { // 回到原点了
continue
}
curSteps, _ := cur.at(steps)
steps[next.i][next.j] = curSteps + 1// 因为我们需要把当前的步数加1,也就是已经探索了的区域，行和列如果有的话加1
Q = append(Q, next)
}
}
return steps
}
func main() {
maze := readMaze("./maze.in")// 返回一个列（横） [[0 1 0 0 0] [0 0 0 1 0] [0 1 0 1 0] [1 1 1 0 0] [0 1 0 0 1] [0 1 0 0 0]]
fmt.Println("这个是终点，目标坐标", len(maze), len(maze[0]))
steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
for _, row := range steps {
for _, val := range row {
fmt.Printf("%3d", val)
}
fmt.Println()
}
}输出
E:\go\src\go_test\maze>go run maze.go
0 0 4 5 6
1 2 3 0 7
2 0 4 0 8
0 0 0 10 9
0 0 12 11 0
0 0 13 12 13
内容总结
以上是互联网集市为您收集整理的用golang实现广度优先搜索算法全部内容，希望文章能够帮你解决用golang实现广度优先搜索算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。