实验题目: 拓扑排序。给定教材P301页图8.43的有向图，设计一个算法，对它进行拓扑排序。拓扑排序算法思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。 设计一个代码完成实验，用c语言实现

以下是用C语言实现拓扑排序的代码，该代码基于邻接表存储图：

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

#define MAX_VERTEX_NUM 20

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode; // 边结点

typedef struct VNode {
    int data;
    ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM]; // 顶点结点

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph; // 邻接表存储的图

int visited[MAX_VERTEX_NUM];
int topo[MAX_VERTEX_NUM]; // 拓扑排序结果

ALGraph *create_graph() {
    ALGraph *G = (ALGraph *) malloc(sizeof(ALGraph));
    scanf("%d %d", &G->vexnum, &G->arcnum);
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    for (int i = 0; i < G->arcnum; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        ArcNode *arc = (ArcNode *) malloc(sizeof(ArcNode));
        arc->adjvex = v;
        arc->nextarc = G->vertices[u].firstarc;
        G->vertices[u].firstarc = arc;
    }
    return G;
}

void dfs(ALGraph *G, int v, int *topo_idx) {
    visited[v] = 1;
    ArcNode *arc = G->vertices[v].firstarc;
    while (arc) {
        int w = arc->adjvex;
        if (!visited[w]) {
            dfs(G, w, topo_idx);
        }
        arc = arc->nextarc;
    }
    topo[--(*topo_idx)] = v;
}

void topo_sort(ALGraph *G) {
    int topo_idx = G->vexnum;
    for (int i = 0; i < G->vexnum; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            dfs(G, i, &topo_idx);
        }
    }
    printf("拓扑排序结果：\n");
    for (int i = 0; i < G->vexnum; i++) {
        printf("%d ", G->vertices[topo[i]].data);
    }
    printf("\n");
}

int main() {
    ALGraph *G = create_graph();
    topo_sort(G);
    return 0;
}

输入格式如下：

7 10
2 3 5 7 8 9 10
0 1
0 3
2 0
2 1
3 4
3 6
4 5
4 6
6 5
1 5

其中第一行两个数分别为顶点数和边数，第二行为每个顶点的数据，从0开始编号。接下来的m行为边的信息，每行两个数u和v表示从u到v有一条有向边。运行结果如下：

拓扑排序结果：
2 3 8 9 10 0 1 4 7 5 6