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.”；否则，按照逆序输出拓扑序列即可。

Answer 2

引用 皆我百晓生 小程序回复内容作答：
判断有向图是否存在环路可以采用深度优先搜索（DFS）的方法。

具体步骤如下：

1. 创建一个数组visited[V]，用于记录每个顶点的访问状态。初值设为0。

2. 针对图中的每个顶点v，如果visited[v]为0，则调用DFS(v)进行深度优先搜索。

3. 在DFS(v)函数中，将visited[v]设为1表示顶点v已经被访问过，并递归访问顶点v的邻接顶点：

   a. 遍历顶点v的邻接顶点u，如果visited[u]为0，则递归调用DFS(u)。

   b. 如果visited[u]为1，表示顶点u已经被访问过，说明存在环路，返回1。

4. 在DFS(v)函数中，将visited[v]设为2表示顶点v的所有邻接顶点已经都访问完毕，并将顶点v加入到拓扑排序的结果中。

5. 遍历所有顶点v，如果visited[v]为1，表示顶点v已经被访问过但未加入到拓扑排序的结果中，说明存在环路，返回1。

6. 若无环路，按顶点加入拓扑排序的顺序输出拓扑排序结果。

示例代码如下：

#include <stdio.h>

#define MAX_V 100

int graph[MAX_V][MAX_V];  // 有向图的邻接矩阵表示
int visited[MAX_V];       // 访问状态数组
int topoSort[MAX_V];      // 拓扑排序结果
int index = 0;            // 拓扑排序结果的索引

int DFS(int v)
{
    visited[v] = 1;  // 标记顶点v已经被访问过

    for (int u = 0; u < MAX_V; u++)
    {
        if (graph[v][u] == 1)  // 顶点v和顶点u之间存在边
        {
            if (visited[u] == 0)  // 顶点u尚未被访问过
            {
                if (DFS(u) == 1)  // 递归访问顶点u
                {
                    return 1;  // 存在环路，返回1
                }
            }
            else if (visited[u] == 1)  // 顶点u已经被访问过但尚未加入拓扑排序结果
            {
                return 1;  // 存在环路，返回1
            }
        }
    }

    visited[v] = 2;             // 已经访问完毕，标记为2
    topoSort[MAX_V - (index++)] = v;  // 将顶点v加入拓扑排序结果

    return 0;
}

int hasCycle(int V)
{
    for (int v = 0; v < V; v++)
    {
        if (visited[v] == 0)  // 顶点v尚未被访问过
        {
            if (DFS(v) == 1)  // 从顶点v开始进行DFS
            {
                return 1;  // 存在环路，返回1
            }
        }
    }

    return 0;  // 不存在环路
}

int main()
{
    int V, E;
    printf("请输入顶点数和边数（以空格分隔）：");
    scanf("%d %d", &V, &E);

    printf("请输入每条边的起点和终点（以空格分隔）：\n");
    for (int i = 0; i < E; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
    }

    if (hasCycle(V) == 1)
    {
        printf("存在环路\n");
    }
    else
    {
        printf("不存在环路\n");
        printf("拓扑排序结果为：");
        for (int i = 0; i < V; i++)
        {
            printf("%d ", topoSort[i]);
        }
        printf("\n");
    }

    return 0;
}

这段代码通过邻接矩阵表示有向图，根据输入的顶点数和边数构建有向图的邻接矩阵。然后调用hasCycle函数判断是否存在环路，并输出拓扑排序结果。如果存在环路，则输出“存在环路”，否则输出“不存在环路”和拓扑排序结果。

注意：这里假设顶点的编号从0开始，顶点数不超过100。实际应用中，如果顶点数较大，需要根据实际情况调整MAX_V的大小，并确保邻接矩阵的构建正确。

Answer 3

以下是一种基于深度优先搜索的C语言实现，可以判断有向图是否存在环路，并输出拓扑排序。

#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100

typedef struct {
    int adj[MAX_VERTICES][MAX_VERTICES]; //邻接矩阵
    int indegree[MAX_VERTICES]; //记录每个顶点的入度
    int n; //图的顶点个数
} Graph;

//初始化图
void initGraph(Graph *g, int n) {
    g->n = n;
    for (int i = 0; i < n; i++) {
        g->indegree[i] = 0;
        for (int j = 0; j < n; j++) {
            g->adj[i][j] = 0;
        }
    }
}

//添加一条从u到v的边
void addEdge(Graph *g, int u, int v) {
    g->adj[u][v] = 1;
    g->indegree[v]++;
}

