C语言判断有向图是否存在环路

Question

给定一个有向图G（V，E），请判断该图是否存在环路，如果不存在则求出该图的拓扑排序。

Answer 1

该回答引用ChatGPT，希望对题主有所帮助，如有帮助，还望采纳。

---

可以使用深度优先遍历来判断有向图是否存在环路。具体做法是，在遍历的过程中，如果发现当前节点已经被访问过，而且它的状态是“正在遍历”，则可以判断出这个图存在环路。如果遍历完成后都没有找到环路，则可以使用拓扑排序来获得图的拓扑序列。

以下是代码实现：

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

#define MAX_VERTICES 100

int visited[MAX_VERTICES]; // 记录节点的访问状态
int is_cyclic = 0; // 是否存在环路的标志
int topological_order[MAX_VERTICES]; // 存储拓扑序列的数组
int order_index = 0; // 拓扑序列数组的下标

typedef struct Node {
    int vertex;
    Node* next;
} Node;

Node* create_node(int vertex) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->vertex = vertex;
    node->next = NULL;
    return node;
}

void add_edge(Node* graph[], int u, int v) {
    Node* node = create_node(v);
    node->next = graph[u];
    graph[u] = node;
}

void dfs(Node* graph[], int u) {
    visited[u] = 1; // 标记当前节点为“正在遍历”
    Node* node = graph[u];
    while (node != NULL) {
        int v = node->vertex;
        if (visited[v] == 1) { // 如果当前节点已经被访问过且状态是“正在遍历”，说明存在环路
            is_cyclic = 1;
            return;
        }
        if (visited[v] == 0) { // 如果当前节点没有被访问过，则继续遍历
            dfs(graph, v);
        }
        node = node->next;
    }
    visited[u] = 2; // 标记当前节点为“已经遍历完成”
    topological_order[order_index++] = u; // 将当前节点添加到拓扑序列中
}

void topological_sort(Node* graph[], int n) {
    for (int i = 0; i < n; i++) {
        visited[i] = 0; // 初始化状态数组
    }
    is_cyclic = 0; // 初始化环路标志
    order_index = 0; // 初始化拓扑序列数组的下标
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) { // 对于每个未被访问过的节点进行深度优先遍历
            dfs(graph, i);
            if (is_cyclic == 1) { // 如果发现存在环路，则直接退出拓扑排序
                printf("The graph has a cycle.\n");
                return;
            }
        }
    }
    printf("The topological order of the graph is:\n");
    for (int i = order_index - 1; i >= 0; i--) { // 按照逆序输出拓扑序列
        printf("%d ", topological_order[i]);
    }
    printf("\n");
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    Node* graph[MAX_VERTICES] = {NULL};
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(graph, u, v);
    }
    topological_sort(graph, n);
    return 0;
}

在该实现中，使用了一个全局数组 visited 来记录节点的访问状态。对于每个节点，它的访问状态可能有以下三种：

1. visited[i] = 0：表示当前节点还没有被访问过。
2. visited[i] = 1：表示当前节点已经被访问过，但是它的后续节点还没有被遍历完（即它的状态是“正在遍历”）。
3. visited[i] = 2：表示当前节点已经被遍历完成。

在深度优先遍历中，如果发现当前节点已经被访问过，而且它的状态是“正在遍历”，则可以判断出这个图存在环路。如果遍历完成后都没有找到环路，则可以使用拓扑排序来获得图的拓扑序列。在拓扑排序中，如果发现存在环路，则直接退出拓扑排序，并输出信息“The graph has a cycle.”；否则，按照逆序输出拓扑序列即可。