拓扑排序

我们会把施工过程、生产流程、软件开发、教学安排等都当成一个项目工程来对待，所有的工程都可分为若干个活动的子工程。由这而来的图首先一定是一个无环图。而之前学习的最短路径问题和最小生成树问题是关于有环图的。

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系。这样的有向图为顶点表示活动的网，我们成为AOV网(Activity On Vertex Network )。AOV网中的弧表示活动之间存在某种制约关系，比如在学习数据结构这门课之前必须先学习C语言等等。这个场景在我们生活中很常见。

拓扑排序的算法实现非常的简单，大体的思路就是用一个栈来存放所有入度为0的顶点，循环每次弹出栈顶入度为0的顶点并输出，然后更新它的邻接顶点的入度-1，如果它的邻接顶点更新后的入度为0就把它压入栈，循环往复，直到栈为空。倘若输出顶点数量<实际的顶点数量就表明图是一个有环的图，算法失败。因此也可以用该算法来判断图是否有环。

对于此算法，我们用邻接表会更方便一点。

/*
邻接表结点结构: in(入度) data(顶点) firstEdge(第一个邻接点)
*/
#include <stdlib.h>
#include <stdio.h>
#define OK 1
#define ERROR 0
#define Status int
typedef struct EdgeNode 
{
    int adjvex;/*邻接点域*/
    int weight;/*权值*/
    struct EdgeNode *next;
}EdgeNode;

typedef struct VertexNode
{
    int in; /*入度*/
    int data;
    EdgeNode *firstEdge;
}VertexNode, AdjvexList[MAXVEX];

typedef struct 
{
    AdjvexList adjList;
    int numVertexes, numEdges;
}*GraphAdjList, graphAdjList;

Status TopologicalSort(GraphAdjList G)
{
    EdgeNode *e;
    int count;/*计数器：如果输出顶点数小于实际顶点数说明有环，拓扑排序则失败。反之则成功*/
    int getTop, i, k;/*getTop,临时存放栈顶弹出的值*/
    int *stack; /*初始化一个栈，用以存放入度为0的顶点*/
    int top; /*栈顶指针*/
    count = 0; top = 0;
    stack = (int *) malloc (sizeof(int) * G->numVertexes + 1); /*0 is not used*/
    for(i = 0; i < G->numVertexes; i++)
    {
        /*初始化遍历每个顶点，如果其入度为0则入。*/
        if(G->adjList[i].in == 0)
        {
            stack[++top] = i;
        }
    }
    while(top != 0)
    {
        /*栈不为空时，循环输出度为0的点，并且随时更新对应顶点的入度*/
        getTop = stack[top--];
        printf("%d->", G->adjList[getTop]);
        count++;/*输出从栈中 取出的度为0的顶点，打印他的值,顶点计数器+1*/
        for(e = G->adjList[i].firstEdge; e; e = e->next)
        {
            k = e->adjvex; /*取的相邻顶点的下标*/
            if(!(--G->adjList[k].in))
            {
                /*先更新相邻顶点的入度，因为刚刚他的前驱顶点度为0被输出了，所以它的度-1，然后判断时候它的度也是0，如果是0的话则入栈*/
                stack[++top] = k;
            }
        }
    }
    if(count != G->numVertexes)
    {
        return ERROR;
    }else
    {
        return OK;
    }
}