//拓扑排序
bool topsort(Graph *g, int *order) {
    int count = 0;
    int indegree[MAX_VERTICES];
    for (int i = 0; i < g->n; i++) {
        indegree[i] = g->indegree[i];
    }
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;
    for (int i = 0; i < g->n; i++) {
        if (indegree[i] == 0) {
            queue[rear++] = i;
        }
    }
    while (front < rear) {
        int u = queue[front++];
        order[count++] = u;
        for (int v = 0; v < g->n; v++) {
            if (g->adj[u][v]) {
                indegree[v]--;
                if (indegree[v] == 0) {
                    queue[rear++] = v;
                }
            }
        }
    }
    if (count != g->n) { //存在环路
        return false;
    } else {
        return true;
    }
}

//深度优先搜索
bool dfs(Graph *g, int v, bool *visited, bool *stack) {
    visited[v] = true;
    stack[v] = true;
    for (int i = 0; i < g->n; i++) {
        if (g->adj[v][i]) {
            if (!visited[i]) {
                if (dfs(g, i, visited, stack)) {
                    return true;
                }
            } else if (stack[i]) {
                return true;
            }
        }
    }
    stack[v] = false;
    return false;
}

//判断是否存在环路
bool hasCycle(Graph *g) {
    bool visited[MAX_VERTICES] = { false };
    bool stack[MAX_VERTICES] = { false };
    for (int i = 0; i < g->n; i++) {
        if (!visited[i]) {
            if (dfs(g, i, visited, stack)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    Graph g;
    initGraph(&g, 6);
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 3);
    addEdge(&g, 2, 4);
    addEdge(&g, 3, 5);
    int order[MAX_VERTICES];
    if (hasCycle(&g)) {
        printf("Graph has cycle\n");
    } else {
        if (topsort(&g, order)) {
            printf("Topological order: ");
            for (int i = 0; i < g.n; i++) {
                printf("%d ", order[i]);
            }
        } else {
            printf("Graph has cycle\n");
        }
    }
    return 0;
}

在上面的例子中，首先定义了一个有向图，然后利用 addEdge 函数添加了若干条边，接着分别调用了 hasCycle 和 topsort 函数来判断有向图是否存在环路并输出拓扑排序。可以根据需要修改有向图的大小和具体的边，并在运行程序时观察输出结果。

Answer 4

在C语言中，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来判断有向图是否存在环路。这里提供一种基于DFS的方法：
首先，我们需要定义一个数组来表示每个节点的状态。我们可以定义一个大小为节点数的数组 visited，其中 visited[i] 等于1表示节点 i 已经被访问过，等于0表示节点 i 尚未被访问。
接下来，我们需要定义一个邻接表来存储有向图中的边。邻接表可以定义为一个大小为节点数的数组，每个数组元素都是一个指向另一个节点的指针数组。
在判断有向图是否存在环路时，我们可以从任意一个节点开始进行DFS遍历。对于每个节点，我们首先将其标记为已访问状态，然后遍历其所有邻居节点。如果存在一个邻居节点已经被访问过，则说明存在一条从当前节点到该节点的路径，因此图存在环路。如果所有的邻居节点都未被访问过，则继续递归地遍历这些邻居节点。
如果图不存在环路，则可以使用拓扑排序算法求出该图的拓扑排序。拓扑排序算法也是基于DFS的，但是它要求图中不存在环路。具体实现方法可以参考以下代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100  // 最大节点数
int graph[MAX_VERTICES][MAX_VERTICES];  // 邻接表
int visited[MAX_VERTICES];  // 节点状态数组
int topo_order[MAX_VERTICES];  // 拓扑排序结果数组
int topo_count;  // 拓扑排序结果个数
// 判断有向图是否存在环路
int has_cycle() {
    for (int i = 0; i < MAX_VERTICES; i++) {
        if (visited[i] == 0) {  // 当前节点未被访问过
            visited[i] = 1;  // 标记为已访问过
            for (int j = 0; j < MAX_VERTICES; j++) {
                if (graph[i][j] == 1 && visited[j] == 1) {  // 存在一条从当前节点到该节点的路径
                    return 1;  // 图存在环路
                }
            }
        }
    }
    return 0;  // 图不存在环路
}
// 拓扑排序算法求出有向图的拓扑排序
void topological_sort() {
    for (int i = 0; i < MAX_VERTICES; i++) {
        visited[i] = 0;  // 初始化所有节点状态为未访问过
    }
    if (has_cycle()) {  // 如果图存在环路，则无法进行拓扑排序
        printf("The graph has cycles.\n");
        return;
    }
    for (int i = 0; i < MAX_VERTICES; i++) {
        if (visited[i] == 0) {  // 当前节点未被访问过
            visited[i] = 1;  // 标记为已访问过
            for (int j = 0; j < MAX_VERTICES; j++) {
                if (graph[i][j] == 1) {  // 遍历当前节点的所有邻居节点
                    topo_order[topo_count++] = j;  // 将邻居节点加入拓扑排序结果数组中
                }
            }
        }
    }
    printf("Topological order: ");
    for (int i = 0; i < topo_count; i++) {
        printf("%d ", topo_order[i]);
    }
    printf("\n");
}
int main() {
    // 读入图的邻接表表示方式
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = graph[v][u] = 1;  // 有向图用邻接表表示时，需要同时记录两条边
    }
    topological_sort();  // 求出有向图的拓扑排序
    return 0;
}

Answer 5

结合GPT给出回答如下请题主参考
判断有向图是否存在环路，可以使用拓扑排序来实现，如果拓扑排序的过程中不存在入度为0的顶点，则说明该图存在环路。

拓扑排序的过程大致如下：

1. 初始化一个队列，并将所有入度为0的顶点入队。

2. 循环对队列中的顶点进行操作，每次取出队首的顶点，并将其加入拓扑序列中。

3. 将该顶点的所有出边的终点的入度减1，并将所有入度变为0的顶点入队。

4. 如果队列为空，但是拓扑序列中的顶点数量小于图的顶点数量，则说明存在环路，否则拓扑序列就是图的一个拓扑排序。

下面是C语言实现的代码案例：

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

#define MAXV 100 // 最大顶点数
#define OK 1
#define ERROR 0

typedef int Status;

// 邻接表结构体
typedef struct EdgeNode {
    int adjvex; // 该边的终点
    struct EdgeNode *next; // 指向下一条边的指针
} EdgeNode;

typedef struct VertexNode {
    int data; // 顶点信息
    int indegree; // 顶点的入度
    EdgeNode *firstedge; // 指向第一条依附该顶点的边的指针
} VertexNode, AdjList[MAXV];

typedef struct {
    AdjList adjList; // 图的邻接表
    int vexnum, arcnum; // 顶点数和边数
} Graph;

// 创建图
Status createGraph(Graph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &(G->vexnum), &(G->arcnum));
    if (G->vexnum < 1 || G->vexnum > MAXV || G->arcnum < 0) {
        printf("输入参数有误！\n");
        return ERROR;
    }
    for (int i = 0; i < G->vexnum; i++) {
        printf("请输入第 %d 个顶点的信息：", i);
        scanf("%d", &(G->adjList[i].data));
        G->adjList[i].firstedge = NULL;
        G->adjList[i].indegree = 0;
    }
    for (int i = 0; i < G->arcnum; i++) {
        printf("请输入第 %d 条边的起点和终点：", i);
        int start, end;
        scanf("%d%d", &start, &end);
        if (start < 0 || start >= G->vexnum || end < 0 || end >= G->vexnum) {
            printf("输入参数有误！\n");
            return ERROR;
        }
        EdgeNode *e = (EdgeNode *) malloc(sizeof(EdgeNode));
        e->adjvex = end;
        e->next = G->adjList[start].firstedge;
        G->adjList[start].firstedge = e;
        G->adjList[end].indegree++;
    }
    return OK;
}

