資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用Go語言實現深度優先搜尋
在本文中，我們將學習如何使用Go語言的內建函式，如`make`、`append`和`range`，來實現深度優先搜尋。深度優先搜尋是一種用於圖和樹資料結構的遍歷演算法。它遞迴地探索圖的所有節點。
語法
func make ([] type, size, capacity)
Go語言中的`make`函式用於建立陣列/對映，它接受要建立的變數型別、大小和容量作為引數。
func append(slice, element_1, element_2…, element_N) []T
`append`函式用於向陣列切片新增值。它接受多個引數。第一個引數是要向其中新增值的陣列，後面跟著要新增的值。然後，該函式返回包含所有值的最終陣列切片。
func range(variable)
`range`函式用於迭代任何資料型別。要使用它，我們首先必須編寫`range`關鍵字，後跟要迭代到的資料型別，結果迴圈將迭代到變數的最後一個元素。
使用鄰接表表示
在這種方法中，我們將編寫一個Go語言程式，使用鄰接表表示法來表示圖，從而實現深度優先搜尋。`DFS`和`DFSUtil`函式將用於執行深度優先搜尋。
演算法
步驟1 − 在程式中匯入`fmt`和`main`包，其中`fmt`有助於輸入和輸出的格式化，`main`確保程式是一個可執行程式。
步驟2 − 建立一個`Graph`結構體，其頂點型別為`int`，並使用鄰接表表示法來表示圖。
步驟3 − 然後，建立一個`AddEdge`方法，其輸入為源和目標，並在其中新增從源到目標的邊。
步驟4 − 建立一個`DFS`方法，其輸入為`startVertex`。在函式中，使用`make`函式（Go語言中的內建函式）初始化一個`visited`對映。
步驟5 − 使用起始頂點和已初始化的對映作為兩個輸入，從`DFS`呼叫`DFSUtil`方法。
步驟6 − 在下面的函式中，遞迴地訪問頂點，並在訪問後將已訪問的頂點設定為`true`，並使用`fmt`包中的`Println`（`ln`表示換行）將其列印到控制檯。
步驟7 − 在`main`函式中，將頂點值傳遞給`AddEdge`函式，透過連線頂點形成邊來建立圖。
示例
以下示例演示了使用鄰接表表示法實現深度優先搜尋的Go語言程式。
package main
import "fmt"
type Graph struct {
vertices int
adjList map[int][]int
}
func NewGraph(vertices int) *Graph {
return &Graph{
vertices: vertices,
adjList: make(map[int][]int),
}
}
func (g *Graph) AddEdge(source, dest int) {
g.adjList[source] = append(g.adjList[source], dest)
g.adjList[dest] = append(g.adjList[dest], source)
}
func (g *Graph) DFSUtil(vertex int, visited map[int]bool) {
visited[vertex] = true
fmt.Printf("%d ", vertex)
for _, v := range g.adjList[vertex] {
if !visited[v] {
g.DFSUtil(v, visited)
}
}
}
func (g *Graph) DFS(startVertex int) {
visited := make(map[int]bool)
g.DFSUtil(startVertex, visited)
}
func main() {
g := NewGraph(5)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(1, 3)
g.AddEdge(1, 4)
fmt.Println("Depth-first traversal starting from vertex 0:")
g.DFS(0)
}
輸出
Depth-first traversal starting from vertex 0: 0 1 3 4 2
使用迭代的鄰接矩陣表示法
在這種方法中，我們將編寫一個Go語言程式，使用迭代的鄰接矩陣表示法來實現深度優先搜尋。這裡`DFS`和`DFSUtil`方法將用於執行深度優先搜尋。
演算法
步驟1 − 在程式中匯入`fmt`和`main`包，其中`fmt`有助於輸入和輸出的格式化，`main`確保程式是一個可執行程式。
步驟2 − 建立一個`Graph`結構體，其鄰接矩陣表示法和頂點型別為`int`。
步驟3 − 建立一個`AddEdge`方法，其引數為源和目標。在這個方法中，將新增從源到目標的邊來建立圖。
步驟4 − 在此步驟中，建立一個`DFS`方法，其輸入為`startvertex`。在這個函式中，建立一個`visited`對映，如果訪問了特定的頂點，則將其設定為`true`。
步驟5 − 然後，從此處呼叫`DFSUtil`方法，其引數為頂點和`visited`對映。
步驟6 − 遞迴地訪問圖的每個頂點，列印它，並在訪問頂點後將其`visited`設定為`true`。
步驟7 − 在`main`函式中，`AddEdge`方法提供了頂點的輸入引數，這些頂點將被連線以獲得圖。
示例
以下示例顯示了使用迭代的鄰接矩陣表示法實現深度優先搜尋的Go語言程式。
package main
import "fmt"
type Graph struct {
vertices int
adjMatrix [][]bool
}
func NewGraph(vertices int) *Graph {
matrix := make([][]bool, vertices)
for i := 0; i < vertices; i++ {
matrix[i] = make([]bool, vertices)
}
return &Graph{
vertices: vertices,
adjMatrix: matrix,
}
}
func (g *Graph) AddEdge(source, dest int) {
g.adjMatrix[source][dest] = true
g.adjMatrix[dest][source] = true
}
func (g *Graph) DFSUtil(vertex int, visited []bool) {
visited[vertex] = true
fmt.Printf("%d ", vertex)
for i := 0; i < g.vertices; i++ {
if g.adjMatrix[vertex][i] && !visited[i] {
g.DFSUtil(i, visited)
}
}
}
func (g *Graph) DFS(startVertex int) {
visited := make([]bool, g.vertices)
g.DFSUtil(startVertex, visited)
}
func main() {
g := NewGraph(5)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(1, 3)
g.AddEdge(1, 4)
fmt.Println("Depth-first traversal starting from vertex 0:")
g.DFS(0)
}
輸出
Depth-first traversal starting from vertex 0: 0 1 3 4 2
使用遞迴
在這種方法中，我們將編寫一個Go語言程式，使用遞迴來實現深度優先搜尋。該函式將被呼叫，直到節點未被訪問。
演算法
步驟1 − 此程式匯入`main`和`fmt`包，其中`main`有助於生成可執行程式碼，`fmt`有助於輸入和輸出的格式化。
步驟2 − 建立一個`Node`結構體，它包含三個欄位：表示節點資料的`value`、表示節點是否已訪問的布林型別`visited`。
步驟3 − 最後一個是`edges`，它有助於新增邊。
步驟4 − 建立一個`DFS`函式，它以節點作為引數，該節點是根節點。
步驟5 − 檢查根節點是否為空，如果是，則返回。
步驟6 − 然後，將根節點的`visited`設定為`true`。
步驟7 − 在控制檯上列印節點值。
步驟8 − 迭代節點邊，並檢查邊是否已訪問。
步驟9 − 如果邊未被訪問，則使用邊作為引數遞迴呼叫`DFS`函式。
步驟10 − 在`main`函式中，設定節點值並連線節點以建立邊。
步驟11 − 使用`node1`作為引數呼叫`DFS`函式。
步驟12 − 使用`fmt`包中的`Printf`函式執行`Print`語句。
示例
以下示例說明了如何建立一個使用遞迴實現深度優先搜尋的Go語言程式。
package main
import "fmt"
type Node struct {
value int
visited bool
edges []*Node
}
func DFS(node *Node) {
if node == nil {
return
}
node.visited = true
fmt.Printf("%d ", node.value)
for _, edge := range node.edges {
if !edge.visited {
DFS(edge)
}
}
}
func main() {
node1 := &Node{value: 10}
node2 := &Node{value: 20}
node3 := &Node{value: 30}
node4 := &Node{value: 40}
node5 := &Node{value: 50}
node1.edges = []*Node{node2, node3}
node2.edges = []*Node{node4, node5}
node3.edges = []*Node{node5}
DFS(node1)
}
輸出
The DFS traversal is: 10 20 40 50 30
結論
我們編譯並執行了使用三個示例實現深度優先搜尋的程式。在第一個示例中使用了鄰接表表示法，在第二個示例中使用了鄰接矩陣表示法，在第三個示例中使用了遞迴。
3K+ 瀏覽量
