C语言AOV网，拓扑排序完整算法实现

将入度为 0 的顶点压栈，如图 (b) 所示；
取栈顶元素 C4，输出 C4，删除 C4 和所有以它为始点的弧 e3、e4、C3 的入度减 1，C5 的入度减 1，C5 的入度变为 0，C5 入栈，如图 (c) 所示；
取栈顶元素 C5，输出 C5，删除 C5 和所有以它为始点的弧 e7，C6 入度减 1，如图 (d) 所示；
取栈顶元素 C1，输出 C1，删除 C1 和所有以它为始点的弧 e1，e2，C2的入度减 1，C2 的入度变为 0，C2 入栈，C3 的入度减1，C3 的入度变为 0，C3 入栈，如图(e)所示；
取栈顶元素 C3，输出 C3，删除 C3 和所有以它为始点的弧 e6，C6 的入度减 1，如图 (f) 所示；
取栈顶元素 C2，输出 C2，删除 C2 和所有以它为始点的弧 e5，C6 的入度减 1，C6 的入度为 0，C6 入栈，如图（g）所示；
取栈顶元素 C6，输出 C62，删除 C6，没有以它为始点的弧，栈空，如图（h）所示；
栈空，算法结束，拓扑序列为：C4，C5，C1，C3，C2，C6。

3.源代码示例

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

#define MAX_VERTEX_NUM 100 // 有向图中最大节点数
typedef char VexType;      // 定义节点名为char型
typedef struct node        // 弧表节点
{
    VexType adjvex;    // 与顶点相连的邻接点下标(adjoin：邻接)
    struct node *next; // 指向顶点的下一个邻接点
} EdgeNode;

typedef struct vnode // 顶点结构
{
    int ID;              // 顶点入度( in-degree )
    VexType vex;         // 存储顶点名
    EdgeNode *firstedge; // 弧表头指针，指向顶点第一个邻接点
} VexNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList adjlist; // 描述有向图结构的邻接表
    int vexnum;      // 节点的数目
    int edgenum;     // 弧的数目
} ALGraph;           // adjacency list：邻接表

void CreateDG(ALGraph *DG);       // 邻接表法创建有向图
void TraverseDG(ALGraph DG);      // 遍历有向图DG
void TopologicalSort(ALGraph DG); // 对有向图DG拓扑排序
void LocateVex(ALGraph DG, VexType vex, int *index);
// 若有向图DG中存在节点vex，则将该下标赋给index

int main(void)
{
    ALGraph g;

    CreateDG(&g);
    printf("------------------------------\n");
    printf("vexnum = %d ; edgenum = %d\n", g.vexnum, g.edgenum);
    printf("------------------------------\n");
    TraverseDG(g);
    printf("------------------------------\n");
    TopologicalSort(g);

    return 0;
}
void CreateDG(ALGraph *DG)
{
    VexType ch;
    int i = 0;
    int start, end; // start:弧尾下标；end:弧头下标
    EdgeNode *temp;

    printf("请输入有向图的顶点数、弧数：");
    scanf("%d%d", &(DG->vexnum), &(DG->edgenum));

    printf("请输入有向图的顶点：");
    getchar();
    while ((ch = getchar()) != '\n') // 建立顶点表
    {
        DG->adjlist[i].vex = ch;
        DG->adjlist[i].firstedge = NULL;
        DG->adjlist[i].ID = 0;
        i++;
    }

    printf("顶点 | 下标\n");
    for (i = 0; i < DG->vexnum; i++) // 显示有向图中顶点及其对应下标
        printf("%3c%6d\n", DG->adjlist[i].vex, i);

    printf("请依次输入每条弧的弧尾下标、弧头下标：\n");
    for (i = 0; i < DG->edgenum; i++) // 头插法建立顶点的邻接弧表
    {
        scanf("\n%d%d", &start, &end);
        while (start < 0 || start > (DG->vexnum - 1) || end < 0 ||
               end > (DG->vexnum - 1)) {
            printf("下标越界，重新输入：");
            scanf("\n%d%d", &start, &end);
        }

        temp = (EdgeNode *)malloc(sizeof(EdgeNode));
        temp->adjvex = DG->adjlist[end].vex;
        temp->next = DG->adjlist[start].firstedge;
        DG->adjlist[start].firstedge = temp;
        DG->adjlist[end].ID++;
    }
}
void TraverseDG(ALGraph DG)
{
    int i;
    EdgeNode *temp;

    if (DG.vexnum == 0) {
        printf("有向图为空\n");
        return;
    }

    for (i = 0; i < DG.vexnum; i++) // 遍历有向图
    {
        printf("顶点 %c ( ID = %d ) ：", DG.adjlist[i].vex, DG.adjlist[i].ID);
        temp = DG.adjlist[i].firstedge;
        while (temp) // 输出有向图的信息
        {
            printf("[ %c ] -> ", temp->adjvex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}
void TopologicalSort(ALGraph DG)
{
    int i, j, k, m = 0, top; // top：栈顶入度为 0 的顶点下标
    EdgeNode *temp;

    top = -1;
    for (i = 0; i < DG.vexnum; i++) // 让初始情况下入度为0的顶点入栈
        if (DG.adjlist[i].ID == 0) {
            DG.adjlist[i].ID =
                top; // 用入度为0的新顶点的ID存储旧入度为0的顶点下标
            top = i; // top始终指向栈顶入度为0的顶点下标
        }

    printf("有向图的拓扑序列为：");
    while (top != -1) {
        j = top;                  // 栈顶顶点下标赋给j
        top = DG.adjlist[top].ID; // 输出栈顶节点后，top下移，指向新的栈顶节点
        printf("%c, ", DG.adjlist[j].vex); // 输出栈顶节点
        m++;
        temp = DG.adjlist[j].firstedge;

        while (temp != NULL) // 遍历顶点所有邻接点
        {
            LocateVex(DG, temp->adjvex, &k);
            DG.adjlist[k].ID--;
            if (DG.adjlist[k].ID == 0) {
                DG.adjlist[k].ID =
                    top; // 用入度为0的新顶点的ID存储旧入度为0的顶点下标
                top = k; // top始终指向栈顶入度为0的顶点下标
            }
            temp = temp->next;
        }
    }

    if (m < DG.vexnum) // 若输出顶点数小于总顶点数，网中有环
        printf("网中有环！\n");
}
void LocateVex(ALGraph DG, VexType vex, int *index)
{
    int i;

    for (i = 0; i < DG.vexnum; i++) {
        if (DG.adjlist[i].vex == vex) {
            *index = i;
            return;
        }
    }
    printf("该节点不存在！\n");
}

原文链接：https://blog.csdn.net/weixin_42250302/article/details/89716519