数据结构
网络
关系型数据库管理系统 (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+ 浏览量
