有向图是否存在环 c代码

有向图是否存在环可以通过深度优先搜索（DFS）来判断。

首先，我们需要定义一个visited数组来表示节点是否被访问过。初始时，visited数组的所有元素均设为未访问过。

然后，我们可以从图中的任意一个节点开始进行深度优先搜索。在深度优先搜索的过程中，每次访问一个节点时，首先将该节点的visited值设为正在访问，并将其所有的未访问的邻居节点递归调用DFS进行深度优先搜索。当递归调用DFS时，如果发现邻居节点已经被访问过且其visited值为正在访问，则说明存在环。最后，在访问结束后，将节点的visited值设为已访问。

以下是用C语言实现的判断有向图是否存在环的代码示例：

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

#define SIZE 100 // 有向图的最大节点数

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

struct Node {
    int value;
    struct Node* next;
};

struct Graph {
    int num_nodes;
    struct Node** adj_list;
};

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adj_list[src];
    graph->adj_list[src] = newNode;
}

int hasCycleUtil(struct Graph* graph, int node, int* visited) {
    visited[node] = 1; // 将节点标记为正在访问

    struct Node* neighbor = graph->adj_list[node];
    while (neighbor != NULL) {
        if (visited[neighbor->value] == 1) {
            return 1; // 如果邻居节点已经被访问过，则存在环
        }
        if (visited[neighbor->value] == 0 && hasCycleUtil(graph, neighbor->value, visited)) {
            return 1; // 递归调用DFS，判断邻居节点是否存在环
        }
        neighbor = neighbor->next;
    }

    visited[node] = 2; // 将节点标记为已访问
    return 0;
}

int hasCycle(struct Graph* graph) {
    int i;
    for (i = 0; i < graph->num_nodes; i++) {
        visited[i] = 0; // 初始化visited数组
    }

    for (i = 0; i < graph->num_nodes; i++) {
        if (visited[i] == 0 && hasCycleUtil(graph, i, visited)==1) {
            return 1; // 从每个未访问的节点开始进行DFS，如果存在环则返回1
        }
    }
    return 0;
}

int main() {
    int numNodes, numEdges, i;
    printf("请输入有向图的节点数和边数：");
    scanf("%d%d", &numNodes, &numEdges);

    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->num_nodes = numNodes;
    graph->adj_list = (struct Node**)malloc(numNodes * sizeof(struct Node*));

    for (i = 0; i < numNodes; i++) {
        graph->adj_list[i] = NULL;
    }

    for (i = 0; i < numEdges; i++) {
        int src, dest;
        printf("请输入第%d条边的起点和终点：", i + 1);
        scanf("%d%d", &src, &dest);
        addEdge(graph, src, dest);
    }

    if (hasCycle(graph)) {
        printf("有向图存在环\n");
    }
    else {
        printf("有向图不存在环\n");
    }

    return 0;
}

以上是通过DFS算法判断有向图是否存在环的C语言代码。代码的核心是hasCycleUtil函数，利用visited数组来标记节点的访问状态，通过递归调用DFS，判断邻居节点是否被访问过且visited值为正在访问，从而判断是否存在环。