m0_74846037 2023-09-24 21:53 采纳率: 25%
浏览 26
已结题

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

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

  • 写回答

16条回答 默认 最新

  • bug菌¹ Java领域优质创作者 2023-09-24 22:00
    关注

    该回答引用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.”;否则,按照逆序输出拓扑序列即可。

    评论

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 9月26日
  • 创建了问题 9月24日

悬赏问题

  • ¥15 Abaqus打不开cae文件怎么办?
  • ¥20 双系统开机引导中windows系统消失问题?
  • ¥15 小程序准备上线,软件开发公司需要提供哪些资料给甲方
  • ¥15 关于生产日期批次退货退款,库存回退的问题
  • ¥15 手机应用的时间可以修改吗
  • ¥15 docker 运行OPEN-webui异常
  • ¥15 麒麟系统如何删除光盘刻录痕迹
  • ¥15 recipe通过gem协议传的是什么
  • ¥15 TS2307: Cannot find module 'cc'.
  • ¥15 100小时学会sap 书上pp章节5.22,标准成本计算逻辑?