Golang程序 实现图的数据结构

在Go编程语言中，图是一种由数量有限的节点（也称为顶点）和一组连接边组成的数据结构。几个实体之间的关系可以在图上描绘出来。它可以通过采用不同的数据结构来表示，如相邻矩阵或相邻列表。特定的用例和应用程序的需求将决定所使用的数据结构。图也可以通过使用go-graph这样的库或包在Go中实现。在这里我们将使用两种方法来实现图的数据结构。

方法1：使用邻接矩阵

在这个实现中，图被显示为Graph结构中的AdMatrix字段。数值N代表图形中的节点数，它决定了矩阵的大小。矩阵的真值用来表示图形的边。

算法

• 第1步 – 在程序中创建一个包main并声明fmt(格式包)包，其中main产生可执行代码，fmt帮助格式化输入和输出。

• 第2步– 为了将图形存储为一个二维矩阵，定义一个带有AdMatrix字段的图形结构。

• 第 3步– 在下一步，为了表示图形，创建一个图形结构的实例。

• 第4步– 通过将AdMatrix中的单元格的值设置为 “真”，您可以连接图形节点。这就是图形中两个节点之间的边。

• 第 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结构

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

语法

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

append函数用于向一个数组片断添加值。它需要一些参数。第一个参数是我们希望添加的数组，后面是要添加的值。然后，该函数返回包含所有值的数组的最终片断。

算法

• 第1步 – 在程序中创建一个包main并声明fmt(format package)包，其中main产生可执行代码，fmt帮助格式化输入和输出。

• 第2步– 为了表示图中的一个节点，创建一个名为Node的结构，该结构有两个字段：一个值字段用来保存节点的值，一个边字段用来保存指向附近节点的片状指针。

• 第3步– 为了给节点添加一个新的边，为Node结构创建Add_Edge方法。

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

• 第5步– 要在节点之间添加边，使用Add_Edge函数。

• 第6步– 通过迭代节点并打印与之相关的节点的值，你可以显示图形。

• 第7步 – 实现中的每个节点都在图的邻接列表中存储了一个邻居的列表。Add_Edge方法将一个新的节点添加到当前节点的edges slice中，在两个节点之间形成一条有向边缘。

• 第8步 – 节点指针片被转化为节点值片，用getNodeValues方法显示。

例子

在这个例子中，我们将使用节点结构来执行程序。

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 -> []

结论

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