写一个用C语言实现有向图的两种遍历

遍历有向图（Directed Graph）通常有两种方式，分别是深度优先遍历（Depth-first Search，DFS）和广度优先遍历（Breadth-first Search，BFS）。下面我来分别介绍一下这两种遍历方式的 C 语言实现。

假设我们的有向图中有 n 个节点，用邻接矩阵来存储图，邻接矩阵的大小为 n x n，其中矩阵元素 A[i][j] 表示从节点 i 到节点 j 是否有一条边。

首先是深度优先遍历（DFS）的实现。DFS 通常使用递归的方式实现。具体实现代码如下：

#define MAX_N 100

int visited[MAX_N];  // 标记节点是否被访问过

void dfs(int v, int n, int graph[MAX_N][MAX_N]) {
    visited[v] = 1;  // 标记当前节点为已访问
    printf("%d ", v);  // 输出当前节点编号
    for (int i = 0; i < n; i++) {
        if (graph[v][i] && !visited[i]) {  // 如果当前节点和节点 i 之间有一条边，并且节点 i 未被访问过
            dfs(i, n, graph);  // 递归访问节点 i
        }
    }
}

上面的代码中，dfs() 函数是实现 DFS 遍历的核心部分。它接受三个参数：当前节点编号 v、节点总数 n 和邻接矩阵 graph[MAX_N][MAX_N]。visited 数组用于标记节点是否被访问过。

接下来是广度优先遍历（BFS）的实现。BFS 通常使用队列的方式实现。具体实现代码如下：

#define MAX_N 100

int visited[MAX_N];  // 标记节点是否被访问过

void bfs(int s, int n, int graph[MAX_N][MAX_N]) {
    int queue[MAX_N];  // 创建一个队列
    int front = 0, rear = 0;
    visited[s] = 1;  // 标记起点为已访问
    printf("%d ", s);  // 输出起点
    queue[rear++] = s;  // 将起点加入队列
    while (front < rear) {  // 当队列非空时
        int v = queue[front++];  // 取出队首元素
        for (int i = 0; i < n; i++) {
            if (graph[v][i] && !visited[i]) {  // 如果当前节点和节点 i 之间有一条边，并且节点 i 未被访问过
                visited[i] = 1;  // 标记节点 i 为已访问
                printf("%d ", i);  // 输出节点 i
                queue[rear++] = i;  // 将节点 i 加入队列
            }
        }
    }
}

上面的代码中，bfs() 函数是实现 BFS 遍历的核心部分。它接受三个参数：起点编号 s、节点总数 n 和邻接矩阵 graph[MAX_N][MAX_N]。visited 数组用于标记节点是否被访问过。queue 数组用于存储队列元素，front 和 rear 分别表示队首和队尾的下标。

通过以上的代码实现，我们就可以在 C 语言中实现有向图的深度优先遍历和广度优先遍历了。