go語言編程學習實現圖的廣度與深度優先搜索

Posted on by

圖的實現

所謂圖就是節點及其連接關系的集合。所以可以通過一個一維數組表示節點，外加一個二維數組表示節點之間的關系。

//圖的矩陣實現
typedef struct MGRAPH{
    nodes int[];    //節點
    edges int[][];  //邊
}mGraph;

在這裡插入圖片描述

然而對於一些實際問題，其鄰接矩陣中可能存在大量的0值，此時可以通過鄰接鏈表來表示稀疏圖，其數據結構如圖所示

在這裡插入圖片描述

其左側為圖的示意圖，右側為圖的鄰接鏈表。紅字表示節點序號，鏈表中為與這個節點相連的節點，如1節點與2、5節點相連。由於在go中，可以很方便地使用數組來代替鏈表，所以其鏈表結構可以寫為

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

其中，map為Go語言中的鍵值索引類型，其定義格式為map[<op1>]<op2>，<op1>為鍵，<op2>為值。在圖結構中，map[Node][]*Node表示一個Node對應一個Node指針所組成的數組。

下面將通過Go語言生成一個圖

//增加節點
//可以理解為Graph的成員函數
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

廣度優先搜索(BFS)是最簡單的圖搜索算法，給定圖的源節點後，向外部進行試探性地搜索。其特點是，通過與源節點的間隔來調控進度，即隻有當距離源節點為 k k k的節點被搜索之後，才會繼續搜索，得到距離源節點為 k + 1 k+1 k+1的節點。

對於圖的搜索而言，可能存在重復的問題，即如果1搜索到2，相應地2又搜索到1，可能就會出現死循環。因此對於圖中的節點，我們用searched對其進行標記，當其值為false時，說明沒有被搜索過，否則則說明已經搜索過瞭。

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

此外，由於在搜索過程中會改變節點的屬性，所以map所對應哈希值也會發生變化，即Node作為鍵值將無法對應原有的鄰接節點，所以Graph中邊的鍵值更替為節點的指針，這樣即便節點的值發生變化，但其指針不會變化。

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		//存儲待搜索節點
	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

深度優先遍歷(DFS)與BFS的區別在於，後者的搜索過程可以理解為逐層的，即可將我們初始搜索的節點看成父節點，那麼與該節點相連接的便是一代節點，搜索完一代節點再搜索二代節點。DFS則是從父節點搜索開始，一直搜索到末代節點，從而得到一個末代節點的一條世系；然後再對所有節點進行遍歷，找到另一條世系，直至不存在未搜索過的節點。

其基本步驟為：

  • 首先選定一個未被訪問過的頂點 V 0 V_0 V0​作為初始頂點，並將其標記為已訪問
  • 然後搜索 V 0 V_0 V0​鄰接的所有頂點，判斷是否被訪問過，如果有未被訪問的頂點，則任選一個頂點 V 1 V_1 V1​進行訪問，依次類推，直到 V n V_n Vn​不存在未被訪問過的節點為止。
  • 若此時圖中仍舊有頂點未被訪問，則再選取其中一個頂點進行訪問，否則遍歷結束。

我們先實現第二步，即單個節點的最深搜索結果

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->

即

在這裡插入圖片描述

可見，還有節點7、9未被訪問。

完整的DFS算法隻需在單點遍歷之前，加上一個對所有節點的遍歷即可

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語言編程學習實現圖的廣度與深度優先搜索的詳細內容，更多關於go語言實現圖的廣度與深度優先搜索的資料請關註WalkonNet其它相關文章！

推薦閱讀：