// 拓扑排序
Status topoSort(Graph *G) {
    int count = 0; // 记录已经输出的顶点数
    int topo[MAXV]; // 拓扑序列
    int front = -1, rear = -1; // 队列的头和尾
    for (int i = 0; i < G->vexnum; i++) {
        if (G->adjList[i].indegree == 0) {
            topo[++rear] = i; // 将入度为0的顶点入队
        }
    }
    while (front != rear) {
        int u = topo[++front]; // 取出队首顶点
        printf("%d ", G->adjList[u].data); // 输出该顶点
        count++;
        for (EdgeNode *e = G->adjList[u].firstedge; e != NULL; e = e->next) {
            int v = e->adjvex;
            if (--(G->adjList[v].indegree) == 0) { // 将所有出边的终点的入度减1
                topo[++rear] = v; // 入度变为0的顶点入队
            }
        }
    }
    if (count < G->vexnum) { // 如果输出的顶点数小于图的顶点数，则说明存在环路
        return ERROR;
    }
    return OK;
}

int main() {
    Graph G;
    if (createGraph(&G) == OK) {
        if (topoSort(&G)) {
            printf("\n存在环路！\n");
        } else {
            printf("\n拓扑排序：\n");
        }
    }
    return 0;
}

Answer 6

以下是使用C语言实现判断有向图是否存在环路以及求拓扑排序的代码示例：

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

