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的顺序访问各个节点。不同的邻接表表示方式可能会导致不同的遍历顺序。

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的顺序访问各个节点。不同的邻接表表示方式可能会导致不同的遍历顺序。

打赏

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,您说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在