邻接表

图 - 邻接表 (Adjacency List)

每个顶点维护一个链表（或动态数组），存储其所有邻居。空间 O(V + E)，适合稀疏图。

---

结构定义

typedef struct AdjNode {
    int vertex;           /* 目标顶点 */
    int weight;           /* 边权重（可选，无权图可省略） */
    struct AdjNode *next;
} AdjNode;
 
typedef struct {
    AdjNode **adj;        /* 邻接表数组 */
    int V;                /* 顶点数 */
    int directed;         /* 是否是有向图 */
} Graph;

---

函数签名

函数	复杂度	说明
Graph* graph_create(int V, int directed)	O(V)	创建图
void graph_add_edge(Graph *g, int u, int v, int w)	O(1)	添加边（头插法）
void graph_remove_edge(Graph *g, int u, int v)	O(deg(u))	移除边
int graph_has_edge(Graph *g, int u, int v)	O(deg(u))	边是否存在
void graph_bfs(Graph *g, int start, void (*visit)(int))	O(V + E)	广度优先
void graph_dfs(Graph *g, int start, void (*visit)(int))	O(V + E)	深度优先
void graph_free(Graph *g)	O(V + E)	释放

---

BFS 实现

void graph_bfs(Graph *g, int start, void (*visit)(int)) {
    int *visited = calloc(g->V, sizeof(int));
    int *queue = malloc(g->V * sizeof(int));
    int front = 0, rear = 0;
 
    visited[start] = 1;
    queue[rear++] = start;
 
    while (front < rear) {
        int u = queue[front++];
        visit(u);
        for (AdjNode *p = g->adj[u]; p; p = p->next) {
            if (!visited[p->vertex]) {
                visited[p->vertex] = 1;
                queue[rear++] = p->vertex;
            }
        }
    }
    free(visited);
    free(queue);
}

---

DFS 实现（递归）

static void dfs_util(Graph *g, int u, int *visited, void (*visit)(int)) {
    visited[u] = 1;
    visit(u);
    for (AdjNode *p = g->adj[u]; p; p = p->next)
        if (!visited[p->vertex])
            dfs_util(g, p->vertex, visited, visit);
}

---

邻接表 vs 邻接矩阵

特性	邻接表	邻接矩阵
空间	O(V + E)	O(V²)
查边 (u,v)	O(deg(u))	O(1)
遍历邻居	O(deg(u))	O(V)
适合场景	稀疏图	稠密图 / 边查询密集

---

跨语言参考

• C语言数据结构：图