图的邻接矩阵表示（Go语言实现图数据结构的入门指南）

Go语言实现邻接矩阵

下面我们用 Go 语言一步步实现一个无向图的邻接矩阵表示。

1. 定义图结构

type Graph struct {    vertices int           // 顶点数量    matrix   [][]int      // 邻接矩阵}

2. 创建新图

func NewGraph(vertices int) *Graph {    // 初始化一个 vertices × vertices 的二维切片    matrix := make([][]int, vertices)    for i := range matrix {        matrix[i] = make([]int, vertices)    }    return &Graph{        vertices: vertices,        matrix:   matrix,    }}

3. 添加边

// AddEdge 添加一条无向边func (g *Graph) AddEdge(v1, v2 int) {    if v1 < g.vertices && v2 < g.vertices {        g.matrix[v1][v2] = 1        g.matrix[v2][v1] = 1 // 无向图：对称    }}

4. 打印邻接矩阵

func (g *Graph) PrintMatrix() {    for i := 0; i < g.vertices; i++ {        for j := 0; j < g.vertices; j++ {            fmt.Printf("%d ", g.matrix[i][j])        }        fmt.Println()    }}

5. 完整示例

package mainimport "fmt"type Graph struct {    vertices int    matrix   [][]int}func NewGraph(vertices int) *Graph {    matrix := make([][]int, vertices)    for i := range matrix {        matrix[i] = make([]int, vertices)    }    return &Graph{vertices: vertices, matrix: matrix}}func (g *Graph) AddEdge(v1, v2 int) {    if v1 < g.vertices && v2 < g.vertices {        g.matrix[v1][v2] = 1        g.matrix[v2][v1] = 1    }}func (g *Graph) PrintMatrix() {    for i := 0; i < g.vertices; i++ {        for j := 0; j < g.vertices; j++ {            fmt.Printf("%d ", g.matrix[i][j])        }        fmt.Println()    }}func main() {    g := NewGraph(4) // 创建包含4个顶点的图    g.AddEdge(0, 1)    g.AddEdge(0, 2)    g.AddEdge(1, 2)    g.AddEdge(2, 3)    fmt.Println("邻接矩阵表示：")    g.PrintMatrix()}

运行上述代码，输出如下：

邻接矩阵表示：0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0

邻接矩阵的优缺点

优点：

• 查询两个顶点是否相连的时间复杂度为 O(1)
• 实现简单直观

缺点：

• 空间复杂度高：O(V²)，即使图很稀疏（边很少）也会浪费大量空间
• 添加/删除顶点成本高，需要重建整个矩阵

总结

通过本教程，我们学习了如何在 Go语言 中使用 邻接矩阵 来表示图。这是理解 图数据结构Go实现 的重要一步。虽然邻接矩阵在稀疏图中效率不高，但它在稠密图或需要频繁判断边是否存在时非常有用。

如果你正在学习 Go语言数据结构教程，建议你也尝试实现 邻接表 表示法，它在大多数实际应用中更节省空间。

希望这篇关于 Go语言图的邻接矩阵 的教程对你有所帮助！动手写一写代码，你会理解得更深刻。