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);}