邻接矩阵
📌 定义
邻接矩阵使用二维数组表示图，其中 matrix[i][j] 表示从顶点 i 到顶点 j 的边。
图: 邻接矩阵:
0---1 0 1 2 3
|\ /| 0[0, 1, 1, 0]
| X | 1[1, 0, 1, 1]
|/ \| 2[1, 1, 0, 1]
2---3 3[0, 1, 1, 0]
核心思路
- 无向图：
matrix[i][j] = matrix[j][i] - 有向图：
matrix[i][j]表示 i→j 的边 - 有权图：存储权重值
- 无权图：存储 0/1
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 初始化 | O(V²) | O(V²) |
| 查询边 | O(1) | - |
| 添加边 | O(1) | - |
| 删除边 | O(1) | - |
| 遍历邻接点 | O(V) | - |
Go 代码
Go 实现
type GraphMatrix struct {
n int
directed bool
matrix [][]int
}
func NewGraphMatrix(n int, directed bool) *GraphMatrix {
matrix := make([][]int, n)
for i := range matrix {
matrix[i] = make([]int, n)
}
return &GraphMatrix{n: n, directed: directed, matrix: matrix}
}
func (g *GraphMatrix) AddEdge(u, v, weight int) {
g.matrix[u][v] = weight
if !g.directed {
g.matrix[v][u] = weight
}
}
func (g *GraphMatrix) HasEdge(u, v int) bool {
return g.matrix[u][v] != 0
}
func (g *GraphMatrix) GetNeighbors(u int) []int {
neighbors := []int{}
for v := 0; v < g.n; v++ {
if g.matrix[u][v] != 0 {
neighbors = append(neighbors, v)
}
}
return neighbors
}💡 优缺点
优点
- ✅ 查询边的存在性：O(1)
- ✅ 适合稠密图
- ✅ 实现简单直观
缺点
- ❌ 空间复杂度高：O(V²)
- ❌ 遍历邻接点慢：O(V)
- ❌ 不适合稀疏图