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

    首先我们需要确定一下这个图需要使用的数据结构。前面求最小生成树和最短路径时，我们用的都是邻接矩阵，但由于拓扑排序的过程中，需要删除顶点，显然用邻接表会更加方便。因此我们需要为AOV网建立一个邻接表。考虑到算法过程中始终要查找入度为0的顶点，我们在原来顶点表结点结构中，增加一个入度域in，结构如表7-8-1所示，其中in就是入度的数字。

    in data firstedge

    因此对于图7-8-2的第一幅图AOV网，我们可以得到如第二幅图的邻接表数据结构。
    image.png
    在拓扑排序算法中，涉及的结构代码如下。

    1. /* 边表结点 */
    2. typedef struct EdgeNode{
    4.     /* 邻接点域，存储该顶点对应的下标 */
    5.     int adjvex;
    7.     /* 用于存储权值，对于非网图可以不需要 */
    8.     int weight;
    10.     /* 链域，指向下一个邻接点 */
    11.     struct EdgeNode *next;
    12. } EdgeNode;
    14. /* 顶点表结点 */
    15. typedef struct VertexNode{
    17.     /* 顶点入度*/
    18.     int in;
    20.     /* 顶点域，存储顶点信息 */
    21.     int data;
    23.     /* 边表头指针 */
    24.     EdgeNode *firstedge;
    25. } VertexNode, AdjList[MAXVEX];
    27. typedef struct{
    29.     AdjList adjList;
    31.     /* 图中当前顶点数和边数 */
    32.     int numVertexes,numEdges;
    33. } graphAdjList, *GraphAdjList;

    在算法中，我还需要辅助的数据结构—栈，用来存储处理过程中入度为0的顶点，目的是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点。

    现在我们来看代码，并且模拟运行它。

    1. /* 拓扑排序，若GL无回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR */
    2. Status TopologicalSort(GraphAdjList GL){
    4.     EdgeNode *e;
    6.     int i, k, gettop;
    8.     /* 用于栈指针下标 */
    9.     int top = 0;
    10.     /* 用于统计输出顶点的个数 */
    11.     int count = 0;
    12.     /* 建栈存储入度为0的顶点 */
    13.     int *stack;
    15.     stack = (int *)malloc(GL->numVertexes * sizeof(int));
    17.     for (i = 0; i < GL->numVertexes; i++)
    18.         if (GL->adjList[i].in == 0)
    19.             /* 将入度为0的顶点入栈 */
    20.             stack[++top] = i;
    22.     while (top != 0){
    24.         /* 出栈 */
    25.         gettop = stack[top--];
    26.         /* 打印此顶点 */
    27.         printf("%d -> ", GL->adjList[gettop].data);
    28.         /* 统计输出顶点数 */
    29.         count++;
    31.         /* 对此顶点弧表遍历 */
    32.         for (e = GL->adjList[gettop].firstedge; e; e = e->next){
    34.             k = e->adjvex;
    36.             /* 将k号顶点邻接点的入度减1 */
    37.             if (!(--GL->adjList[k].in))
    38.                 /*若为0则入栈，以便于下次循环输出 */
    39.                 stack[++top] = k;
    40.         }
    41.     }
    43.     /*如果count小于顶点数，说明存在环 */
    44.     if (count < GL->numVertexes)
    45.         return ERROR;
    46.     else
    47.         return OK;
    48. }
    1. 程序开始运行，第3～7行都是变量的定义，其中stack是一个栈，用来存储整型的数字。
    2. 第8～10行，作了一个循环判断，把入度为0的顶点下标都入栈，从图7-8-3的右图邻接表可知，此时stack应该为：{0,1,3}，即v0 、v1 、v3的顶点入度为0，如图7-8-3所示。

    image.png

    1. 第12～23行，while循环，当栈中有数据元素时，始终循环。
    2. 第14～16行，v 3 出栈得到gettop=3。并打印此顶点，然后count加1。
    3. 第17～22行，循环其实是对v 3 顶点对应的弧链表进行遍历，即图7-8-4中的灰色部分，找到v 3 连接的两个顶点v 2 和v 13 ，并将它们的入度减少一位，此时v 2 和v 13 的in值都为1。它的目的是为了将v 3 顶点上的弧删除。

    image.png

    1. 再次循环，第12～23行。此时处理的是顶点v 1 。经过出栈、打印、count=2后，我们对v 1 到v 2 、v 4 、v 8 的弧进行了遍历。并同样减少了它们的入度数，此时v 2 入度为0，于是由第20～21行知，v 2 入栈，如图7-8-5所示。试想，如果没有在顶点表中加入in这个入度数据域，20行的判断就必须要是循环，这显然是要消耗时间的，我们利用空间换取了时间。

    image.png

    1. 接下来，就是同样的处理方式了。图7-8-6展示了v 2 v 6 v 0 v 4 v 5 v 8 的打印删除过程，后面还剩几个顶点都类似，就不图示了。

    image.png

    1. 最终拓扑排序打印结果为3->1->2->6->0->4->5->8->7->12->9->10->13->11。当然这结果并不是唯一的一种拓扑排序方案。

    分析整个算法，对一个具有n个顶点e条弧的AOV网来说，第8～10行扫描顶点表，将入度为0的顶点入栈的时间复杂为O(n)，而之后的while循环中，每个顶点进一次栈，出一次栈，入度减1的操作共执行了e次，所以整个算法的时间复杂度为O(n+e)。