拓扑排序的基本思想为：从有向图中选一个无前驱的节点输出，然后删去此顶点，并删除以此结点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。若此时输出的结点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。

若要算法实现拓扑排序，因为要删除顶点，所以用邻接表存储比较方便。入度为零的顶点即没有前趋的顶点，因此我们可以附设一个存放各顶点入度的数组indegree［］，于是有：

①找G中无前驱的顶点——查找indegree［i］为零的顶点i；

②删除以i为起点的所有弧——对链在顶点i后面的所有邻接顶点k，将对应的indegree［k］减1。

为了避免重复检测入度为零的顶点，可以再设置一个辅助栈，若某一顶点的入度减为0，则将它入栈。每当输出某一顶点时，便将它从栈中删除。

算法的实现如下。

算法7.7 求拓扑排序算法

若有向无环图有n个顶点和e条弧，则在拓扑排序的算法中，FOR循环需要执行n次，时间复杂度为O（n）；对于WHILE循环，由于每一顶点必定进一次栈，出一次栈，其时间复杂度为O（e）；故该算法的时间复杂度为O（n＋e）。