#define MAX_VERTEX 100 // 假设最多有100个顶点

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

struct Graph {
    int numVertex;
    struct Node* adjacencyList[MAX_VERTEX];
    int indegree[MAX_VERTEX];
};

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

struct Graph* createGraph(int numVertex) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertex = numVertex;

    for (int i = 0; i < numVertex; ++i) {
        graph->adjacencyList[i] = NULL;
        graph->indegree[i] = 0;
    }

    return graph;
}

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

    // 计算每个节点的入度
    graph->indegree[dest]++;
}

bool hasCycleUtil(struct Graph* graph, int v, bool visited[], bool recStack[]) {
    visited[v] = true;
    recStack[v] = true;

    struct Node* temp = graph->adjacencyList[v];
    while (temp != NULL) {
        if (!visited[temp->vertex] && hasCycleUtil(graph, temp->vertex, visited, recStack))
            return true;
        else if (recStack[temp->vertex])
            return true;

        temp = temp->next;
    }

    recStack[v] = false;
    return false;
}

bool hasCycle(struct Graph* graph) {
    bool visited[MAX_VERTEX];
    bool recStack[MAX_VERTEX];
    for (int i = 0; i < graph->numVertex; ++i) {
        visited[i] = false;
        recStack[i] = false;
    }

    for (int i = 0; i < graph->numVertex; ++i) {
        if (!visited[i]) {
            if (hasCycleUtil(graph, i, visited, recStack))
                return true;
        }
    }

    return false;
}

void topologicalSortUtil(struct Graph* graph, int v, bool visited[], int stack[], int* index) {
    visited[v] = true;

    struct Node* temp = graph->adjacencyList[v];
    while (temp != NULL) {
        if (!visited[temp->vertex])
            topologicalSortUtil(graph, temp->vertex, visited, stack, index);

        temp = temp->next;
    }

    stack[(*index)] = v;
    (*index)--;
}

void topologicalSort(struct Graph* graph) {
    int stack[MAX_VERTEX];
    int index = graph->numVertex - 1;

    bool visited[MAX_VERTEX];
    for (int i = 0; i < graph->numVertex; ++i)
        visited[i] = false;

    for (int i = 0; i < graph->numVertex; ++i) {
        if (!visited[i])
            topologicalSortUtil(graph, i, visited, stack, &index);
    }

    printf("拓扑排序的结果：\n");
    for (int i = 0; i < graph->numVertex; ++i)
        printf("%d ", stack[i]);
}

int main() {
    int numVertex = 6;
    struct Graph* graph = createGraph(numVertex);

    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 5);

    bool hasCycleFlag = hasCycle(graph);

    if (hasCycleFlag)
        printf("该图存在环路\n");
    else {
        printf("该图不存在环路\n");
        topologicalSort(graph);
    }

    return 0;
}

这里假设图最多有100个顶点，可以根据需要调整MAX_VERTEX的值。首先创建了Node结构，用于表示有向图中的顶点，然后定义了Graph结构，用于存储有向图的邻接链表以及顶点的入度。createNode函数用于创建新的节点，createGraph函数用于创建图，并初始化邻接链表和入度数组。addEdge函数用于添加边，同时计算每个节点的入度。hasCycleUtil函数是图中检测环路的工具函数，采用深度优先搜索（DFS）的方式进行递归遍历。hasCycle函数利用hasCycleUtil函数判断图中是否存在环路。topologicalSortUtil函数是进行拓扑排序的工具函数，它也是利用深度优先搜索（DFS）的方式进行递归遍历，并将结果存储在栈中。topologicalSort函数调用topologicalSortUtil函数进行拓扑排序，并输出结果。

在示例中，我们创建了一个包含6个顶点的有向图，并添加了一些边。首先判断该图是否存在环路，如果不存在环路，则进行拓扑排序并输出结果。

Answer 7

