边集数组
📌 定义
边集数组直接存储所有的边，每条边用一个结构体或元组表示。
图: 边集数组:
0---1 [(0, 1, 5),
|\ /| (0, 2, 3),
| X | (1, 2, 2),
|/ \| (1, 3, 6),
2---3 (2, 3, 4)]
核心思路
- 边的表示：(起点, 终点, 权重)
- 无向图：每条边可存储一次或两次
- 排序友好：便于按权重排序
- 适用场景：并查集、最小生成树
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 初始化 | O(E) | O(E) |
| 查询边 | O(E) | - |
| 添加边 | O(1) | - |
| 排序边 | O(E log E) | - |
Go 代码
Go 实现
type Edge struct {
U, V, Weight int
}
type GraphEdges struct {
n int
directed bool
edges []Edge
}
func NewGraphEdges(n int, directed bool) *GraphEdges {
return &GraphEdges{
n: n,
directed: directed,
edges: []Edge{},
}
}
func (g *GraphEdges) AddEdge(u, v, weight int) {
g.edges = append(g.edges, Edge{U: u, V: v, Weight: weight})
if !g.directed {
g.edges = append(g.edges, Edge{U: v, V: u, Weight: weight})
}
}
func (g *GraphEdges) SortEdges() {
sort.Slice(g.edges, func(i, j int) bool {
return g.edges[i].Weight < g.edges[j].Weight
})
}
func (g *GraphEdges) GetEdges() []Edge {
return g.edges
}💡 优缺点
优点
- ✅ 空间效率高：O(E)
- ✅ 便于按权重排序
- ✅ 适合 Kruskal 算法
- ✅ 适合并查集
缺点
- ❌ 查询边慢：O(E)
- ❌ 查找邻接点慢：O(E)
- ❌ 不适合遍历
🎯 应用场景
边集数组主要用于：
- Kruskal 算法：按权重排序边
- 并查集：处理连通性
- 边的批处理：需要对所有边进行操作