go語言怎么實(shí)現(xiàn)圖的廣度與深度優(yōu)先搜索

本篇內(nèi)容介紹了“go語言怎么實(shí)現(xiàn)圖的廣度與深度優(yōu)先搜索”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

圖的實(shí)現(xiàn)

所謂圖就是節(jié)點(diǎn)及其連接關(guān)系的集合。所以可以通過一個(gè)一維數(shù)組表示節(jié)點(diǎn)，外加一個(gè)二維數(shù)組表示節(jié)點(diǎn)之間的關(guān)系。

//圖的矩陣實(shí)現(xiàn)
typedef struct MGRAPH{
    nodes int[];    //節(jié)點(diǎn)
    edges int[][];  //邊
}mGraph;

然而對于一些實(shí)際問題，其鄰接矩陣中可能存在大量的0值，此時(shí)可以通過鄰接鏈表來表示稀疏圖，其數(shù)據(jù)結(jié)構(gòu)如圖所示

其左側(cè)為圖的示意圖，右側(cè)為圖的鄰接鏈表。紅字表示節(jié)點(diǎn)序號(hào)，鏈表中為與這個(gè)節(jié)點(diǎn)相連的節(jié)點(diǎn)，如1節(jié)點(diǎn)與2、5節(jié)點(diǎn)相連。由于在go中，可以很方便地使用數(shù)組來代替鏈表，所以其鏈表結(jié)構(gòu)可以寫為

package main
import "fmt"
type Node struct{
	value int;      //節(jié)點(diǎn)為int型
};
type Graph struct{
	nodes []*Node
	edges map[Node][]*Node		//鄰接表示的無向圖
}

其中，map為Go語言中的鍵值索引類型，其定義格式為map[<op1>]<op2>，<op1>為鍵，<op2>為值。在圖結(jié)構(gòu)中，map[Node][]*Node表示一個(gè)Node對應(yīng)一個(gè)Node指針?biāo)M成的數(shù)組。

下面將通過Go語言生成一個(gè)圖

//增加節(jié)點(diǎn)
//可以理解為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()
}

其運(yùn)行結(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é)點(diǎn)后，向外部進(jìn)行試探性地搜索。其特點(diǎn)是，通過與源節(jié)點(diǎn)的間隔來調(diào)控進(jìn)度，即只有當(dāng)距離源節(jié)點(diǎn)為 k k k的節(jié)點(diǎn)被搜索之后，才會(huì)繼續(xù)搜索，得到距離源節(jié)點(diǎn)為 k + 1 k+1 k+1的節(jié)點(diǎn)。

對于圖的搜索而言，可能存在重復(fù)的問題，即如果1搜索到2，相應(yīng)地2又搜索到1，可能就會(huì)出現(xiàn)死循環(huán)。因此對于圖中的節(jié)點(diǎn)，我們用searched對其進(jìn)行標(biāo)記，當(dāng)其值為false時(shí)，說明沒有被搜索過，否則則說明已經(jīng)搜索過了。

type Node struct{
	value int;
	searched bool;
}
/*func initGraph() Graph{
    g := Graph{}
*/
    //相應(yīng)地更改節(jié)點(diǎn)生成函數(shù)
    for i:=1;i<=5;i++{
		g.AddNode(&Node{i,false})
	}
/*
...
*/

此外，由于在搜索過程中會(huì)改變節(jié)點(diǎn)的屬性，所以map所對應(yīng)哈希值也會(huì)發(fā)生變化，即Node作為鍵值將無法對應(yīng)原有的鄰接節(jié)點(diǎn)，所以Graph中邊的鍵值更替為節(jié)點(diǎn)的指針，這樣即便節(jié)點(diǎn)的值發(fā)生變化，但其指針不會(huì)變化。

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		//存儲(chǔ)待搜索節(jié)點(diǎn)
	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é)點(diǎn)看成父節(jié)點(diǎn)，那么與該節(jié)點(diǎn)相連接的便是一代節(jié)點(diǎn)，搜索完一代節(jié)點(diǎn)再搜索二代節(jié)點(diǎn)。DFS則是從父節(jié)點(diǎn)搜索開始，一直搜索到末代節(jié)點(diǎn)，從而得到一個(gè)末代節(jié)點(diǎn)的一條世系；然后再對所有節(jié)點(diǎn)進(jìn)行遍歷，找到另一條世系，直至不存在未搜索過的節(jié)點(diǎn)。

其基本步驟為：

• 首先選定一個(gè)未被訪問過的頂點(diǎn) V 0 V_0 V0作為初始頂點(diǎn)，并將其標(biāo)記為已訪問

• 然后搜索 V 0 V_0 V0鄰接的所有頂點(diǎn)，判斷是否被訪問過，如果有未被訪問的頂點(diǎn)，則任選一個(gè)頂點(diǎn) V 1 V_1 V1進(jìn)行訪問，依次類推，直到 V n V_n Vn不存在未被訪問過的節(jié)點(diǎn)為止。

• 若此時(shí)圖中仍舊有頂點(diǎn)未被訪問，則再選取其中一個(gè)頂點(diǎn)進(jìn)行訪問，否則遍歷結(jié)束。

我們先實(shí)現(xiàn)第二步，即單個(gè)節(jié)點(diǎ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])
}

結(jié)果為

PS E:\Code> go run .\goGraph.go
1->2->3->4->5->6->8->

即

可見，還有節(jié)點(diǎn)7、9未被訪問。

完整的DFS算法只需在單點(diǎn)遍歷之前，加上一個(gè)對所有節(jié)點(diǎn)的遍歷即可

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語言怎么實(shí)現(xiàn)圖的廣度與深度優(yōu)先搜索”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！