图 - 邻接矩阵 (Adjacency Matrix)
用 V×V 二维矩阵表示边。矩阵[i][j] 存储边权重（或 0/1 表示有无边）。空间 O(V²)，适合稠密图。
结构定义
typedef struct {
int **mat; /* V×V 矩阵，mat[u][v] = 权重，0 表示无边 */
int V;
int directed;
} GraphM;函数签名
| 函数 | 复杂度 | 说明 |
|---|---|---|
GraphM* graphm_create(int V, int directed) | O(V²) | 创建并初始化全 0 矩阵 |
void graphm_add_edge(GraphM *g, int u, int v, int w) | O(1) | 设置 mat[u][v] = w |
void graphm_remove_edge(GraphM *g, int u, int v) | O(1) | 设置 mat[u][v] = 0 |
int graphm_has_edge(GraphM *g, int u, int v) | O(1) | 检查 mat[u][v] != 0 |
void graphm_bfs(GraphM *g, int start, void (*visit)(int)) | O(V²) | 广度优先（遍历整行找邻居） |
void graphm_dfs(GraphM *g, int start, void (*visit)(int)) | O(V²) | 深度优先 |
void graphm_free(GraphM *g) | O(V) | 释放 |
创建
GraphM* graphm_create(int V, int directed) {
GraphM *g = malloc(sizeof(GraphM));
g->V = V;
g->directed = directed;
g->mat = malloc(V * sizeof(int *));
for (int i = 0; i < V; i++)
g->mat[i] = calloc(V, sizeof(int));
return g;
}加边
void graphm_add_edge(GraphM *g, int u, int v, int w) {
g->mat[u][v] = w;
if (!g->directed)
g->mat[v][u] = w; /* 无向图对称设置 */
}遍历邻居
/* 遍历顶点 u 的所有邻居 */
for (int v = 0; v < g->V; v++) {
if (g->mat[u][v] != 0) {
/* v 是 u 的邻居，权重为 mat[u][v] */
}
}邻接矩阵遍历邻居始终是 O(V)，即使实际邻居很少——这是稀疏图上的主要劣势。
优势场景
| 场景 | 适合原因 |
|---|---|
| 稠密图 (E ≈ V²) | 空间利用率高 |
| Floyd-Warshall 全源最短路径 | 需要 O(1) 查边长 |
| 快速查询”u 到 v 是否有边” | O(1) vs 邻接表的 O(deg) |
| 矩阵乘法 (图的代数性质) | 邻接矩阵的 n 次幂表示 n 步可达关系 |