C语言数据结构与算法之图的遍历(一)

我来给您详细讲解一下“C语言数据结构与算法之图的遍历(一)”的完整攻略。

简介

本篇攻略主要介绍了图的遍历问题。图是由若干个点和连接这些点的边构成的数据结构，常用来表示复杂的关系和网络。图的遍历就是从图的某一点开始，按照一定的规则沿着边逐个访问图中所有的点，不重不漏地遍历整个图。

在本篇攻略中，我们将探讨图的深度优先遍历(DFS)和广度优先遍历(BFS)两种常见的遍历方法。

图的深度优先遍历(DFS)

深度优先遍历(DFS)是一种先纵向再横向遍历的算法。具体来说，它从图的某一起始点出发，依次访问该节点的第一个相邻节点，再依次访问该节点的相邻节点的第一个未被访问的相邻节点，依次类推，直至遍历完所有与其连通的节点。如果某一个节点有多个未被访问的相邻节点，那么就任意选择其中的一个继续访问，直到所有节点被遍历完为止。

下面是一个简单的例子：

#include <stdio.h>

#define MAX_N 10

int visited[MAX_N]; // 标记数组
int graph[MAX_N][MAX_N] = {  // 定义一个无向图
    {0, 1, 1, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 1, 1, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 1, 1, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
    {0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
    {0, 0, 1, 0, 0, 0, 0, 0, 1, 1},
    {0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 1, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0}
};

void DFS(int start, int n) {  // 深度优先遍历
    printf("%d ", start);
    visited[start] = 1;
    for (int i = 0; i < n; i++) {
        if (graph[start][i] == 1 && !visited[i]) {
            DFS(i, n);
        }
    }
}

int main() {
    int n = 10;
    for (int i = 0; i < n; i++) {
        visited[i] = 0; // 初始化标记数组
    }
    printf("DFS遍历结果：");
    DFS(0, n);
    printf("\n");
    return 0;
}

以上代码实现了一个由10个顶点组成的无向图的遍历，DFS算法的时间复杂度为$O(n+m)$，其中$n$和$m$分别表示图中的节点数和边数。

图的广度优先遍历(BFS)

广度优先遍历(BFS)是一种先横向再纵向遍历的算法。具体来说，它从图的某一起始点出发，先遍历其所有直接相邻的节点，依次访问它们的所有未被访问的相邻节点，直到全部遍历完为止。在遍历每一层节点时，BFS会按照从左到右的顺序进行访问，保证每一层节点的遍历顺序是相同的。

下面是一个简单的例子：

#include <stdio.h>

#define MAX_N 10

int visited[MAX_N]; // 标记数组
int graph[MAX_N][MAX_N] = {  // 定义一个无向图
    {0, 1, 1, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 1, 1, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 1, 1, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
    {0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
    {0, 0, 1, 0, 0, 0, 0, 0, 1, 1},
    {0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 1, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0}
};

void BFS(int start, int n) {  // 广度优先遍历
    int queue[MAX_N], front = 0, rear = 0;  // 定义一个队列
    queue[rear++] = start;  // 初始节点入队
    while (front < rear) {
        int cur = queue[front++];
        printf("%d ", cur);  // 打印节点值
        visited[cur] = 1;
        for (int i = 0; i < n; i++) {
            if (graph[cur][i] == 1 && !visited[i]) {
                queue[rear++] = i;  // 相邻节点入队
            }
        }
    }
}

int main() {
    int n = 10;
    for (int i = 0; i < n; i++) {
        visited[i] = 0; // 初始化标记数组
    }
    printf("BFS遍历结果：");
    BFS(0, n);
    printf("\n");
    return 0;
}

以上代码同样实现了一个由10个顶点组成的无向图的遍历，BFS算法的时间复杂度同样为$O(n+m)$。

总结

通过本篇攻略的学习，我们了解了深度优先遍历和广度优先遍历两种常见的图遍历算法。DFS算法按照一定的规律逐个遍历各个节点，遍历的顺序更倾向于纵向；BFS算法则是先遍历某一层所有节点，再遍历下一层所有节点，遍历的顺序更倾向于横向。在实际应用中，我们需要根据自己的需求选择合适的算法。

希望这篇攻略能对您有所帮助，谢谢！