在Golang程序中查找图形中的所有路径

在本文中，我们将学习如何在 Golang 中使用深度优先搜索算法和广度优先搜索方法查找图形中的所有路径。在图中，节点由实体表示，边表示这些实体之间的关系。在图论中查找所有路径是一项常见任务，可以在各种应用程序中发挥作用。

算法

步骤1 − 首先，我们需要导入 fmt 包。
步骤2 − 然后创建不同的结构和函数，并对它们定义属性。
步骤3 − 现在，创建 main () 函数。在 main() 中初始化节点并为其分配值。
步骤4 − 进一步，通过将它们作为图形结构的参数传递来创建从这些节点的边缘。
步骤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("所需的路径为：", paths)
}