#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
typedef struct {
    int adj[MAX_VERTICES][MAX_VERTICES]; //邻接矩阵
    int indegree[MAX_VERTICES]; //记录每个顶点的入度
    int n; //图的顶点个数
} Graph;
//初始化图
void initGraph(Graph *g, int n) {
    g->n = n;
    for (int i = 0; i < n; i++) {
        g->indegree[i] = 0;
        for (int j = 0; j < n; j++) {
            g->adj[i][j] = 0;
        }
    }
}
//添加一条从u到v的边
void addEdge(Graph *g, int u, int v) {
    g->adj[u][v] = 1;
    g->indegree[v]++;
}
//拓扑排序
bool topsort(Graph *g, int *order) {
    int count = 0;
    int indegree[MAX_VERTICES];
    for (int i = 0; i < g->n; i++) {
        indegree[i] = g->indegree[i];
    }
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;
    for (int i = 0; i < g->n; i++) {
        if (indegree[i] == 0) {
            queue[rear++] = i;
        }
    }
    while (front < rear) {
        int u = queue[front++];
        order[count++] = u;
        for (int v = 0; v < g->n; v++) {
            if (g->adj[u][v]) {
                indegree[v]--;
                if (indegree[v] == 0) {
                    queue[rear++] = v;
                }
            }
        }
    }
    if (count != g->n) { //存在环路
        return false;
    } else {
        return true;
    }
}
//深度优先搜索
bool dfs(Graph *g, int v, bool *visited, bool *stack) {
    visited[v] = true;
    stack[v] = true;
    for (int i = 0; i < g->n; i++) {
        if (g->adj[v][i]) {
            if (!visited[i]) {
                if (dfs(g, i, visited, stack)) {
                    return true;
                }
            } else if (stack[i]) {
                return true;
            }
        }
    }
    stack[v] = false;
    return false;
}
//判断是否存在环路
bool hasCycle(Graph *g) {
    bool visited[MAX_VERTICES] = { false };
    bool stack[MAX_VERTICES] = { false };
    for (int i = 0; i < g->n; i++) {
        if (!visited[i]) {
            if (dfs(g, i, visited, stack)) {
                return true;
            }
        }
    }
    return false;
}
int main() {
    Graph g;
    initGraph(&g, 6);
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 3);
    addEdge(&g, 2, 4);
    addEdge(&g, 3, 5);
    int order[MAX_VERTICES];
    if (hasCycle(&g)) {
        printf("Graph has cycle\n");
    } else {
        if (topsort(&g, order)) {
            printf("Topological order: ");
            for (int i = 0; i < g.n; i++) {
                printf("%d ", order[i]);
            }
        } else {
            printf("Graph has cycle\n");
        }
    }
    return 0;
}

Answer 8

1. 初始化一个空的结果列表result和一个空的访问标记列表visited。
2. 对于图G中的每一个节点v：
   • 如果v没有被访问过，那么执行DFS(v)。
   • 在DFS中，对于节点v的每一个邻接节点n：
     • 如果n没有被访问过，那么递归调用DFS(n)。
     • 如果n正在被访问（即n在栈中），那么说明存在环路，返回false。
   • 如果不存在环路，那么在DFS的逆后序遍历中，将节点v添加到result中。
3. 如果不存在环路，那么返回result，即为该图的拓扑排序。

以下是Python代码实现：

def topological_sort(G):
    result = []
    visited = [False] * len(G)
    
    def dfs(node):
        visited[node] = True
        for neighbor in G[node]:
            if not visited[neighbor]:
                if dfs(neighbor):
                    return True
            elif visited[neighbor] == True:
                return True
        visited[node] = False
        return False
    
    for node in range(len(G)):
        if not visited[node]:
            if dfs(node):
                return None  # 存在环路
    return result[::-1]  # 逆后序遍历

Answer 9

判断图是否存在环路并进行拓扑排序

from collections import defaultdict, deque

def topological_sort(graph):
    # 计算入度
    in_degree = defaultdict(int)
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    
    # 将入度为0的顶点加入队列
    queue = deque([u for u in graph if in_degree[u] == 0])
    
    # 存储拓扑排序结果
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        
        # 更新相邻顶点的入度
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    # 如果所有顶点都在拓扑排序结果中，说明是DAG
    if len(result) == len(graph):
        return result
    else:
        return None  # 存在环路

# 示例用法
graph = {
    'A': ['B', 'C'],
    'B': ['C', 'D'],
    'C': ['D'],
    'D': []
}

topo_sort_result = topological_sort(graph)
if topo_sort_result:
    print("拓扑排序结果:", topo_sort_result)
else:
    print("图中存在环路")

Answer 10

参考gpt：
判断一个有向图是否存在环路，可以使用拓扑排序算法。拓扑排序是一种对有向无环图（DAG）进行排序的算法，如果成功完成拓扑排序，那么图中不存在环路；反之，如果拓扑排序失败，说明图中存在环路。

以下是使用C语言的示例代码来实现判断有向图是否存在环路以及拓扑排序的过程。我们将使用邻接表来表示有向图。

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

#define MAX_VERTICES 100

// 邻接表节点结构
struct Node {
    int data;
    struct Node* next;
};

// 图结构
struct Graph {
    int numVertices;
    struct Node** adjLists;
};

