拓扑排序

1、在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为AOV网。

2、设G = (V,E)是一个具有n个顶点的有向图，V中的顶点序列v1，v2，.......，vn，满足若从顶点vi到vj有一条路径，则在顶点序列中vi必在顶点vj之前，则我们称这样的顶点序列为一个拓扑序列。

3、所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都输出，则说明它是不存在环（回路）的AOV网；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环（回路），不是AOV网。

4、对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删除此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或AOV网中不存在入度为0的顶点为止。

    拓扑排序设计的结构代码如下所示。

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

typedef struct VertexNode //顶点表结点
{
    int in;                    //顶点入度
    int data;                //顶点域，存储顶点信息
    EdgeNode *firstedge;    //边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes, numEdges;    //图中当前顶点数和边数
}graphAdjList, *GraphAdjList;

    在算法中，我还需要辅助的数据结构一栈，用来存储处理过程中入度为0的顶点，目的是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点。
    现在看代码，并且进行模拟它。

//拓扑排序，若GL无回路，则输出拓扑排序序列并返回OK，若有回路，返回ERROR
status TopologicalSort(GraphAdjList GL)
{
    EdgeNode *e;
    int i, k, gettop;
    int top = 0;    //用于栈指针下标
    int count = 0; //用于统计输出顶点的个数
    int *stack; //建栈存储入度为0的顶点

    stack = (int *)malloc(GL->numVertexes * sizeof(int) );
    for(i = 0; i < GL->numVertexes; i++)
    {
        if(GL->adjList[i].in == 0)
        {
            stack[++top] = i; //将入度为0的顶点入栈
        }
    }

    while(top != 0)
    {
        gettop = stack[top--]; // 出栈
        printf("%d -> ", GL->adjList[gettop].data); //打印此结点
        count++;

        for(e = GL->adjList[gettop].firstedge; e; e = e->next)
        {
            //对此顶点弧表遍历
            k = e->adjvex;
            if(!(--GL->adjList[k].in) )
            {
                //将k号顶点邻接点的入度减1
                stack[++top] = k; //若为0，则入栈，以便于下次循环输出
            }
        }
    }

    if(count < GL->numVertexes)    //如果count小于顶点数，说明存在环
    {
        return ERROR;
    }
    else
    {
        return OK;
    }
}