演算法 in Golang：Breadth-first search
（BFS、廣度優先搜索）
最短路徑問題 Shortest-path problem
- 從 A 到 F 點有多條路徑
解決問題的演算法 Breadth-first Search（廣度優先搜索）
- 將問題建模為圖（Graph）
- 通過 Breadth-first Search 演算法來解決問題
圖（Graph）是什么？
圖是用來對不同事物間如何關聯進行建模的一種方式
圖是一種資料結構
Breadth-first Search（BFS）廣度優先搜索演算法
- 作用于圖（Graph）
- 能夠回答兩類問題：
- 是否能夠從節點 A 到節點 B？
- 從 A 到 B 的最短路徑是什么？
以社交網路為例
- 直接添加的朋友
- 朋友的朋友...
- 第一層沒找到再找第二層
資料結構 Queue
- 先進來的資料先處理（FIFO）先進先出原則
- 無法隨機的訪問 Queue 里面的元素
- 相關操作：
- enqueue：添加元素
- dequeue：移除元素
例子
找到名為 Tom 的朋友
- 把你所有的朋友都加到 Queue 里面
- 把 Queue 里面第一個人找出來
- 看他是不是 Tom
- 是 結束任務
- 否 把他所有的朋友加到 Queue 重復操作
創建專案
~/Code/go via ?? v1.20.3 via ?? base
? mcd breadth_first_search
Code/go/breadth_first_search via ?? v1.20.3 via ?? base
? go mod init breadth_first_search
go: creating new go.mod: module breadth_first_search
Code/go/breadth_first_search via ?? v1.20.3 via ?? base
? c
Code/go/breadth_first_search via ?? v1.20.3 via ?? base
?
main.go 代碼：
package main
import "fmt"
type GraphMap map[string][]string
func main() {
var graphMap GraphMap = make(GraphMap, 0)
graphMap["you"] = []string{"alice", "bob", "claire"}
graphMap["bob"] = []string{"anuj", "peggy"}
graphMap["alice"] = []string{"peggy"}
graphMap["claire"] = []string{"tom", "johnny"}
graphMap["anuj"] = []string{}
graphMap["peggy"] = []string{}
graphMap["tom"] = []string{}
graphMap["johnny"] = []string{}
search_queue := graphMap["you"]
for {
if len(search_queue) > 0 {
var person string
person, search_queue = search_queue[0], search_queue[1:]
if personIsTom(person) {
fmt.Printf("%s is already in the queue for you.\n", person)
break
} else {
search_queue = append(search_queue, graphMap[person]...)
}
} else {
fmt.Println("Not found in search queue")
break
}
}
}
func personIsTom(p string) bool {
return p == "tom"
}
運行
Code/go/breadth_first_search via ?? v1.20.3 via ?? base
? go run main.go
tom is already in the queue for you.
Code/go/breadth_first_search via ?? v1.20.3 via ?? base took 3.2s
?
本文來自博客園，作者：尋月隱君，轉載請注明原文鏈接：https://www.cnblogs.com/QiaoPengjun/p/17462128.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/554487.html
標籤：其他
下一篇：返回列表