@[TOC](拓扑排序简单实现(C语言)
今天刷洛谷的图时看到好多题都要用图的拓扑排序，索性就学一把，敲一敲代码学学算法也复习一下图的具体操作和栈的使用。

拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

预备知识

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。如图3-6是一个具有三个顶点的回路，由<A,B>边可得B活动必须在A活动之后，由<B,C>边可得C活动必须在B活动之后，所以推出C活动必然在A活动之后，但由<C,A>边可得C活动必须在A活动之前，从而出现矛盾，使每一项活动都无法进行。这种情况若在程序中出现，则称为死锁或死循环，是必须避免的。
在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。
（以上来源百度）
简单说，就是把图的先后顺序排序，由先到后依次排序，其中不能存在环，最终得到的拓扑序列其实就是完成所有事，求中间所做事的顺序。

执行步骤

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

图解

1：删除1或2输出

2：删除2或3以及对应边

3：删除3或者4以及对应边

3：重复以上规则步骤

代码实现

我这里用的是图的邻接表实现的，只不过在原先图的基本操作上加入度次数统计的操作，再利用栈进行拓扑排序。
图为：

（别问，问就是灵魂画师）
目前这个图只有单个路径1 2 4 3 5 6，但是如果图中存在多条拓扑路径，那么拓扑结果不唯一。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXVEX 10
typedef char VerType;   //顶点值类型

struct EdgeNode{
    int adjvex; //邻接点域，存储该顶点对应的下标
    int weight; //用于存储权值，对于非网图可以不需要
    struct EdgeNode* next;  //下一个结点
};

struct VertexNode{
    int in; //入度
    VerType data;   //值
    struct EdgeNode* firstedge; //邻接表头指针
};

struct Graph{
    struct VertexNode vers[MAXVEX];
    int numVertexes, numEdges;  //顶点数和边数
};

/* 拓扑排序，若G没有回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR */
int  TopologicalSort(struct Graph* G){
    struct EdgeNode* e;
    int i, k, gettop;
    int top = 0;    //栈指针下标
    int count = 0;  //统计输出顶点个数
    int* stack; //存储入度为0的顶点
    stack = (int*)malloc(G->numVertexes * sizeof(int));

    for(i = 0;i<G->numVertexes;i++) //遍历所有结点
        if(G->vers[i].in == 0)
            stack[++top] = i;   //将入度为0的顶点入栈

    while(top != 0){
        gettop = stack[top--];  //出栈
        printf("%c ",G->vers[gettop].data);
        count++;    //统计输出顶点数
        for(e=G->vers[gettop].firstedge; e; e = e->next){
            //弧表遍历
            k = e->adjvex;
            if(!(--G->vers[k].in))  //将k号顶点邻接点的入度减1
                stack[++top] = k;   //若为0则入栈，以便下次循环输出
        }
    }
    if(count < G->numVertexes)  //如果count小于顶点数，说明存在环
        return 0;
    else
        return 1;
}

/* 图初始化 */
void CreateGraph(struct Graph* G){
    int i, m, n;

    printf("输入顶点数和边数：\n");
    scanf("%d %d",&G->numVertexes, &G->numEdges);
    printf("输入顶点值：\n");
    getchar();  //吃掉回车
    for(i=0;i<G->numVertexes;i++){
        //getchar();    //吃掉回车
        G->vers[i].data=getchar();
        getchar();
        //scanf("%c",&G->vers[i].data);
    }
    //初始化图头结点指针和入度值
    for(i=0;i<G->numVertexes;i++){
        G->vers[i].firstedge = NULL;
        G->vers[i].in = 0;  //入度为0
    }
    printf("输入边：\n");
    for(i=0;i<G->numEdges;i++){
        scanf("%d %d",&m, &n);
        struct EdgeNode *newNode = (struct EdgeNode*)malloc(sizeof(struct EdgeNode));
        newNode->next = G->vers[m].firstedge == NULL ? NULL : G->vers[m].firstedge;
        newNode->adjvex = n;
        G->vers[m].firstedge = newNode;
        G->vers[n].in++;    //入度+1
    }
}

int main(){

    struct Graph *G=(struct Graph*)malloc(sizeof(struct Graph)) ;
    CreateGraph(G);
    if(TopologicalSort(G)){
        printf("拓扑排序完成！\n");
    }else{
        printf("图存在环");
    }
    return 0;
}

结果如图：