数据结构

拓扑排序，是对有向无环图的顶点的一种排序，使得各个顶点之间有序

入度：指向该顶点的边数量
如下图，顶点D的入度有两条，则顶点D的入度 = 2

拓扑排序需要借助一个栈Stack存储入度为零的顶点
（1）获取所有顶点的入度，初始化栈Stack，入栈入度为0的顶点

（2）出栈栈顶 顶点A，并遍历出栈顶点A所有的连接的尾顶点，并使这些尾顶点的入度减一，相当于剔除掉了栈顶顶点
同时判断入度减一后的尾顶点中，若存在入度为0的顶点，则将其入栈

（3）通过while循环获取栈顶元素来依次提取入度为0的顶点，从而完成拓扑排序

#include
#include
#define MaxVex 20

typedef int EdgeType;
typedef char VertexType;

// 边结点结构（链表）
typedef struct EdgeNode
{
    int adjvex;         // 该边邻接的结点下标
    EdgeType edgeData;  // 该边结点的数据（权值）
    struct EdgeNode *next;
}EdgeNode, *EdgeList;

// 顶点结点结构（顺序表）
typedef struct
{
    VertexType vextexData;  // 顶点数据
    EdgeList edgeList;      // 顶点的边链表 
    int indegree;           // 顶点的入度
}VertexNode, *VertexList;

// 邻接表结构
typedef struct
{
    VertexList vertexList; // 顶点顺序表
    int numVertexs, numEdges;     // 顶点数
}ALGraph;

// 初始化邻接表
void InitALGraph(ALGraph *G)
{

    G->numVertexs = 0;
    G->numEdges = 0;
    G->vertexList = (VertexNode *)malloc(MaxVex * sizeof(VertexNode));
    
    // 初始化边链表头结点，和顶点入度
    int i;
    for (i = 0; i < MaxVex; i++)
    {
        G->vertexList[i].edgeList = (EdgeNode *)malloc(sizeof(EdgeNode));
        G->vertexList[i].edgeList->next = NULL;
        G->vertexList[i].indegree = 0;
    }
    printf("已初始化邻接表nn");
}

// 创建邻接表
void CreateALGraph(ALGraph *G)
{
    printf("请输入顶点数和边数:");
    scanf("%d %d", &G->numVertexs, &G->numEdges);
    
    int i, j, k;
    EdgeType w;
    // 输入顶点数据
    for (i = 0; i < G->numVertexs; i++)
    {
        fflush(stdin);
        printf("请输入第%d个顶点数据:", i + 1);
        scanf("%c", &G->vertexList[i].vextexData);
    }
    // 输入边的权值
    for (k = 0; k < G->numEdges; k++)
    {
        printf("请输入边(vi, vj)上的顶点序号及权值:");
        scanf("%d %d %d", &i, &j, &w);

        EdgeNode *p1;
        p1 = (EdgeNode *)malloc(sizeof(EdgeNode));

        // 链表头插法 插入 顶点（vi -> vj）的边
        p1->edgeData = w;
        p1->next = G->vertexList[i - 1].edgeList->next;
        G->vertexList[i - 1].edgeList->next = p1;
        p1->adjvex = j - 1;                 // 该边邻接着顶点j
        G->vertexList[j - 1].indegree++;    // 邻接顶点j的入度加一
    }
    printf("已创建邻接表!nn");
}

void TopoSort(ALGraph G)
{
    // 用一个数组来代表一个栈结构，top为栈顶指针
    int top = 0;
    EdgeType Stack[MaxVex];

    int i, indegree[MaxVex];
    for (i = 0; i < G.numVertexs; i++)
    {
        // 获取每个顶点的入度
        indegree[i] = G.vertexList[i].indegree;
        // 初始化栈，将入度为0的顶点入栈
        if (indegree[i] == 0)
        {
            Stack[top++] = i;
        }
    }

    EdgeNode *p;
    int v, count = 0;
    while (top > 0)
    {
        // 将入度为0的顶点出栈
        i = Stack[--top];
        printf("%c--->", G.vertexList[i].vextexData);
        // 用于记录成功输出的顶点数
        count++;
        // 遍历该顶点所有的尾顶点（邻接顶点）
        for (p = G.vertexList[i].edgeList->next; p ; p = p->next)
        {
            v = p->adjvex;
            // 将尾顶点的入度减一
            indegree[v]--;
            // 如果尾顶点入度为零，则入栈
            if (!indegree[v])
            {
                Stack[top++] = v;
            }
        }
    }   
    printf("n");
    // 存在回路的情况
    if (count < G.numVertexs)
    {
        printf("排序失败!存在回路n");
    }
}

int main()
{
    ALGraph G;
    InitALGraph(&G);
    CreateALGraph(&G);
    TopoSort(G);
    system("pause");
    return 0;
}

#测试用例
5 7
A
B
C
D
E
1 2 10
1 4 20
2 3 30
2 4 40
3 5 50
4 3 60
4 5 70