1076: 判断给定有向图是否存在回路

判断给定有向图是否存在回路，可以使用拓扑排序或深度优先搜索算法。如果在拓扑排序中发现有节点的入度为，但是该节点的出边指向的节点已经被访问过，那么就说明存在回路。如果使用深度优先搜索，如果在搜索过程中遇到了已经访问过但是还没有回溯的节点，那么就说明存在回路。

相关问题

以邻接矩阵为图的存储结构，设计算法判断给定的有向图是否存在回路。

可以回答这个问题。对于给定的有向图，可以使用深度优先搜索算法来判断是否存在回路。具体实现方法是，从任意一个顶点开始进行深度优先搜索，如果在搜索过程中遇到了已经访问过的顶点，则说明存在回路。如果搜索结束后仍然没有发现回路，则说明该有向图不存在回路。

C语言代码实现：建立有向图的邻接表存储，并分别对建立的有向图进行深度优先遍历和广度优先 遍历。编写算法判断在给定的有向图中是否存在一个简单有向回路。设计算法判断任意两个顶点间是否存在路径。

好的，我会尽力回答你的问题。对于你的第一个问题，以下是 C 语言代码实现建立有向图的邻接表存储，并分别对建立的有向图进行深度优先遍历和广度优先遍历的示例代码：

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

#define MAX_VERTEX_NUM 100    // 最大顶点数
typedef int VertexType;       // 顶点数据类型

// 边表结点
typedef struct ArcNode {
    int adjvex;              // 邻接点在顶点数组中的下标
    struct ArcNode *next;   // 指向下一个结点的指针
} ArcNode;

// 顶点表结点
typedef struct VertexNode {
    VertexType data;        // 顶点数据
    ArcNode *firstarc;      // 指向第一条依附该顶点的边的指针
    bool visited;           // 表示该顶点是否被访问过
} VertexNode;

// 图结构体
typedef struct {
    VertexNode vertex[MAX_VERTEX_NUM];  // 顶点数组
    int vexnum, arcnum;                 // 顶点数和边数
} Graph;

// 创建图
void CreateGraph(Graph *G)
{
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);

    // 初始化顶点表
    for (int i = 0; i < G->vexnum; i++) {
        printf("请输入第 %d 个顶点的值：", i + 1);
        scanf("%d", &G->vertex[i].data);
        G->vertex[i].firstarc = NULL;
        G->vertex[i].visited = false;
    }

    // 建立边表
    int v1, v2;
    ArcNode *arc;
    for (int i = 0; i < G->arcnum; i++) {
        printf("请输入第 %d 条边的两个顶点下标：", i + 1);
        scanf("%d %d", &v1, &v2);

        // 创建边表结点
        arc = (ArcNode *)malloc(sizeof(ArcNode));
        arc->adjvex = v2 - 1;
        arc->next = G->vertex[v1 - 1].firstarc;
        G->vertex[v1 - 1].firstarc = arc;
    }
}

// 深度优先遍历
void DFS(Graph *G, int v)
{
    printf("%d ", G->vertex[v].data);
    G->vertex[v].visited = true;

    ArcNode *arc;
    for (arc = G->vertex[v].firstarc; arc != NULL; arc = arc->next) {
        int adjvex = arc->adjvex;
        if (!G->vertex[adjvex].visited) {
            DFS(G, adjvex);
        }
    }
}

// 广度优先遍历
void BFS(Graph *G, int v)
{
    int queue[MAX_VERTEX_NUM];  // 队列
    int front = 0, rear = 0;

    printf("%d ", G->vertex[v].data);
    G->vertex[v].visited = true;
    queue[rear++] = v;

    ArcNode *arc;
    while (front < rear) {
        int v = queue[front++];

        for (arc = G->vertex[v].firstarc; arc != NULL; arc = arc->next) {
            int adjvex = arc->adjvex;
            if (!G->vertex[adjvex].visited) {
                printf("%d ", G->vertex[adjvex].data);
                G->vertex[adjvex].visited = true;
                queue[rear++] = adjvex;
            }
        }
    }
}

// 判断是否存在简单有向回路
bool HasCycle(Graph *G, int v)
{
    G->vertex[v].visited = true;

    ArcNode *arc;
    for (arc = G->vertex[v].firstarc; arc != NULL; arc = arc->next) {
        int adjvex = arc->adjvex;
        if (!G->vertex[adjvex].visited) {
            if (HasCycle(G, adjvex)) {
                return true;
            }
        } else {
            return true;
        }
    }

    G->vertex[v].visited = false;
    return false;
}

// 判断是否存在路径
bool HasPath(Graph *G, int v1, int v2)
{
    if (v1 == v2) {
        return true;
    }

    G->vertex[v1].visited = true;

    ArcNode *arc;
    for (arc = G->vertex[v1].firstarc; arc != NULL; arc = arc->next) {
        int adjvex = arc->adjvex;
        if (!G->vertex[adjvex].visited && HasPath(G, adjvex, v2)) {
            return true;
        }
    }

    return false;
}

int main()
{
    Graph G;
    CreateGraph(&G);

    printf("深度优先遍历：");
    for (int i = 0; i < G.vexnum; i++) {
        if (!G.vertex[i].visited) {
            DFS(&G, i);
        }
    }
    printf("\n");

    // 重置 visited 标记
    for (int i = 0; i < G.vexnum; i++) {
        G.vertex[i].visited = false;
    }

    printf("广度优先遍历：");
    for (int i = 0; i < G.vexnum; i++) {
        if (!G.vertex[i].visited) {
            BFS(&G, i);
        }
    }
    printf("\n");

    // 判断是否存在简单有向回路
    bool hasCycle = false;
    for (int i = 0; i < G.vexnum; i++) {
        if (!G.vertex[i].visited && HasCycle(&G, i)) {
            hasCycle = true;
            break;
        }
    }
    if (hasCycle) {
        printf("存在简单有向回路\n");
    } else {
        printf("不存在简单有向回路\n");
    }

    // 判断是否存在路径
    int v1, v2;
    printf("请输入要判断的两个顶点下标：");
    scanf("%d %d", &v1, &v2);
    if (HasPath(&G, v1 - 1, v2 - 1)) {
        printf("存在路径\n");
    } else {
        printf("不存在路径\n");
    }

    return 0;
}

对于第一个问题的 C 语言代码实现就介绍到这里了，如果有不明白的地方请随时问我。