图论入门：从存储结构到DFS/BFS遍历，零基础也能看懂的实战教程 接上文
// 步骤1 创建1指向v2的边节点（用头插法，效率高）
EdgeNode *e1 = (EdgeNode *)malloc(sizeof(EdgeNode)); // 申请内存
e1->adjvex = v2; // 邻接点是v2
e1->weight = weight; // 边权
e1->next = graph->adjlist[v1].firstedge; // 新节点指向原链表头
graph->adjlist[v1].firstedge = e1; // 链表头更新为新节点
// 步骤2：创建v2指向v1的边节点（无向图双向，重复步骤1）
EdgeNode *e2 = (EdgeNode *)malloc(sizeof(EdgeNode));
e2->adjvex = v1;
e2->weight = weight;
e2->next = graph->adjlist[v2].firstedge;
graph->adjlist[v2].firstedge = e2;
graph->edge_num++; // 边数量+1
}
// 6. 打印邻接表
void printAdjList(AdjListGraph *graph) {
printf("邻接表（格式：顶点 -> 邻接点(边权) -> ... -> NULL）：\n");
for (int i = 0; i < graph->vertex_num; i++) {
printf("%c -> ", graph->adjlist[i].data);
EdgeNode *p = graph->adjlist[i].firstedge; // 遍历边链表
while (p != NULL) {
// 打印邻接点和边权
printf("%c(%d) -> ", graph->adjlist[p->adjvex].data, p->weight);
p = p->next; // 指向下一个边节点
}
printf("NULL\n");
}
}
// 主函数：测试邻接表
int main() {
AdjListGraph graph;
// 1. 初始化5个顶点的图
initAdjList(&graph, 5);
// 2. 添加和邻接矩阵相同的边（便于对比）
addEdgeList(&graph, 0, 1, 2);
addEdgeList(&graph, 0, 2, 3);
addEdgeList(&graph, 1, 3, 1);
addEdgeList(&graph, 2, 4, 4)；
// 3. 打印结果
printAdjList(&graph);
return 0;
}
3.3 编译运行与结果
和邻接矩阵步骤一致：
1. 编译： gcc adjacency_list.c -o adjacency_list ；
2. 运行： ./adjacency_list.exe ；
3. 结果：终端输出“顶点→邻接点(边权)”的链表结构，与前文示例一致，说明代码成功。
四、图的核心遍历算法：DFS与BFS（附代码）
存储图的最终目的是“遍历”——即从某个顶点出发，访问所有可达的顶点。DFS和BFS是两种最基础、最常用的遍历算法，以下基于邻接表实现（邻接矩阵版代码见文末附录）。
4.1 深度优先遍历（DFS）：递归实现，像“走迷宫”
核心逻辑
DFS的思路是“一条路走到黑”：
1. 访问当前顶点，标记为“已访问”；
2. 找到当前顶点的一个未访问邻接点，递归访问这个邻接点；
3. 若没有未访问邻接点，回溯到上一个顶点，重复步骤2；
4. 直到所有可达顶点都被访问。
完整代码（添加到adjacency_list.c中）
// 深度优先遍历（start：起始顶点索引，visited：访问标记数组）
void DFS(AdjListGraph *graph, int start, bool visited[]) {
// 1. 访问当前顶点，标记为已访问
printf("%c ", graph->adjlist[start].data);
visited[start] = true;
// 2. 遍历当前顶点的所有邻接点
EdgeNode *p = graph->adjlist[start].firstedge;
while (p != NULL) {
// 若邻接点未访问，递归遍历
if (!visited[p->adjvex]) {
DFS(graph, p->adjvex, visited);
}
p = p->next; // 继续遍历下一个邻接点
}
}
// 在main函数中添加测试代码
int main() {
// （前面的初始化、加边、打印代码不变）
// 测试DFS
bool visited_dfs[MAX_VERTICES] = {false}; // 访问标记数组（初始全未访问）
printf("\n深度优先遍历（DFS）结果：");
DFS(&graph, 0, visited_dfs); // 从顶点0开始遍历
printf("\n");
return 0;
}
4.2 广度优先遍历（BFS）：队列实现，像“水波扩散”
核心逻辑
BFS的思路是“逐层扩散”：
1. 访问起始顶点，标记为“已访问”，加入队列；
2. 出队一个顶点，访问该顶点的所有未访问邻接点，标记后加入队列；
3. 重复步骤2，直到队列为空；
4. 队列保证了“先访问的顶点，其邻接点也先被访问”（层次顺序）。
完整代码（添加到adjacency_list.c中）
// BFS依赖的队列结构体（先进先出）
typedef struct {
int data[MAX_VERTICES]; // 存储顶点索引
int front, rear; // 队头、队尾指针
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = q->rear = 0; // 队空标识：front == rear
}
// 入队（队列未满时，添加元素到队尾）
bool enQueue(Queue *q, int val) {
// 循环队列：队满条件是 (rear+1)%MAX_VERTICES == front
if ((q->rear + 1) % MAX_VERTICES == q->front) {
printf("队列满，入队失败！\n");
return false;
}
q->data[q->rear] = val;
q->rear = (q->rear + 1) % MAX_VERTICES; // 队尾后移
return true;
}
// 出队（队列非空时，取出队头元素）
bool deQueue(Queue *q, int *val) {
if (q->front == q->rear) { // 队空
printf("队列空，出队失败！\n");
return false;
}
*val = q->data[q->front];
q->front = (q->front + 1) % MAX_VERTICES; // 队头后移
return true;
}
// 广度优先遍历（start：起始顶点索引）
void BFS(AdjListGraph *graph, int start, bool visited[]) {
Queue q;
initQueue(&q);
// 1. 访问起始顶点，标记入队
printf("%c ", graph->adjlist[start].data);
visited[start] = true;
enQueue(&q, start);
// 2. 队列非空时，循环出队、访问邻接点
while (q.front != q.rear) {
int current;
deQueue(&q, ¤t); // 出队当前顶点
// 遍历当前顶点的所有邻接点
EdgeNode *p = graph->adjlist[current].firstedge;
while (p != NULL) {
if (!visited[p->adjvex]) {
printf("%c ", graph->adjlist[p->adjvex].data); // 访问邻接点
visited[p->adjvex] = true; // 标记已访问
enQueue(&q, p->adjvex); // 邻接点入队
}
p = p->next;
}
}
}
// 在main函数中添加测试代码
int main() {
// （前面的初始化、加边、打印、DFS代码不变）
// 测试BFS
bool visited_bfs[MAX_VERTICES] = {false};
printf("\n广度优先遍历（BFS）结果：");
BFS(&graph, 0, visited_bfs); // 从顶点0开始遍历
printf("\n");
return 0;
}
4.3 最终运行结果
结果符合预期：DFS是“0→2→4→1→3”（一条路走到黑），BFS是“0→2→1→4→3”（逐层扩散）。
4.4 邻接矩阵版DFS/BFS代码
邻接矩阵的遍历逻辑与邻接表类似，只是“遍历邻接点”的方式从“链表遍历”改为“数组遍历”，完整代码可参考：邻接矩阵DFS/BFS实现（示例链接，可自行替换）。
总结
本文从“存储结构→遍历算法”层层递进，核心是“动手实践”：
1. 先理解邻接矩阵和邻接表的差异——稠密图用矩阵，稀疏图用表；
2. 再掌握DFS和BFS的逻辑——DFS靠递归回溯，BFS靠队列层次；
3. 最后多敲代码、多改参数（比如增减顶点和边），感受图论的灵活应用。
后续可以学习图的进阶算法，比如最短路径（Dijkstra）、最小生成树（Prim），这些算法都基于本文的存储结构和遍历逻辑，打好基础就能轻松上手。