本文是《Go语言100个实战案例》系列中的一篇，聚焦图的邻接表表示法，结合Go语言进行数据结构与算法的实践。适合初学者以及有一定基础的开发者学习图结构在实际工程中的应用。
一、什么是图的邻接表表示？在图（Graph）的表示方法中，邻接表（Adjacency List）是一种常用的结构。它适用于稀疏图，即边数远少于点数平方的图。邻接表使用链表或切片来保存每个顶点的相邻顶点，相较邻接矩阵节省大量空间。
邻接表的核心思想：
- • 每个顶点对应一个链表（或切片），存储与该顶点相邻的边（即相邻的顶点）。
- • 可以用于有向图和无向图。
我们使用 Go 的map 和 slice数据结构实现邻接表。下面是一个基础结构：
packagemainimport"fmt"// Graph 表示图结构（使用邻接表）typeGraphstruct{ verticesmap[string][]stringisDirectedbool}// NewGraph 构造函数funcNewGraph(isDirectedbool) *Graph {return&Graph{ vertices:make(map[string][]string), isDirected: isDirected, }}// AddVertex 添加顶点func(g *Graph) AddVertex(vstring) {if_, exists := g.vertices[v]; !exists { g.vertices[v] = []string{} }}// AddEdge 添加边func(g *Graph) AddEdge(from, tostring) { g.AddVertex(from) g.AddVertex(to) g.vertices[from] =append(g.vertices[from], to)if!g.isDirected { g.vertices[to] =append(g.vertices[to], from) }}// PrintGraph 输出邻接表func(g *Graph) PrintGraph {forvertex, neighbors :=rangeg.vertices { fmt.Printf("%s -> %v\n", vertex, neighbors) }}
三、使用示例：构建一个简单的无向图
funcmain { graph := NewGraph(false)// false 表示无向图graph.AddEdge("A","B") graph.AddEdge("A","C") graph.AddEdge("B","D") graph.AddEdge("C","D") graph.AddEdge("D","E") graph.PrintGraph}输出：A -> [B C]B -> [A D]C -> [A D]D -> [B C E]E -> [D]
四、支持有向图
我们只需要在构造图的时候传入 true，表示是有向图：
graph := NewGraph(true)// 有向图graph.AddEdge("A","B")graph.AddEdge("A","C")graph.PrintGraph输出：A -> [B C]B -> []C -> []
五、扩展思路
为了适用于更多实际场景，我们可以拓展该邻接表：
- • 支持权重：将 []string 改为 []Edge，其中 Edge 结构体包含 To 和 Weight 字段。
- • 实现图遍历：如 BFS、DFS 算法。
- • 实现图算法：如 Dijkstra 最短路径、拓扑排序、最小生成树等。
- • 可视化：输出 Graphviz DOT 格式可视化图结构。
邻接表是图结构中非常高效且实用的一种表示方式，尤其适用于稀疏图。在Go语言中，我们可以利用 map 和 slice 快速构建邻接表，为实现更复杂的图算法打下基础。
