一、拓扑排序思路

①从从网中找到入度为0的点，输出并保存。
②从网中删除该点。
③不断重复①、②步骤

二、预先设定：

1、如何存储？

邻接表。邻接矩阵其实也可以。

2、如何找到入度为0的点？

建立一个count数组，记录各个点的入度。
通过扫描count数组就可以找到入度为0的点。
但是，没有必要每次都扫描所有点。当v被删去时，仅仅需要扫描v邻接的点。

3、如何保存入度为0的点？

课本给了一种巧妙的方式：利用模拟栈。
建立方法：

初始状态，设定栈顶指针为-1.
扫描counti，当count[i] = 0时，count[i]赋值成top，top赋值为i。此时i便成了栈顶，且count[i]记录了上一个入栈元素的下标。

由于模拟栈是直接建立在count数组上的，需要考虑：
模拟栈会不会受到删点操作的干扰？
不会，入栈的元素不会是任何边的终点。

模拟栈会不会干扰入度的判断？

由于0号元素也可能入栈，会不会栈中的“0”会被误认为是入度为0的点？

答：那就…0号位不存结点

算法 TopoOrder(Head,n)
/*拓扑排序，n为结点个数*/
TopoOrder 1.[初始化]
    FOR i = 1 TO n DO count[i] = 0.
    FOR i = 1 TO n DO {
        p = adjacent(Head[i]).
        WHILE p ≠ NULL DO{
            count[VerAdj(p)] = count[VerAdj(p)] + 1.
            p = link(p). 
        }

    }
TopoOrder 2.[排序]
    FOR i = 1 TO n DO{//每次循环都会收录一个元素，故循环n次
        IF top = -1 THEN{
            PRINT("There is a cycle in network").
            RETURN.
        }
        j = top.
        PRINT(j).//输出栈顶元素
        top = count[top].
        p = adjacent(Head[j]).
        WHILE p ≠ NULL DO{
            count[VerAdj(p)] = count[VerAdj(p)] - 1.
            IF count[VerAdj(p)] == 0 THEN{
                count[k] = top.
                top = k.
            }
            p = link(p).
        }   
    }

三、序列的改进

如上图。假如找到1号点后立即删除，2号点入度变为0，会导致2号点的拓扑序列先于3、4号点。
这样好吗？这样不好。假如可以同时访问多个点——3、4号点应该是与1号点平级的，访问次序应该先于2号点。

如何存储度为0的结点呢？应该用队列而不是栈。
代码略了因为懒🤤

拓扑排序