用c语言遍历一个有邻接矩阵的有向图

假设有一个有向图的邻接矩阵如下：

#define MAX_VERTEX_NUM 100

int G[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = {
    {0, 1, 0, 0, 1},
    {0, 0, 1, 1, 1},
    {0, 0, 0, 1, 0},
    {0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0}
};

其中，G[i][j]表示从顶点i到顶点j是否有一条有向边。如果有，则G[i][j]的值为1，否则为0。

下面是用C语言实现遍历该有向图的代码：

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

#define MAX_VERTEX_NUM 100

void DFS(int G[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int n, bool visited[MAX_VERTEX_NUM], int v) {
    visited[v] = true; // 标记当前顶点为已访问
    printf("%d ", v); // 输出已访问的顶点
    for (int i = 0; i < n; i++) {
        if (G[v][i] && !visited[i]) { // 如果从当前顶点出发有一条边指向未访问的顶点，则递归访问该顶点
            DFS(G, n, visited, i);
        }
    }
}

void traverse(int G[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int n) {
    bool visited[MAX_VERTEX_NUM] = {false}; // 初始化所有顶点为未访问状态
    for (int i = 0; i < n; i++) {
        if (!visited[i]) { // 如果当前顶点未被访问，则从该顶点开始进行深度优先遍历
            DFS(G, n, visited, i);
        }
    }
}

int main() {
    int G[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = {
        {0, 1, 0, 0, 1},
        {0, 0, 1, 1, 1},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0}
    };
    traverse(G, 5);
    return 0;
}

该代码使用了深度优先遍历算法，先以第一个顶点开始进行递归遍历，对于每个顶点，找到它所能到达的所有未访问的顶点，然后递归访问这些顶点。由于使用了递归，所以该算法的空间复杂度为O(n)，时间复杂度为O(n^2)。