go語言編程學(xué)習(xí)實現(xiàn)圖的廣度與深度優(yōu)先搜索
圖的實現(xiàn)
所謂圖就是節(jié)點及其連接關(guān)系的集合。所以可以通過一個一維數(shù)組表示節(jié)點，外加一個二維數(shù)組表示節(jié)點之間的關(guān)系。
//圖的矩陣實現(xiàn)
typedef struct MGRAPH{
nodes int[]; //節(jié)點
edges int[][]; //邊
}mGraph;
然而對于一些實際問題，其鄰接矩陣中可能存在大量的0值，此時可以通過鄰接鏈表來表示稀疏圖，其數(shù)據(jù)結(jié)構(gòu)如圖所示
其左側(cè)為圖的示意圖，右側(cè)為圖的鄰接鏈表。紅字表示節(jié)點序號，鏈表中為與這個節(jié)點相連的節(jié)點，如1節(jié)點與2、5節(jié)點相連。由于在go中，可以很方便地使用數(shù)組來代替鏈表，所以其鏈表結(jié)構(gòu)可以寫為
package main
import "fmt"
type Node struct{
value int; //節(jié)點為int型
};
type Graph struct{
nodes []*Node
edges map[Node][]*Node //鄰接表示的無向圖
}
其中，map為Go語言中的鍵值索引類型，其定義格式為map[<op1>]<op2>，<op1>為鍵，<op2>為值。在圖結(jié)構(gòu)中，map[Node][]*Node表示一個Node對應(yīng)一個Node指針所組成的數(shù)組。
下面將通過Go語言生成一個圖
//增加節(jié)點
//可以理解為Graph的成員函數(shù)
func (g *Graph) AddNode(n *Node) {
g.nodes = append(g.nodes, n)
}
//增加邊
func (g *Graph) AddEdge(u, v *Node) {
g.edges[*u] = append(g.edges[*u],v) //u->v邊
g.edges[*v] = append(g.edges[*v],u) //u->v邊
}
//打印圖
func (g *Graph) Print(){
//range遍歷 g.nodes，返回索引和值
for _,iNode:=range g.nodes{
fmt.Printf("%v:",iNode.value)
for _,next:=range g.edges[*iNode]{
fmt.Printf("%v->",next.value)
}
fmt.Printf("\n")
}
}
func initGraph() Graph{
g := Graph{}
for i:=1;i<=5;i++{
g.AddNode(&Node{i,false})
}
//生成邊
A := [...]int{1,1,2,2,2,3,4}
B := [...]int{2,5,3,4,5,4,5}
g.edges = make(map[Node][]*Node)//初始化邊
for i:=0;i<7;i++{
g.AddEdge(g.nodes[A[i]-1], g.nodes[B[i]-1])
}
return g
}
func main(){
g := initGraph()
g.Print()
}
其運行結(jié)果為
PS E:\Code> go run .\goGraph.go 1:2->5-> 2:1->3->4->5-> 3:2->4-> 4:2->3->5-> 5:1->2->4->
BFS
廣度優(yōu)先搜索(BFS)是最簡單的圖搜索算法，給定圖的源節(jié)點后，向外部進行試探性地搜索。其特點是，通過與源節(jié)點的間隔來調(diào)控進度，即只有當(dāng)距離源節(jié)點為 k k k的節(jié)點被搜索之后，才會繼續(xù)搜索，得到距離源節(jié)點為 k + 1 k+1 k+1的節(jié)點。
對于圖的搜索而言，可能存在重復(fù)的問題，即如果1搜索到2，相應(yīng)地2又搜索到1，可能就會出現(xiàn)死循環(huán)。因此對于圖中的節(jié)點，我們用searched對其進行標記，當(dāng)其值為false時，說明沒有被搜索過，否則則說明已經(jīng)搜索過了。
type Node struct{
value int;
searched bool;
}
/*func initGraph() Graph{
g := Graph{}
*/
//相應(yīng)地更改節(jié)點生成函數(shù)
for i:=1;i<=5;i++{
g.AddNode(&Node{i,false})
}
/*
...
*/
此外，由于在搜索過程中會改變節(jié)點的屬性，所以map所對應(yīng)哈希值也會發(fā)生變化，即Node作為鍵值將無法對應(yīng)原有的鄰接節(jié)點，所以Graph中邊的鍵值更替為節(jié)點的指針，這樣即便節(jié)點的值發(fā)生變化，但其指針不會變化。
type Graph struct{
nodes []*Node
edges map[*Node][]*Node //鄰接表示的無向圖
}
//增加邊
func (g *Graph) AddEdge(u, v *Node) {
g.edges[u] = append(g.edges[u],v) //u->v邊
g.edges[v] = append(g.edges[v],u) //u->v邊
}
//打印圖
func (g *Graph) Print(){
//range遍歷 g.nodes，返回索引和值
for _,iNode:=range g.nodes{
fmt.Printf("%v:",iNode.value)
for _,next:=range g.edges[iNode]{
fmt.Printf("%v->",next.value)
}
fmt.Printf("\n")
}
}
func initGraph() Graph{
g := Graph{}
for i:=1;i<=9;i++{
g.AddNode(&Node{i,false})
}
//生成邊
A := [...]int{1,1,2,2,2,3,4,5,5,6,1}
B := [...]int{2,5,3,4,5,4,5,6,7,8,9}
g.edges = make(map[*Node][]*Node)//初始化邊
for i:=0;i<11;i++{
g.AddEdge(g.nodes[A[i]-1], g.nodes[B[i]-1])
}
return g
}
func (g *Graph) BFS(n *Node){
var adNodes[] *Node //存儲待搜索節(jié)點
n.searched = true
fmt.Printf("%d:",n.value)
for _,iNode:=range g.edges[n]{
if !iNode.searched {
adNodes = append(adNodes,iNode)
iNode.searched=true
fmt.Printf("%v ",iNode.value)
}
}
fmt.Printf("\n")
for _,iNode:=range adNodes{
g.BFS(iNode)
}
}
func main(){
g := initGraph()
g.Print()
g.BFS(g.nodes[0])
}
該圖為
輸出結(jié)果為
PS E:\Code\goStudy> go run .\goGraph.go 1:2->5->9-> 2:1->3->4->5-> 3:2->4-> 4:2->3->5-> 5:1->2->4->6->7-> 6:5->8-> 7:5-> 8:6-> 9:1-> //下面為BFS結(jié)果 1:2 5 9 2:3 4 3: 4: 5:6 7 6:8 8: 7: 9:
DFS
深度優(yōu)先遍歷(DFS)與BFS的區(qū)別在于，后者的搜索過程可以理解為逐層的，即可將我們初始搜索的節(jié)點看成父節(jié)點，那么與該節(jié)點相連接的便是一代節(jié)點，搜索完一代節(jié)點再搜索二代節(jié)點。DFS則是從父節(jié)點搜索開始，一直搜索到末代節(jié)點，從而得到一個末代節(jié)點的一條世系；然后再對所有節(jié)點進行遍歷，找到另一條世系，直至不存在未搜索過的節(jié)點。
其基本步驟為：
- 首先選定一個未被訪問過的頂點 V 0 V_0 V0作為初始頂點，并將其標記為已訪問
- 然后搜索 V 0 V_0 V0鄰接的所有頂點，判斷是否被訪問過，如果有未被訪問的頂點，則任選一個頂點 V 1 V_1 V1進行訪問，依次類推，直到 V n V_n Vn不存在未被訪問過的節(jié)點為止。
- 若此時圖中仍舊有頂點未被訪問，則再選取其中一個頂點進行訪問，否則遍歷結(jié)束。
我們先實現(xiàn)第二步，即單個節(jié)點的最深搜索結(jié)果
func (g *Graph) visitNode(n *Node){
for _,iNode:= range g.edges[n]{
if !iNode.searched{
iNode.searched = true
fmt.Printf("%v->",iNode.value)
g.visitNode(iNode)
return
}
}
}
func main(){
g := initGraph()
g.nodes[0].searched = true
fmt.Printf("%v->",g.nodes[0].value)
g.visitNode(g.nodes[0])
}
結(jié)果為
PS E:\Code> go run .\goGraph.go 1->2->3->4->5->6->8->
即
可見，還有節(jié)點7、9未被訪問。
完整的DFS算法只需在單點遍歷之前，加上一個對所有節(jié)點的遍歷即可
func (g *Graph) DFS(){
for _,iNode:=range g.nodes{
if !iNode.searched{
iNode.searched = true
fmt.Printf("%v->",iNode.value)
g.visitNode(iNode)
fmt.Printf("\n")
g.DFS()
}
}
}
func main(){
g := initGraph()
g.nodes[0].searched = true
fmt.Printf("%v->",g.nodes[0].value)
g.visitNode(g.nodes[0])
}
結(jié)果為
PS E:\Code> go run .\goGraph.go 1->2->3->4->5->6->8-> 7-> 9->
以上就是go語言編程學(xué)習(xí)實現(xiàn)圖的廣度與深度優(yōu)先搜索的詳細內(nèi)容，更多關(guān)于go語言實現(xiàn)圖的廣度與深度優(yōu)先搜索的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
詳解golang中的結(jié)構(gòu)體編解碼神器Mapstructure庫
mapstructure是GO字典(map[string]interface{})和Go結(jié)構(gòu)體之間轉(zhuǎn)換的編解碼工具,這篇文章主要為大家介紹一下Mapstructure庫的相關(guān)使用,希望對大家有所幫助2023-09-09
Go語言實現(xiàn)的排列組合問題實例(n個數(shù)中取m個)
這篇文章主要介紹了Go語言實現(xiàn)的排列組合問題,結(jié)合實例形式分析了Go語言實現(xiàn)排列組合數(shù)學(xué)運算的原理與具體操作技巧,需要的朋友可以參考下2017-02-02
這篇文章主要為大家介紹了golang之資源釋放/異常錯誤處理解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2024-01-01
Go 的運行時的當(dāng)前設(shè)計，假定程序員自己負責(zé)檢測何時終止一個 goroutine 以及何時終止該程序。有時候我們需要的是使程序阻塞在這一行，本文就來詳細的介紹一下，感興趣的可以了解一下2021-12-12
go 原生http web 服務(wù)跨域restful api的寫法介紹
這篇文章主要介紹了go 原生http web 服務(wù)跨域restful api的寫法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
本文主要介紹了Go語言使用buffer讀取文件的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
這篇文章主要為大家介紹了Go語言如何通過通信共享內(nèi)存實現(xiàn)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-11-11
這篇文章主要為大家介紹了Go?1.21中引入的新包maps和cmp功能作用詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-11-11
Go 語言的內(nèi)存分配機制是理解和優(yōu)化 Go 程序性能的關(guān)鍵,在 Go 中,內(nèi)存管理是自動進行的,這得益于 Go 的垃圾回收機制,了解內(nèi)存如何分配和回收,可以幫助我們寫出更高性能的代碼,本文將深入講解下 Go 內(nèi)存分配機制,需要的朋友可以參考下2023-12-12
Configor是一個支持?yaml、json、toml、shell?的配置文件工具,這篇文中主要為大家詳細介紹了Configor的具體使用,感興趣的小伙伴可以學(xué)習(xí)一下2023-08-08