Golang 实现深度优先搜索的程序

在本文中，我们将学习如何使用Golang的内部函数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函数初始化一个visited映射，该函数是Go语言的内置函数。
步骤5 - 从DFS调用DFSUtil方法，包括两个输入：起始顶点和初始化的映射。
步骤6 - 在以下函数中，递归访问顶点，并在访问后将访问的顶点设置为true，并使用fmt包中的Println将其打印到控制台，其中ln表示换行。
步骤7 - 在主函数中，通过将顶点值传递给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

在迭代中使用邻接矩阵表示法

在这种方法中，我们将编写一个Golang程序，使用邻接矩阵表示法来实现深度优先搜索。这里的DFS方法和DFSUtil方法将用于执行深度优先搜索。

步骤

第1步 －在程序中导入fmt和main包，其中fmt帮助格式化输入和输出，而main确保程序是可执行的程序
第2步 －创建一个Graph结构体，使用邻接矩阵表示法，并且顶点的类型为int
第3步 －创建一个AddEdge方法，参数为源顶点和目标顶点。在这个方法中，将从源顶点到目标顶点添加边，以创建一个图
第4步 －在这一步中，创建一个DFS方法，参数为起始顶点。在这个函数中，创建一个visited映射，如果某个顶点被访问过，则将其设置为true
第5步 －然后，调用DFSUtil方法，参数为顶点和visited映射
第6步 －递归访问图的每个顶点，打印它，并在访问完顶点后将visited设置为true
第7步 －在主函数中，AddEdge方法提供顶点的输入参数，这些顶点将连接以获取图形

示例

以下示例展示了使用邻接矩阵表示法迭代实现深度优先搜索的golang程序。

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 − 迭代节点的edges并检查边是否被访问。
步骤9 − 如果边未被访问，则递归调用DFS函数，并将边作为参数。
步骤10 − 在主函数中，设置节点值并连接节点创建边。
步骤11 − 使用节点1作为参数调用DFS函数。
步骤12 − 使用fmt包的Printf函数执行打印语句。

示例

下面的示例演示了如何创建一个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)
}