go語言編程學習實現(xiàn)圖的廣度與深度優(yōu)先搜索
圖的實現(xiàn)
所謂圖就是節(jié)點及其連接關系的集合。所以可以通過一個一維數(shù)組表示節(jié)點，外加一個二維數(shù)組表示節(jié)點之間的關系。
//圖的矩陣實現(xiàn)
typedef struct MGRAPH{
nodes int[]; //節(jié)點
edges int[][]; //邊
}mGraph;
然而對于一些實際問題，其鄰接矩陣中可能存在大量的0值，此時可以通過鄰接鏈表來表示稀疏圖，其數(shù)據(jù)結構如圖所示
其左側為圖的示意圖，右側為圖的鄰接鏈表。紅字表示節(jié)點序號，鏈表中為與這個節(jié)點相連的節(jié)點，如1節(jié)點與2、5節(jié)點相連。由于在go中，可以很方便地使用數(shù)組來代替鏈表，所以其鏈表結構可以寫為
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>為值。在圖結構中，map[Node][]*Node表示一個Node對應一個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()
}
其運行結果為
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)控進度，即只有當距離源節(jié)點為 k k k的節(jié)點被搜索之后，才會繼續(xù)搜索，得到距離源節(jié)點為 k + 1 k+1 k+1的節(jié)點。
對于圖的搜索而言，可能存在重復的問題，即如果1搜索到2，相應地2又搜索到1，可能就會出現(xiàn)死循環(huán)。因此對于圖中的節(jié)點，我們用searched對其進行標記，當其值為false時，說明沒有被搜索過，否則則說明已經(jīng)搜索過了。
type Node struct{
value int;
searched bool;
}
/*func initGraph() Graph{
g := Graph{}
*/
//相應地更改節(jié)點生成函數(shù)
for i:=1;i<=5;i++{
g.AddNode(&Node{i,false})
}
/*
...
*/
此外，由于在搜索過程中會改變節(jié)點的屬性，所以map所對應哈希值也會發(fā)生變化，即Node作為鍵值將無法對應原有的鄰接節(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])
}
該圖為
輸出結果為
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結果 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é)點為止。
- 若此時圖中仍舊有頂點未被訪問，則再選取其中一個頂點進行訪問，否則遍歷結束。
我們先實現(xiàn)第二步，即單個節(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])
}
結果為
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])
}
結果為
PS E:\Code> go run .\goGraph.go 1->2->3->4->5->6->8-> 7-> 9->
以上就是go語言編程學習實現(xiàn)圖的廣度與深度優(yōu)先搜索的詳細內(nèi)容，更多關于go語言實現(xiàn)圖的廣度與深度優(yōu)先搜索的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要為大家詳細介紹了如何使用golang開發(fā)一個簡單的curl命令行工具,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2023-11-11
golang復用http.request.body的方法示例
這篇文章主要給大家介紹了關于golang復用http.request.body的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2018-10-10
學習?golang?，對于?interface{}?接口類型，我們一定繞不過，這篇文章咱們就來一起來看看?使用?interface{}?的時候，都有哪些注意事項吧2023-03-03
go語言實現(xiàn)字符串與其它類型轉換(strconv包)
strconv包是Go語言標準庫的一部分,主要提供字符串與基本數(shù)據(jù)類型之間的轉換功能,使用strconv包可以方便地在不同類型之間進行轉換,滿足日常編程中的需求,感興趣的可以了解一下2024-10-10
并發(fā)性和并行性是是兩個既有聯(lián)系又有所區(qū)別的概念,本文主要介紹了Go并發(fā)與并行,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-05-05
詳解Go操作supervisor xml rpc接口及注意事項
這篇文章主要介紹了Go操作supervisor xml rpc接口及注意事項,管理web，在配置文件中配置相關信息，通過go-supervisor的處理庫進行操作，需要的朋友可以參考下2021-09-09
本文主要介紹了golang Iris運行多個應用的實現(xiàn),在Iris里面,提供了一種方式可以讓我們同時運行多個應用,具有一定的參考價值,感興趣的可以了解一下2024-01-01
這篇文章主要給大家介紹了關于Golang中對json的優(yōu)雅處理方式,解析JSON在golang中很麻煩,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-06-06
Golang因Channel未關閉導致內(nèi)存泄漏的解決方案詳解
這篇文章主要為大家詳細介紹了當Golang因Channel未關閉導致內(nèi)存泄漏時蓋如何解決，文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下2023-07-07
Golang中數(shù)據(jù)結構Queue的實現(xiàn)方法詳解
這篇文章主要給大家介紹了關于Golang中數(shù)據(jù)結構Queue的實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧。2017-09-09