c语言邻接表 DFS算法判定有向无环图

邻接表 DFS 算法判断有向无环图（DAG）的过程如下：

1. 初始化：对每个顶点 v，设置 visited[v] = 0。

2. 对于每个未访问过的顶点 v，调用 DFS(v)。

3. 在 DFS(v) 中，首先将 visited[v] 设置为 1，表示当前顶点已经被访问过。

4. 对于 v 的每个邻接点 w，如果 visited[w] = 0，那么就调用 DFS(w)。

5. 如果在 DFS(v) 中发现 v 的某个邻接点 w 已经被访问过且 visited[w] = 1，那么说明图中存在环，不是 DAG。

6. DFS(v) 结束后，将 visited[v] 设置为 2，表示该顶点的所有邻接点都已经被访问过。

7. 如果对于所有顶点 v，visited[v] 都被设置为 2，那么说明图是 DAG。

下面是一个基于邻接表的 C 语言实现：

#define MAX_VERTEX_NUM 100

struct ArcNode {
    int adjvex;
    struct ArcNode *next;
};

struct VertexNode {
    int data;
    struct ArcNode *first;
};

struct Graph {
    struct VertexNode vertex[MAX_VERTEX_NUM];
    int vexnum, arcnum;
    int visited[MAX_VERTEX_NUM];
};

void DFS(struct Graph *G, int v)
{
    struct ArcNode *p;

    G->visited[v] = 1;
    for (p = G->vertex[v].first; p != NULL; p = p->next) {
        if (G->visited[p->adjvex] == 0)
            DFS(G, p->adjvex);
        else if (G->visited[p->adjvex] == 1) {
            printf("Graph contains a cycle.\n");
            exit(1);
        }
    }
    G->visited[v] = 2;
}

int isDAG(struct Graph *G)
{
    int i;

    for (i = 0; i < G->vexnum; i++)
        G->visited[i] = 0;

    for (i = 0; i < G->vexnum; i++)
        if (G->visited[i] == 0)
            DFS(G, i);

    return 1;
}