Go语言图的邻接表表示（从零开始掌握图的数据结构）

Go语言中如何实现邻接表？

在 Go 中，我们可以用 map[int][]int 或 []*[]int 来实现邻接表。下面是一个简单、清晰的实现方式。

1. 定义图结构

type Graph struct {    adjList map[int][]int}

2. 初始化图

func NewGraph() *Graph {    return &Graph{        adjList: make(map[int][]int),    }}

3. 添加边（无向图）

func (g *Graph) AddEdge(v, w int) {    // 确保顶点存在    if g.adjList[v] == nil {        g.adjList[v] = []int{}    }    if g.adjList[w] == nil {        g.adjList[w] = []int{}    }    // 无向图：双向添加    g.adjList[v] = append(g.adjList[v], w)    g.adjList[w] = append(g.adjList[w], v)}

4. 打印邻接表

func (g *Graph) Print() {    for vertex, neighbors := range g.adjList {        fmt.Printf("%d: %v\n", vertex, neighbors)    }}

5. 完整示例

package mainimport "fmt"type Graph struct {    adjList map[int][]int}func NewGraph() *Graph {    return &Graph{        adjList: make(map[int][]int),    }}func (g *Graph) AddEdge(v, w int) {    if g.adjList[v] == nil {        g.adjList[v] = []int{}    }    if g.adjList[w] == nil {        g.adjList[w] = []int{}    }    g.adjList[v] = append(g.adjList[v], w)    g.adjList[w] = append(g.adjList[w], v)}func (g *Graph) Print() {    for vertex, neighbors := range g.adjList {        fmt.Printf("%d: %v\n", vertex, neighbors)    }}func main() {    g := NewGraph()    g.AddEdge(0, 1)    g.AddEdge(0, 2)    g.AddEdge(1, 2)    g.AddEdge(2, 3)    fmt.Println("邻接表表示：")    g.Print()}

运行结果：

邻接表表示：0: [1 2]1: [0 2]2: [0 1 3]3: [2]

为什么选择邻接表？

对于大多数真实世界的图（如社交网络、网页链接），它们通常是稀疏图（边的数量远小于顶点数的平方）。使用Go语言图的邻接表表示法能显著减少内存占用，并提高遍历效率。

扩展思考

- 如果是有向图，只需在 AddEdge 中单向添加即可。
- 可以用 struct 存储带权重的边，例如 []Edge，其中 Edge{to: int, weight: int}。
- 在实际项目中，可结合 Go数据结构 的其他特性（如并发安全、接口抽象）进行封装。

总结

通过本文，你已经掌握了在 Go 语言中使用邻接表表示图的基本方法。这是学习图的表示方法和后续图算法（如 DFS、BFS、Dijkstra）的重要基础。希望你能动手实践，加深理解！

关键词回顾：Go语言图的邻接表、Go数据结构、图的表示方法、邻接表实现。