邻接表
📌 定义
邻接表使用链表数组表示图，每个顶点对应一个链表，存储其所有邻接点。
图: 邻接表:
0---1 0 → [1, 2]
|\ /| 1 → [0, 2, 3]
| X | 2 → [0, 1, 3]
|/ \| 3 → [1, 2]
2---3
核心思路
- 无向图：每条边存储两次
- 有向图：只存储出边
- 有权图：存储 (邻接点, 权重) 对
- 空间效率：只存储存在的边
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 初始化 | O(V) | O(V+E) |
| 查询边 | O(degree) | - |
| 添加边 | O(1) | - |
| 删除边 | O(degree) | - |
| 遍历邻接点 | O(degree) | - |
Go 代码
Go 实现
type Edge struct {
To int
Weight int
}
type GraphList struct {
n int
directed bool
graph [][]Edge
}
func NewGraphList(n int, directed bool) *GraphList {
graph := make([][]Edge, n)
for i := range graph {
graph[i] = []Edge{}
}
return &GraphList{n: n, directed: directed, graph: graph}
}
func (g *GraphList) AddEdge(u, v, weight int) {
g.graph[u] = append(g.graph[u], Edge{To: v, Weight: weight})
if !g.directed {
g.graph[v] = append(g.graph[v], Edge{To: u, Weight: weight})
}
}
func (g *GraphList) GetNeighbors(u int) []int {
neighbors := []int{}
for _, edge := range g.graph[u] {
neighbors = append(neighbors, edge.To)
}
return neighbors
}
func (g *GraphList) GetEdges(u int) []Edge {
return g.graph[u]
}💡 优缺点
优点
- ✅ 空间效率高：O(V+E)
- ✅ 适合稀疏图
- ✅ 遍历邻接点快：O(degree)
缺点
- ❌ 查询边存在性慢：O(degree)
- ❌ 删除边较慢
🎯 应用场景
邻接表是最常用的图表示方法，适用于：
- 稀疏图（边数远小于 V²）
- 需要频繁遍历邻接点
- DFS/BFS遍历
- 最短路径算法