生成一个带“入度”域的图，邻接表存储。写一个拓扑排序算法

以下是生成带“入度”域的图并实现拓扑排序的C语言代码：

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

#define MAX_VERTEX_NUM 20   // 最大顶点数

// 定义邻接表节点结构体
typedef struct ArcNode {
    int adjvex;             // 该边所指向的顶点的位置
    struct ArcNode *next;   // 指向下一条边的指针
} ArcNode;

// 定义顶点信息结构体
typedef struct {
    char data;              // 顶点数据
    int indegree;           // 顶点入度
    ArcNode *firstarc;      // 指向第一个依附该顶点的边的指针
} VNode;

// 定义邻接表结构体
typedef struct {
    VNode vertices[MAX_VERTEX_NUM];    // 存放顶点信息的数组
    int vexnum, arcnum;                 // 顶点数和边数
} ALGraph;

// 初始化邻接表
void InitALGraph(ALGraph *G) {
    int i;
    G->vexnum = 0;
    G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].firstarc = NULL;
        G->vertices[i].indegree = 0;
    }
}

// 添加边
void AddArc(ALGraph *G, int start, int end) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = end;
    p->next = G->vertices[start].firstarc;
    G->vertices[start].firstarc = p;
    G->vertices[end].indegree++;    // 相应顶点入度加1
    G->arcnum++;
}

// 拓扑排序
int TopoSort(ALGraph *G) {
    int i, j, k, count = 0;
    int result[MAX_VERTEX_NUM];     // 存放拓扑排序结果的数组
    ArcNode *p;
    for (i = 0; i < G->vexnum; i++) {   // 将所有入度为0的顶点入队
        if (G->vertices[i].indegree == 0) {
            result[count++] = i;
        }
    }
    for (i = 0; i < count; i++) {   // 依次输出队首顶点，并将该顶点的所有邻接点的入度减1
        j = result[i];
        printf("%c ", G->vertices[j].data);
        for (p = G->vertices[j].firstarc; p; p = p->next) {
            k = p->adjvex;
            if (--G->vertices[k].indegree == 0) {
                result[count++] = k;
            }
        }
    }
    if (count < G->vexnum) {    // 如果输出的顶点数少于总顶点数，则说明存在环，拓扑排序失败
        return 0;
    } else {
        return 1;
    }
}

// 测试代码
int main() {
    ALGraph G;
    InitALGraph(&G);
    G.vexnum = 6;
    G.arcnum = 8;
    G.vertices[0].data = 'A';   // 添加顶点数据和入度
    G.vertices[1].data = 'B';
    G.vertices[2].data = 'C';
    G.vertices[3].data = 'D';
    G.vertices[4].data = 'E';
    G.vertices[5].data = 'F';
    AddArc(&G, 0, 1);   // 添加边
    AddArc(&G, 0, 3);
    AddArc(&G, 1, 2);
    AddArc(&G, 1, 3);
    AddArc(&G, 3, 2);
    AddArc(&G, 3, 4);
    AddArc(&G, 2, 5);
    AddArc(&G, 4, 5);
    if (TopoSort(&G)) { // 执行拓扑排序
        printf("\n拓扑排序成功\n");
    } else {
        printf("\n拓扑排序失败，存在环\n");
    }
    return 0;
}

在上述代码中，我们定义了一个邻接表结构体`ALGraph`，其中`vertices`数组存放顶点信息，`vexnum`表示顶点数，`arcnum`表示边数。我们用`AddArc`函数向邻接表中添加边，用`TopoSort`函数进行拓扑排序。在测试代码中，我们添加了一些边，并且执行了拓扑排序。如果拓扑排序成功，则输出拓扑排序结果，否则说明存在环，拓扑排序失败。