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

图的表示方法

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

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

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

深度优先搜索（DFS）

深度优先搜索（Depth-First Search, DFS）就像走迷宫：一条路走到黑，走不通就回退。它使用递归或栈来实现。

DFS 算法步骤：

1. 从起始顶点开始。
2. 访问该顶点，并标记为已访问。
3. 递归访问所有未访问的相邻顶点。

C语言实现 DFS：

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

广度优先搜索（BFS）

广度优先搜索（Breadth-First Search, BFS）像水波一样层层扩散。它使用队列来实现，先访问离起点最近的所有节点。

BFS 算法步骤：

1. 将起始顶点入队，并标记为已访问。
2. 当队列非空时，取出队首顶点并访问。
3. 将其所有未访问的邻居入队并标记。

C语言实现 BFS：

#include <stdio.h>#define MAX_VERTICES 100int graph[MAX_VERTICES][MAX_VERTICES];int 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++];}int isEmpty() {    return front == rear;}void bfs(int start) {    visited[start] = 1;    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] = 1;                enqueue(i);            }        }    }}int main() {    n = 5;    // 初始化邻接矩阵（同上）    for (int i = 0; i < n; i++)        for (int j = 0; j < n; j++)            graph[i][j] = 0;    graph[0][1] = graph[1][0] = 1;    graph[0][2] = graph[2][0] = 1;    graph[1][3] = graph[3][1] = 1;    graph[2][4] = graph[4][2] = 1;    for (int i = 0; i < n; i++)        visited[i] = 0;    printf("BFS 遍历结果: ");    bfs(0);    printf("\n");    return 0;}  

DFS 与 BFS 的区别

总结

通过本教程，你已经掌握了C语言图的遍历两大核心算法：深度优先搜索和广度优先搜索。无论你是准备面试还是学习图算法教程，这两种方法都是必须掌握的基础技能。建议你动手敲一遍代码，加深理解！

记住：编程不是看会的，而是练会的。加油！