用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关键字，后接我们想要遍历的数据类型，结果循环将迭代到变量的最后一个元素。

使用邻接表表示法

在这种方法中，我们将编写一个Golang程序，使用邻接表表示法来表示图并执行深度优先搜索。函数DFS和DFSUtil将用于执行深度优先搜索。

算法

步骤1 − 在程序中导入fmt和main包，其中fmt帮助格式化输入和输出，而main确保程序应为可执行程序。
步骤2 − 创建一个Graph结构，其中顶点的类型为int，邻接表表示将用于表示该图。
步骤3 − 然后，创建一个AddEdge方法，其中源和目标作为输入，在其中从源到目标添加边。
步骤4 − 创建一个方法DFS，startVertex作为输入。在该函数中，使用make函数初始化visited map，该函数是Golang中的内置函数。
步骤5 − 从DFS中调用方法DFSUtil，其中包括两个输入：起始顶点和初始化的映射。
步骤6 − 在以下函数中，递归访问顶点，一旦访问，将其设置为已访问的顶点，并使用来自fmt包的Println将其打印到控制台上，其中ln表示换行。
步骤7 − 在main中，通过将顶点值传递给AddEdge函数，将顶点连接起来以形成边，从而创建图。

示例

下面的示例演示了使用邻接表表示法实现深度优先搜索的Golang程序。

包 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("从顶点0开始的深度优先遍历：")
   g.DFS(0)
}

输出

从顶点0开始的深度优先遍历：
0 1 3 4 2

使用邻接矩阵表示进行迭代

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

算法

第一步 − 在程序中导入fmt和main程序包，其中fmt会帮助格式化输入和输出，而main则确保程序应该是可执行程序。
第二步 − 创建一个Graph结构体来存储邻接矩阵表示，其中vertices的类型为int。
第三步 − 创建一个AddEdge方法，将源和目的地作为参数传递进来。在此方法中，将从源到目的地添加边缘以创建图形。
第四步 − 在这一步中，创建一个带startvertex输入的DFS方法。在此函数中，创建一个visited map，如果访问了特定顶点，则将其设置为true。
第五步 − 然后，从这里调用带顶点和visited map作为参数的DFSUtil方法。
第六步 − 递归地访问图形的每个顶点，打印它并在顶点被访问后将visited设置为true。
第七步 − 在main中，提供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("从顶点0开始的深度优先遍历：")
   g.DFS(0)
}

输出

从顶点0开始的深度优先遍历：
0 1 3 4 2

使用递归

在此方法中，我们将编写一个 Golang 程序，使用递归实现深度优先搜索。该函数将在节点未访问时被调用。

算法

步骤 1 − 该程序导入主要包和 fmt 包。其中主要帮助生成可执行代码，并 fmt 帮助格式化输入和输出
步骤 2 − 创建一个 Node 结构，具有三个字段：值（表示节点数据），类型为 bool 的 visited（确定节点是否已访问）
步骤 3 − 最后一个是透过 edges 添加边
步骤 4 − 创建一个函数 DFS，其将节点作为参数，即根节点
步骤 5 − 检查根节点是否为空，如果为空，则返回
步骤 6 − 然后，将根节点的访问设置为 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)
}