5.6 拓扑排序

拓扑排序就是将有向无环图（不存在回路的AOV网）的顶点以特定的先后次序排序，所谓特定的先后次序排序是使得所有有向边<u,v>的两个顶点在序列中都遵顼u在v前面。
（注：之所以是无环，是因为，环存在的话，有些顶点无法分先后）

举个例子

有向无环图

这个图的拓扑排序是，ABCD或ACBD，拓扑排序的结果可能是多种的。
但如果AOV图有环，拓扑序列是不存在的。所以，拓扑排序可以用来判断AOV图是否存在环。

两种拓扑排序算法

1. Kahn算法

本质是减治法，步骤是

1. 找到所有入度为0的的顶点
2. 这些顶点入栈
3. 出栈，输出，并删除该顶点的出边，回到第 1 步

按这个次序输出的就是拓扑序列了。

for (i = 0; i < GL->numVertexes; i++)//遍历所有顶点
    if (GL->adjList[i].in == 0)//如果入度为0，入栈
        stack[++top] = i;

while (top != 0)
{
    getTop = stack[top--]; //取出栈顶元素
    printf("%d",GL->adjList[getTop].data);

    for (e = GL->adjList[getTop].firstedge; e;  e=e->next;)
    {   //对刚刚去除的顶点的邻顶点进行处理，遍历所有邻结点
        k = e->adjVex;
        if( !(--GL->adjList[k].in))//顶点入度减 1 ，如果此时入度为0，入栈
            stack[++top] = k;
    }
}

2. 基于dfs的拓扑排序

与dfs算法本身有一定的区别，是通过dfs算法的顺序去遍历顶点，但是输出拓扑排序的时候是需要新的顺序的。

dfs的顺序，第一个顶点，第一个顶点的其中一个邻顶点，然后是不断的访问下一个邻顶点，直到没有之后，返回第一个顶点，访问其未访问过的邻顶点。

显然，这样是不符合拓扑排序的顺序的，所以，我们在使用dfs进行拓扑排序的时候，进行了修改。

此时的顺序是，dfs访问顺序，但是其访问的第一个结点是最深的结点，接着是最深结点的上一个结点，一直到第一个结点，不访问第一个结点，而是进而向第一个结点的未被访问的邻结点开始访问这一方向的最深结点。直到第一个结点的所有邻结点都被访问了，在访问第一个结点。
可递归调用dfs

注：

1. 每次访问时，并不输出，而是加入栈中。最后开始把所有元素出栈，才是真正的拓扑序列。
2. 方法二：记录每个顶点访问的次序，最后逆序输出。

void dfs(int tag)
{
    visited[tag] = 1; //标记访问过该顶点
    Vex p = GL->adjList[tag].firstedge;
    
    while( !visited[p->vex] && p)
    {
         //遍历该顶点的邻顶点，递归停止条件是没有邻顶点，或都被访问过
        dfs(p->vex);
        p = p->next;
    }

    stack[++top] = tag;
}