用c语言写一个图的遍历

在C语言中，我们可以使用邻接矩阵或邻接表来表示图，并采用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历它。这里以邻接矩阵为例，展示一个简单的DFS实现：

#include <stdio.h>
#include <stdbool.h>

#define V 5 // 图的顶点数
bool graph[V][V]; // 用布尔值表示邻接关系

// 深度优先搜索函数
void dfs(int vertex) {
    bool visited[V] = {false}; // 初始化已访问数组
    printf("Visiting %d\n", vertex);
    visited[vertex] = true; // 标记该节点已访问

    // 递归遍历相邻未访问节点
    for (int i = 0; i < V; i++)
        if (graph[vertex][i] && !visited[i])
            dfs(i);
}

int main() {
    // 初始化邻接矩阵
    // 例如：graph[0][1] = 1 表示从0到1有边
    graph[0][1] = graph[1][0] = 1; // 建立一个环形图

    // 开始遍历
    dfs(0); // 从0节点开始

    return 0;
}

对于广度优先搜索，可以使用队列来代替递归，以下是BFS的简单版本：

#include <stdio.h>
#include <stdlib.h>

void bfs(int source) {
    int queue[V], front = -1, rear = -1; // 使用双端队列
    bool visited[V] = {false};

    queue[++rear] = source; // 将起始节点入队
    visited[source] = true;

    while (front != rear) {
        int u = queue[++front]; // 取出队首节点
        printf("Visiting %d\n", u);

        // 遍历相邻节点，若未访问则入队
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !visited[v]) {
                queue[++rear] = v;
                visited[v] = true;
            }
        }
    }
}

int main() {
    // 初始化邻接矩阵...
    bfs(0); // 从0节点开始

    return 0;
}