C语言图的遍历算法详解（从零开始掌握深度优先与广度优先搜索）

什么是图？

图由顶点（Vertex）和边（Edge）组成。例如，社交网络中的人可以看作顶点，朋友关系就是边。图可以是有向的（如关注关系）或无向的（如好友关系）。

图的表示方法

在C语言中，图通常用两种方式表示：

• 邻接矩阵：用二维数组表示，适合稠密图。
• 邻接表：用链表数组表示，适合稀疏图。

为简化教学，本文使用邻接矩阵来实现遍历算法。

1. 深度优先搜索（DFS）

深度优先搜索（DFS）的思路类似于“一条路走到黑”：从一个起点出发，沿着一条路径尽可能深入，直到无法继续为止，然后回溯到上一个节点，尝试其他路径。

DFS通常使用递归或栈来实现。下面我们用递归方式实现：

#include <stdio.h>#include <stdbool.h>#define MAX_VERTICES 100int graph[MAX_VERTICES][MAX_VERTICES];bool visited[MAX_VERTICES];int n; // 顶点数量void dfs(int vertex) {    visited[vertex] = true;    printf("%d ", vertex);    for (int i = 0; i < n; i++) {        if (graph[vertex][i] == 1 && !visited[i]) {            dfs(i);        }    }}int main() {    // 示例：构建一个简单无向图    n = 5;    // 初始化图（邻接矩阵）    int edges[][2] = {{0,1}, {0,2}, {1,3}, {2,4}};    int num_edges = sizeof(edges)/sizeof(edges[0]);    for (int i = 0; i < num_edges; i++) {        int u = edges[i][0];        int v = edges[i][1];        graph[u][v] = 1;        graph[v][u] = 1; // 无向图    }    // 初始化访问数组    for (int i = 0; i < n; i++) {        visited[i] = false;    }    printf("DFS遍历结果: ");    dfs(0); // 从顶点0开始    printf("\n");    return 0;}  

2. 广度优先搜索（BFS）

广度优先搜索（BFS）则像“水波扩散”：从起点开始，先访问所有直接邻居，再访问邻居的邻居，依此类推。BFS通常使用队列实现。

#include <stdio.h>#include <stdbool.h>#define MAX_VERTICES 100int graph[MAX_VERTICES][MAX_VERTICES];bool visited[MAX_VERTICES];int queue[MAX_VERTICES];int front = 0, rear = 0;int n;void enqueue(int x) {    queue[rear++] = x;}int dequeue() {    return queue[front++];}bool isEmpty() {    return front == rear;}void bfs(int start) {    visited[start] = true;    enqueue(start);    while (!isEmpty()) {        int current = dequeue();        printf("%d ", current);        for (int i = 0; i < n; i++) {            if (graph[current][i] == 1 && !visited[i]) {                visited[i] = true;                enqueue(i);            }        }    }}int main() {    n = 5;    int edges[][2] = {{0,1}, {0,2}, {1,3}, {2,4}};    int num_edges = sizeof(edges)/sizeof(edges[0]);    for (int i = 0; i < num_edges; i++) {        int u = edges[i][0];        int v = edges[i][1];        graph[u][v] = 1;        graph[v][u] = 1;    }    for (int i = 0; i < n; i++) {        visited[i] = false;    }    printf("BFS遍历结果: ");    bfs(0);    printf("\n");    return 0;}  

DFS vs BFS：如何选择？

在实际应用中：

• 如果你要找是否存在路径，DFS更节省内存（但可能陷入很深的分支）。
• 如果你要找最短路径（在无权图中），BFS是首选。

总结

通过本教程，你已经掌握了C语言图的遍历两大核心算法：深度优先搜索（DFS）和广度优先搜索（BFS）。这两种图算法教程中的基础方法，是解决更复杂图问题（如拓扑排序、连通分量、最短路径等）的基石。

建议你动手敲一遍代码，修改图的结构，观察输出结果，加深理解。编程没有捷径，实践出真知！

希望这篇图算法教程对你有帮助。如果你觉得有用，欢迎分享给更多正在学习C语言的朋友！