GO实现深度优先搜索（Depth-First Search，DFS）算法

GO实现深度优先搜索（Depth-First Search，DFS）算法

以下是用Go语言实现的深度优先搜索（Depth-First Search，DFS）算法示例：

package main

import (
	"fmt"
)

// Graph 表示图的结构
type Graph struct {
	adjList map[string][]string
}

// NewGraph 创建一个新的图
func NewGraph() *Graph {
	return &Graph{
		adjList: make(map[string][]string),
	}
}

// AddEdge 向图中添加边
func (g *Graph) AddEdge(v, w string) {
	g.adjList[v] = append(g.adjList[v], w)
}

// DFSUtil 递归辅助函数，用于执行实际的DFS
func (g *Graph) DFSUtil(v string, visited map[string]bool) {
	// 将当前节点标记为已访问
	visited[v] = true
	fmt.Print(v, " ")

	// 递归访问所有未访问的邻接节点
	for _, neighbor := range g.adjList[v] {
		if !visited[neighbor] {
			g.DFSUtil(neighbor, visited)
		}
	}
}

// DFS 深度优先搜索的主函数
func (g *Graph) DFS(start string) {
	visited := make(map[string]bool) // 用于跟踪已访问的节点
	g.DFSUtil(start, visited)
}

func main() {
	g := NewGraph()
	g.AddEdge("A", "B")
	g.AddEdge("A", "C")
	g.AddEdge("B", "D")
	g.AddEdge("B", "E")
	g.AddEdge("C", "F")
	g.AddEdge("E", "F")

	fmt.Print("从节点 A 开始的深度优先搜索遍历结果: ")
	g.DFS("A")
}

代码解释：

1. type Graph struct：

   • 使用一个邻接表来表示图，其中adjList是一个map，键是节点，值是与该节点相邻的节点列表。

2. func NewGraph() *Graph：

   • 创建一个新的图实例，并初始化adjList。

3. func (g *Graph) AddEdge(v, w string)：

   • 向图中添加从节点v到节点w的边。

4. func (g *Graph) DFSUtil(v string, visited map[string]bool)：

   • 递归辅助函数，用于执行实际的DFS。
   • 将当前节点v标记为已访问并打印。
   • 递归访问所有未访问的邻接节点。

5. func (g *Graph) DFS(start string)：

   • DFS的主函数，初始化一个map来跟踪已访问的节点，并调用DFSUtil。

6. func main()：

   • 创建一个图并添加边。
   • 从节点A开始执行DFS，并打印遍历结果。

运行结果：

该代码将打印从节点A开始的DFS遍历顺序。例如，对于上述示例图，输出可能为：

从节点 A 开始的深度优先搜索遍历结果: A B D E F C

这个输出表示从节点A开始，按照DFS的顺序访问各个节点。不同的邻接表表示方式可能会导致不同的遍历顺序。