Golang 实现图数据结构的程序

在Go编程语言中，图是一种由有限数量的节点（也称为顶点）和一组连通边构成的数据结构。图可以用于表示多个实体之间的关系。可以使用不同的数据结构来表示图，例如邻接矩阵或邻接表。使用哪种数据结构取决于具体的用例和应用程序的需求。可以使用类似go-graph的库或软件包在Go中实现图。我们将在这里使用两种方法来实现图数据结构。

方法1：使用邻接矩阵

在这个实现中，图被显示为Graph结构中的AdMatrix字段。值N表示图中节点的数量，确定了矩阵的大小。矩阵中的true值表示图的边。

步骤

• 步骤1 - 在程序中创建一个package main并声明fmt（格式化包）包，其中main生成可执行代码，fmt用于格式化输入和输出。

• 步骤2 - 定义一个Graph结构，其中包含AdMatrix字段，将图存储为二维矩阵。

• 步骤3 - 创建一个Graph结构的实例，来表示图。

• 步骤4 - 通过将AdMatrix中的一个单元格的值设置为true，可以连接图节点，这在图中表示两个节点之间的边。

• 步骤5 - 对于图中的每条边，再次执行步骤3。

• 步骤6 - 通过迭代遍历AdMatrix并打印值，创建图。

• 步骤7 - 使用邻接矩阵，此技术可以创建出具有基本功能的网络表示。还可以扩展功能，如添加和删除节点或边，确定两个节点之间的最短路径等。

示例

在下面的示例中，我们将使用邻接矩阵来在Go编程语言中实现图数据结构。

package main
import (
   "fmt"
)

const n = 4

// Graph represents a graph using an adjacency matrix
type Graph struct {
   AdMatrix [n][n]bool
}

func main() {
   // Create graph
   graph := Graph{}

   // Connect nodes
   graph.AdMatrix[0][1] = true
   graph.AdMatrix[0][2] = true
   graph.AdMatrix[1][2] = true

   // Print graph
   fmt.Println("The graph is printed as follows using adjacency matrix:")
   fmt.Println("Adjacency Matrix:")
   for i := 0; i < n; i++ {
      for j := 0; j < n; j++ {
         fmt.Printf("%t ", graph.AdMatrix[i][j])
      }
      fmt.Println()
   }
}

输出

The graph is printed as follows using adjacency matrix:
Adjacency Matrix:
false true true false 
false false true false 
false false false false 
false false false false

方法2：使用Node Struct

在这个示例中，我们将使用节点结构来实现图数据结构。最终结果会在控制台上打印出一个图。让我们通过代码和算法来理解这个概念。

语法

func append(slice, element_1, element_2…, element_N) []T

append函数用于向数组切片中添加值。它接受多个参数。第一个参数是我们希望向其添加值的数组，其后是要添加的值。该函数然后返回包含所有值的最终数组切片。

步骤

• 步骤1 - 创建一个名为main的包并在程序中声明fmt（格式化包）。main包生成可执行代码，fmt包用于格式化输入和输出。

• 步骤2 - 为了表示图中的一个节点，创建一个名为Node的结构体，该结构体有两个字段：一个value字段用于保存节点的值，一个edges字段用于保存一个指向附近节点的指针切片。

• 步骤3 - 为了向节点添加新的边，创建Node结构体的Add_Edge方法。

• 步骤4 - 在下一步中，为了表示图中的节点，创建Node结构体的实例。

• 步骤5 - 使用Add_Edge函数在节点之间添加边。

• 步骤6 - 通过迭代节点并打印它们所关联的节点的值，你可以展示图。

• 步骤7 - 实现中的每个节点在一个邻接表表示的图中存储其邻居节点的列表。Add_Edge方法将一个新节点添加到当前节点的edges切片中，形成两个节点之间的有向边。

• 步骤8 - 使用getNodeValues方法将节点指针切片转换为用于显示的节点值切片。

示例

在这个示例中，我们将使用node结构体来执行程序。

package main
import (
   "fmt"
)

// Node represents a node in the graph.
type Node struct {
   value int
   edges []*Node
}

// AddEdge adds a new edge to the node.
func (n *Node) Add_Edge(node *Node) {
   n.edges = append(n.edges, node)
}

func main() {
   // Create nodes.
   n1 := &Node{value: 10}
   n2 := &Node{value: 20}
   n3 := &Node{value: 30}
   n4 := &Node{value: 40}
   n5 := &Node{value: 50}

   // Add edges.
   n1.Add_Edge(n2)
   n1.Add_Edge(n3)
   n2.Add_Edge(n4)
   n2.Add_Edge(n5)
   n3.Add_Edge(n5)

   // Display the graph.
   fmt.Println("The Graph is represented as:")
   fmt.Printf("Node %d -> %v\n", n1.value, getNodeValues(n1.edges))
   fmt.Printf("Node %d -> %v\n", n2.value, getNodeValues(n2.edges))
   fmt.Printf("Node %d -> %v\n", n3.value, getNodeValues(n3.edges))
   fmt.Printf("Node %d -> %v\n", n4.value, getNodeValues(n4.edges))
   fmt.Printf("Node %d -> %v\n", n5.value, getNodeValues(n5.edges))
}

// returns a slice of node values.
func getNodeValues(nodes []*Node) []int {
   var values []int
   for _, node := range nodes {
      values = append(values, node.value)
   }
   return values
}

输出

The Graph is represented as:
Node 10 -> [20 30]
Node 20 -> [40 50]
Node 30 -> [50]
Node 40 -> []
Node 50 -> []

结论

我们执行了实现图数据结构的程序，使用了两个示例。在第一个示例中，我们使用邻接矩阵来实现图数据结构；在第二个示例中，我们使用节点结构。