试实现拓扑排序算法。函数void findindegree(algraph g,int indegree[])实现图中各个顶点入度的统计；函数int topologicalsort(algraph g , int topo[])获取拓扑序列。

题目要求实现拓扑排序算法。函数void findindegree(algraph g,int indegree[])实现统计图中各个顶点入度的功能，函数int topologicalsort(algraph g , int topo[])获取拓扑序列。

相关问题

存入度得函数FindInDegree(G,indegree)

存入度函数 FindInDegree(G,indegree) 是一个用于计算有向图中每个节点的入度的函数。其中，G 是一个有向图，indegree 是一个字典，用于存储每个节点的入度。

代码实现如下：

def FindInDegree(G, indegree):
    for u in G:
        indegree[u] = 0
    for u in G:
        for v in G[u]:
            indegree[v] += 1

其中，第一个循环用于初始化 indegree 字典，将每个节点的入度初始化为 0。第二个循环遍历有向图中的每个节点 u，然后遍历与节点 u 相连的节点 v，将节点 v 的入度加 1。

使用示例：

G = {0: [1, 2], 1: [3], 2: [3], 3: []}
indegree = {}
FindInDegree(G, indegree)
print(indegree)  # 输出: {0: 0, 1: 1, 2: 1, 3: 2}

在这个例子中，有向图 G 有 4 个节点，其中节点 0 指向节点 1 和节点 2，节点 1 指向节点 3，节点 2 也指向节点 3，节点 3 没有出边。使用 FindInDegree 函数计算每个节点的入度，得到结果为 {0: 0, 1: 1, 2: 1, 3: 2}。

用c语言写 拓扑排序 功能描述：通过调用FindInDegree计算各顶点的入度并存入本地变量数组，顺序查找度为0的顶点，作为起始点，通过栈操作完成拓扑排序，打印节点printf("%s ", 课程名); 如果该图有回路则打印printf("该图有回路"); 参数说明：G-ALGraph型参数 返回值说明：无

好的，下面是用C语言实现拓扑排序的代码，注意其中的注释：

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

#define MAX_VERTEX_NUM 20  // 最大顶点数

typedef struct ArcNode {  // 定义边节点结构体
    int adjvex;           // 邻接点下标
    struct ArcNode *nextarc;  // 指向下一条边的指针
} ArcNode;

typedef struct VNode {      // 定义顶点节点结构体
    char data[10];         // 课程名称
    int inDegree;          // 入度
    ArcNode *firstarc;     // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {            // 定义邻接表结构体
    AdjList vertices;      // 顶点数组
    int vexnum, arcnum;    // 顶点数和边数
} ALGraph;

int LocateVex(ALGraph G, char *e) {  // 查找元素在数组中的位置
    int i;
    for (i = 0; i < G.vexnum; ++i) {
        if (strcmp(G.vertices[i].data, e) == 0) {
            return i;
        }
    }
    return -1;
}

void CreateUDG(ALGraph *G, char *vexs[], int vlen, char *edges[][2], int elen) {
    int i, j, p1, p2;
    ArcNode *arc;

    G->vexnum = vlen;  // 顶点数
    G->arcnum = elen;  // 边数

    for (i = 0; i < G->vexnum; ++i) {
        G->vertices[i].inDegree = 0;  // 初始化每个顶点的入度为0
        G->vertices[i].firstarc = NULL;  // 初始化每个顶点的邻接表为空
        strcpy(G->vertices[i].data, vexs[i]);  // 给每个顶点赋值
    }

    for (i = 0; i < G->arcnum; ++i) {  // 构建邻接表
        p1 = LocateVex(*G, edges[i][0]);  // 找到边的起点在数组中的位置
        p2 = LocateVex(*G, edges[i][1]);  // 找到边的终点在数组中的位置

        arc = (ArcNode *) malloc(sizeof(ArcNode));  // 创建边节点
        arc->adjvex = p2;  // 存储终点下标
        arc->nextarc = G->vertices[p1].firstarc;  // 将新边节点插入到起点的邻接表头部
        G->vertices[p1].firstarc = arc;  // 更新起点的邻接表头指针

        ++G->vertices[p2].inDegree;  // 终点入读+1
    }
}

int FindInDegree(ALGraph G, int indegree[]) {  // 计算每个顶点的入度
    int i;
    for (i = 0; i < G.vexnum; ++i) {
        indegree[i] = G.vertices[i].inDegree;
    }
}

void TopologicalSort(ALGraph G) {
    int i, j, k, m, n;
    int indegree[MAX_VERTEX_NUM];
    int stack[MAX_VERTEX_NUM], top = -1;  // 初始化栈顶指针为-1
    ArcNode *p;

    FindInDegree(G, indegree);  // 计算每个顶点的入度

    for (i = 0; i < G.vexnum; ++i) {  // 将入度为0的顶点入栈
        if (indegree[i] == 0) {
            stack[++top] = i;
        }
    }

    while (top != -1) {  // 栈不为空时循环
        j = stack[top--];  // 将栈顶元素出栈
        printf("%s ", G.vertices[j].data);  // 打印节点
        p = G.vertices[j].firstarc;
        while (p) {  // 将与该节点相邻的顶点的入度减1
            k = p->adjvex;
            if (--indegree[k] == 0) {  // 若入度为0则入栈
                stack[++top] = k;
            }
            p = p->nextarc;
        }
    }

    for (i = 0; i < G.vexnum; ++i) {  // 检查是否有回路
        if (indegree[i] > 0) {
            printf("该图有回路");
            break;
        }
    }
}

int main() {
    ALGraph G;
    char *vexs[] = {"数学", "英语", "物理", "化学", "生物"};
    char *edges[][2] = {
        {"数学", "物理"},
        {"英语", "数学"},
        {"英语", "化学"},
        {"物理", "化学"},
        {"物理", "生物"},
        {"化学", "生物"}
    };

    CreateUDG(&G, vexs, 5, edges, 6);
    TopologicalSort(G);

    return 0;
}

这里我使用了邻接表来存储图，并且在顶点结构体中增加了一个 `inDegree` 属性来记录每个顶点的入度。在计算完每个顶点的入度后，将入度为0的顶点入栈，然后从栈顶依次出栈并打印节点，将与该节点相邻的顶点的入度减1，若入度为0则入栈。最后检查是否有入度大于0的顶点，如果有则说明图中存在回路。