数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Go语言程序查找图中所有路径
本文我们将学习如何使用Go语言中的深度优先搜索算法和广度优先搜索方法来查找图中的所有路径。在图中，节点由实体表示，边表示这些实体之间的关系。查找图中的所有路径是图论中的一个常见任务，可用于各种应用。
算法
步骤1 − 首先，我们需要导入fmt包。
步骤2 − 然后创建不同的结构体和函数，并为其定义属性。
步骤3 − 现在，创建main()函数。在main()函数内部初始化节点并为其赋值。
步骤4 − 接下来，通过将这些节点作为参数传递给graph结构体来创建边。
步骤5 − 现在，通过将所需的节点作为参数传递给AllPaths()函数来调用它，并将获得的结果存储在一个变量中。
步骤6 − 使用fmt.Println()函数在屏幕上打印结果。
示例1
在这个例子中，我们将编写一个Go语言程序，使用深度优先搜索来查找图中的所有路径。深度优先搜索(DFS)算法是用于遍历和搜索图的经典算法。
package main
import "fmt"
type Node struct {
name string
}
type Edge struct {
source *Node
dest *Node
}
type Graph struct {
nodes []*Node
edges []*Edge
}
func (g *Graph) AddNode(n *Node) {
g.nodes = append(g.nodes, n)
}
func (g *Graph) AddEdge(s *Node, d *Node) {
e := &Edge{source: s, dest: d}
g.edges = append(g.edges, e)
}
func (g *Graph) DFS(s *Node, d *Node, visited map[*Node]bool, path []string, paths *[][]string) {
visited[s] = true
path = append(path, s.name)
if s == d {
*paths = append(*paths, path)
} else {
for _, e := range g.edges {
if e.source == s && !visited[e.dest] {
g.DFS(e.dest, d, visited, path, paths)
}
}
}
delete(visited, s)
path = path[:len(path)-1]
}
func (g *Graph) AllPaths(s *Node, d *Node) [][]string {
visited := make(map[*Node]bool)
paths := [][]string{}
path := []string{}
g.DFS(s, d, visited, path, &paths)
return paths
}
func main() {
a := &Node{name: "A"}
b := &Node{name: "B"}
c := &Node{name: "C"}
d := &Node{name: "D"}
g := &Graph{}
g.AddNode(a)
g.AddNode(b)
g.AddNode(c)
g.AddNode(d)
g.AddEdge(a, b)
g.AddEdge(b, c)
g.AddEdge(a, c)
g.AddEdge(c, d)
paths := g.AllPaths(a, d)
fmt.Println("The required paths in a graph are:", paths)
}
输出
The required paths in a graph are: [[A B C D] [A C D]]
示例2
在这个例子中，我们将编写一个Go语言程序，使用广度优先搜索方法来查找图中的所有路径。
package main
import "fmt"
type Node struct {
name string
}
type Edge struct {
source *Node
dest *Node
}
type Graph struct {
nodes []*Node
edges []*Edge
}
func (g *Graph) AddNode(n *Node) {
g.nodes = append(g.nodes, n)
}
func (g *Graph) AddEdge(s *Node, d *Node) {
e := &Edge{source: s, dest: d}
g.edges = append(g.edges, e)
}
func (g *Graph) BFS(s *Node, d *Node) [][]string {
visited := make(map[*Node]bool)
queue := [][]*Node{{s}}
paths := [][]string{}
for len(queue) > 0 {
path := queue[0]
queue = queue[1:]
node := path[len(path)-1]
if node == d {
var pathStr []string
for _, n := range path {
pathStr = append(pathStr, n.name)
}
paths = append(paths, pathStr)
}
for _, e := range g.edges {
if e.source == node && !visited[e.dest] {
newPath := append(path, e.dest)
queue = append(queue, newPath)
visited[e.dest] = true
}
}
}
return paths
}
func main() {
a := &Node{name: "A"}
b := &Node{name: "B"}
c := &Node{name: "C"}
d := &Node{name: "D"}
g := &Graph{}
g.AddNode(a)
g.AddNode(b)
g.AddNode(c)
g.AddNode(d)
g.AddEdge(a, b)
g.AddEdge(b, c)
g.AddEdge(a, c)
g.AddEdge(c, d)
paths := g.BFS(a, d)
fmt.Println("The required paths are:", paths)
}
输出
The required paths are: [[A C D]]
结论
我们已经成功地编译并执行了一个Go语言程序来查找图中的所有路径，并附带了示例。这用于网络路由、社交网络分析和推荐系统等应用。我们展示了两种方法，即广度优先搜索和深度优先搜索来实现此结果。
更新于：2023年4月5日
664 次浏览
广告