// 创建图
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// 拓扑排序的辅助函数
int topologicalSortUtil(struct Graph* graph, int v, int visited[], int stack[]) {
    visited[v] = 1;

    struct Node* temp = graph->adjLists[v];
    while (temp != NULL) {
        int adjVertex = temp->data;
        if (!visited[adjVertex]) {
            if (topologicalSortUtil(graph, adjVertex, visited, stack)) {
                return 1; // 存在环路
            }
        } else if (visited[adjVertex] == 1) {
            return 1; // 存在环路
        }
        temp = temp->next;
    }

    visited[v] = 2;
    stack[--stack[0]] = v;
    return 0;
}

// 拓扑排序
int topologicalSort(struct Graph* graph, int result[]) {
    int* visited = (int*)malloc(graph->numVertices * sizeof(int));
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = 0;
    }

    int* stack = (int*)malloc((graph->numVertices + 1) * sizeof(int));
    stack[0] = graph->numVertices; // 栈顶指针

    for (int i = 0; i < graph->numVertices; i++) {
        if (!visited[i]) {
            if (topologicalSortUtil(graph, i, visited, stack)) {
                free(visited);
                free(stack);
                return 1; // 存在环路
            }
        }
    }

    // 没有环路，将拓扑排序结果保存在result数组中
    for (int i = 0; i < graph->numVertices; i++) {
        result[i] = stack[i + 1];
    }

    free(visited);
    free(stack);
    return 0; // 拓扑排序成功
}

int main() {
    int vertices, edges;
    printf("请输入有向图的顶点数和边数: ");
    scanf("%d %d", &vertices, &edges);

    struct Graph* graph = createGraph(vertices);

    printf("请输入每条边的起点和终点:\n");
    for (int i = 0; i < edges; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    int* result = (int*)malloc(vertices * sizeof(int));

    if (topologicalSort(graph, result)) {
        printf("存在环路，无法进行拓扑排序。\n");
    } else {
        printf("拓扑排序结果为: ");
        for (int i = 0; i < vertices; i++) {
            printf("%d ", result[i]);
        }
        printf("\n");
    }

    free(result);
    return 0;
}

Answer 11

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
 
#define INFO_MAX_SIZE 20
#define MAX_SIZE 200
 //领接矩阵存储的图
struct Graph{
    int vexNumber;
    string vexInfo[INFO_MAX_SIZE];
    int adjMatrix[MAX_SIZE][MAX_SIZE];
};
 //弧结点定义
struct ArcNode{
    int weight;//弧上的信息部分
    int adj;//邻接点的序号
    ArcNode *nextarc;
};
 //顶点结点定义
struct VexNode{
    string Info;
    ArcNode *firstarc;
};
 //领接表结构的图的定义
struct linkGraph{
    VexNode *vexes;
    int vexnumber;
};
 
struct tempNode{
    int col;
    int row;
    //tempNode *next;
};
 
struct temp{
    int num;
    tempNode *docu;
};
 
 
int preInitGraph(linkGraph &G,const Graph &g){
    G.vexes=new VexNode[g.vexNumber];
    G.vexnumber=g.vexNumber;
    for(int i=0;i<g.vexNumber;i++){
        G.vexes[i].firstarc=NULL;
    }
    return 0;
}
//将邻接矩阵存储的图转换为领接表存储的图
void InitGraph(linkGraph &G,const Graph &g,temp &t){
    preInitGraph(G,g);
    for(int i=0;i<t.num;i++){
        int a,b;
        a=t.docu[i].row;b=t.docu[i].col;
        ArcNode *p=new ArcNode();
        p->nextarc=NULL;
        p->adj=b;
        ArcNode *q=G.vexes[a].firstarc;
        if(G.vexes[a].firstarc==NULL)
            G.vexes[a].firstarc=p;
        else{
            while(q->nextarc!=NULL){
                q=q->nextarc;
            }
            q->nextarc=p;
        }
    }
}
 
int TopologicalSort(linkGraph LG,int Topo[]){
    vector<int>indegree(LG.vexnumber);
    for(int i=0;i<LG.vexnumber;i++) indegree[i]=0;
    for(int i=0;i<LG.vexnumber;i++){
        for(ArcNode *p=LG.vexes[i].firstarc;p!=nullptr;p=p->nextarc)
            indegree[p->adj]++;
    }
    //入度为零的点入栈
    stack<int>s;
    for(int i=0;i<LG.vexnumber;i++){
        if(indegree[i]==0)  s.push(i);
    }
 
    int i=0;
    while(!s.empty()){
        int j=s.top();s.pop();
        Topo[i++]=j;
        //将Vj邻接点入度减一，减为0的入栈
        for(ArcNode *p=LG.vexes[j].firstarc;p!=nullptr;p=p->nextarc){
            indegree[p->adj]--;
            if(indegree[p->adj]==0)  s.push(p->adj);
        }
    }
    if(i==LG.vexnumber)  return 0;
    else  return 1;
}
 
 
 
 
//comment
 
int main(){
    //freopen("/config/workspace/test/test","r",stdin);
    int n,m;
    cin>>n>>m;
    while(n!=0){
        Graph G;
        G.vexNumber=n;
        temp t;
        t.num=m;
        t.docu=new tempNode[m];
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            t.docu[i].row=a-1;
            t.docu[i].col=b-1;
        }
        linkGraph LG;
        InitGraph(LG,G,t);
        int Topo[LG.vexnumber];
        int flag=TopologicalSort(LG,Topo);
        if(flag==0)  cout<<"NO"<<endl;
        else  cout<<"YES"<<endl;
        cin>>n>>m;
    }
    
    return 0;
}

