Aaaaaa

栈先入后出

首先说下这个拓扑有序，说明这个图得到的拓扑唯一。如上面这个图的拓扑就是一个有序的。
言归正传：首先这个有向无环图的深度遍历得到的序列是不唯一的。比如从ABCD、ABDC、CBDA等这些都是这些。但是他们退栈确实相同的。A入栈然后看A有那个可以到达的访问B，然后查看B有没有哪个可以到达的访问。有D。看D还有没有哪个可以到达的访问。没有。D出站，看看B有没有哪个除了D可以访问的。没有退栈B。查看A还有没有除了B其他的访问的。有C，C入栈，看看C没有哪个除了BD可以访问的，没有退栈C，所以A还有没有除了BC可以到达的，没有退栈A。最后退栈的序列就是DBCA。同理可以验证其他几个最后退栈的序列都会DBCA。然后这个有向图的拓扑序列是ACBD。所以说这哥深度优先遍历算法中退栈次序是逆拓扑有序。