Answer 12

以下回答结合了AI回答
为了判断有向图是否存在环路，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法。下面是使用 DFS 和 BFS 判断有向图是否存在环路的 C 语言代码示例。在判断出是否存在环路后，可以使用拓扑排序算法对图进行排序。

```c  
#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>
typedef int VertexType;  
typedef enum DG, UDG GraphType;  
typedef struct ArcNode {  
   int adjvex;  
   struct ArcNode *nextarc;  
} ArcNode;
typedef struct VNode {  
   VertexType data;  
   ArcNode *firstarc;  
} VNode, AdjList[VertexType];
typedef struct {  
   VertexType vexnum;  
   AdjList adjlist;  
} ALGraph;
// DFS 判断有向图是否存在环路  
void dfs(ALGraph *G, VertexType v, bool *has_cycle) {  
   if (v == G->vexnum) {  
       *has_cycle = true;  
       return;  
   }
   ArcNode *p = G->adjlist[v].firstarc;  
   while (p) {  
       if (!visited[p->adjvex]) {  
           visited[p->adjvex] = true;  
           dfs(G, p->adjvex, has_cycle);  
       }  
       p = p->nextarc;  
   }  
}
// BFS 判断有向图是否存在环路  
void bfs(ALGraph *G, VertexType v, bool *has_cycle) {  
   if (v == G->vexnum) {  
       *has_cycle = true;  
       return;  
   }
   ArcNode *p = G->adjlist[v].firstarc;  
   while (p) {  
       if (!visited[p->adjvex]) {  
           q[++r] = p->adjvex;  
           visited[p->adjvex] = true;  
       }  
       p = p->nextarc;  
   }
   while (r > 0) {  
       VertexType u = q[r - 1];  
       ArcNode *p = G->adjlist[u].firstarc;  
       while (p) {  
           if (!visited[p->adjvex]) {  
               dfs(G, p->adjvex, has_cycle);  
           }  
           p = p->nextarc;  
       }  
       r--;  
   }  
}
// 拓扑排序  
void topological_sort(ALGraph *G) {  
   int vexnum = G->vexnum;  
   bool visited[vexnum] = {false};  
   bool has_cycle = false;
   for (int i = 0; i < vexnum; i++) {  
       if (!visited[i]) {  
           bfs(G, i, &has_cycle);  
           if (has_cycle) {  
               break;  
           }  
       }  
   }
   if (!has_cycle) {  
       printf("拓扑排序结果：\n");  
       for (int i = 0; i < vexnum; i++) {  
           ArcNode *p = G->adjlist[i].firstarc;  
           while (p) {  
               printf("%d -> %d\n", i, p->adjvex);  
               p = p->nextarc;  
           }  
       }  
   } else {  
       printf("图中存在环路。\n");  
   }  
}
int main() {  
   // 创建有向图  
   ALGraph G;  
   G.vexnum = 6;  
   G.adjlist = (AdjList[VertexType])malloc(6 * sizeof(AdjList[VertexType]));
   // 添加边  
   G.adjlist[0].firstarc = (ArcNode *)malloc(sizeof(ArcNode));  
   G.adjlist[0].firstarc->adjvex = 1;  
   G.adjlist[0].firstarc->nextarc = NULL;
   G.adjlist[1].firstarc = (ArcNode *)malloc(sizeof(ArcNode));  
   G.adjlist[1].firstarc->adjvex = 2;

Answer 13

#include <iostream>  
#include <vector>  
#include <stack>  
using namespace std;  
  
const int MAXN = 1000; // 最大节点数  
vector<int> G[MAXN]; // 邻接表存图  
bool visited[MAXN]; // 标记数组  
stack<int> S; // 存储拓扑排序的栈  
  
// DFS函数  
void DFS(int v) {  
    visited[v] = true; // 标记为已访问  
    for (int i = 0; i < G[v].size(); i++) {  
        int u = G[v][i];  
        if (!visited[u]) { // 如果邻居节点没有被访问过  
            DFS(u); // 递归调用DFS函数  
        } else if (visited[u] && !S.empty() && S.top() == u) { // 如果邻居节点已经被访问过并且在栈中  
            cout << "存在环路" << endl;  
            exit(0); // 存在环路，退出程序  
        }  
    }  
    S.push(v); // 将节点加入栈中  
}  
  
int main() {  
    int n, m; // n表示节点数，m表示边数  
    cin >> n >> m;  
    for (int i = 0; i < m; i++) {  
        int u, v; // u表示起点，v表示终点  
        cin >> u >> v;  
        G[u].push_back(v); // 将边加入邻接表中  
    }  
    for (int i = 1; i <= n; i++) { // 对于每个节点进行DFS遍历  
        if (!visited[i]) {  
            DFS(i);  
        }  
    }  
    if (S.size() == n) { // 如果遍历了所有节点并且没有环路，则输出拓扑排序序列  
        while (!S.empty()) {  
            cout << S.top() << " ";  
            S.pop();  
        }  
        cout << endl;  
    } else { // 如果存在环路则输出无法拓扑排序的信息  
        cout << "无法拓扑排序" << endl;  
    }  
    return 0;  
}

Answer 14

【相关推荐】

• 你可以参考下这篇文章：C语言：求不带权无向连通图 G 中距离顶点 v 最远的一个顶点算法

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

Answer 15

应该是要使用DFS算法，进行判断，你看下这个例子

#include <stdio.h>  
#include <stdbool.h>  
#define MAX_VEX 100   // 最大顶点数  
  
int n;               // 顶点数  
int G[MAX_VEX][MAX_VEX];   // 邻接表  
bool visited[MAX_VEX];      // 记录每个顶点是否被访问过  
int topo_order[MAX_VEX];    // 拓扑排序结果  
  
bool dfs(int v) {  
    visited[v] = true;  
    for (int i = 0; i < n; i++) {  
        if (G[v][i] && !visited[i]) {  
            if (dfs(i)) {  
                return true;  
            }  
        }  
    }  
    topo_order[n - 1 - v] = v;  // 将当前顶点加入拓扑排序结果中  
    return false;  
}  
  
bool has_cycle() {  
    for (int i = 0; i < n; i++) {  
        if (!visited[i]) {  
            if (dfs(i)) {  
                return true;  
            }  
        }  
    }  
    return false;  
}  
  
int main() {  
    // 读入顶点数和边数  
    scanf("%d", &n);  
    // 读入邻接表  
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n; j++) {  
            scanf("%d", &G[i][j]);  
        }  
    }  
    // 判断是否存在环路  
    if (has_cycle()) {  
        printf("图中存在环路\n");  
    } else {  
        printf("图中不存在环路，拓扑排序结果为：");  
        for (int i = 0; i < n; i++) {  
            printf("%d ", topo_order[i]);  
        }  
        printf("\n");  
    }  
    return 0;  
}

Answer 16

可以参考下

图——判断有向图中是否有环_有向图判环-CSDN博客 1. 判断有向图中是否有环给定有向图，检查该图是否包含循环。如果给定图包含至少一个循环，则函数应返回true，否则返回false。1.1. 方法一：DFS1.1.1. 思路对一个图进行DFS， 则DFS的路径可以生成一个棵树。对于DFS树上的结点，如果存在指向祖先的边或指向自己边，则图存在回路。（这种边叫做后向边）下面通过图来描述一下：有向图，如下。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JzaHYM3F-1607045914066)(D:\笔记图片集_有向图判环 https://blog.csdn.net/weixin_43326910/article/details/110622703

算法复习——图算法篇之图中环路的存在性判断_图的环路性质-CSDN博客 算法复习——图算法篇之图中环路的存在性判断以下内容主要参考中国大学MOOC《算法设计与分析》，墙裂推荐希望入门算法的童鞋学习！1. 问题定义有向图中环路的存在性判断输入：有向图G=G=G=，VVV是顶点集合，EEE是边的集合输出：图GGG是否存在环2. 猜想证明​根据有向图中深度优先搜索边的性质，并研究实例，我们可以猜想有向图存在环路等价于搜索时出现后向边。证明：充分性：不妨设环路上被搜索的第一个点_图的环路性质 https://blog.csdn.net/NickHan_cs/article/details/113132359