方法一：深度优先搜索

如果在拓扑序列中顶点u在顶点v前面，则在深度优先搜索中顶点v先访问完成。按照访问顶点的结束时间从大到小输出即为拓扑序列。

所以每个顶点在搜索过程中需要记录一个状态，用color表示，该状态有3种情况：

• 未访问：还没有搜索到这个顶点，记为WHITE；
• 访问中：搜索过这个顶点，但还没有回溯到该顶点，该顶点还有相邻顶点没有访问完成，记为GRAY；
• 访问完成：搜索过并且回溯到这个顶点，且该顶点的所有相邻顶点均已访问完成，记为BLACK。

拓扑排序过程 TOPOLOGICAL-SORT 的伪代码如下：

DFS(u, L)
    u.color = GRAY
    for each vertex v ∈ G.Adj[u]
        if v.color == WHITE
            DFS(v, L)
            if valid == FALSE
                return
            else if v.color == GRAY
                valid = FALSE
                return
    u.color = BLACK
    insert u onto the front of L

TOPOLOGICAL-SORT(G)
    let L be a new linked-list
    valid = TRUE
    for each vertex u ∈ G.V
        u.color = WHITE
    for each vertex u ∈ G.V
        if valid == TRUE
            if u.color == WHITE
                DFS(u, L)
        else break
    if valid == FALSE
        error "G has cycles"
        return
    else return L

由于深度优先搜索运行时间为O(n+e)，其它开销为常数，因此过程 TOPOLOGICAL-SORT 的运行时间为 O(n+e) 。

本题选B。

方法二：广度优先搜索

若一个顶点的所有前驱顶点均已输出到拓扑序列中，则该顶点的入度为0。重复寻找入度为0的顶点，输出该顶点并将该顶点及从该顶点发出的边从图中删除。

拓扑排序过程 TOPOLOGICAL-SORT 的伪代码如下：

TOPOLOGICAL-SORT(G)
    let L be a new linked-list
    for each vertex u ∈ G.V
        u.in-degree = 0
    for each vertex u ∈ G.V
        for each v ∈ G.Adj[u]
            v.in-degree = v.in-degree + 1
    Q = ∅
    for each vertex u ∈ G.V
        if u.in-degree == 0
            ENQUEUE(Q, u)
            insert u onto the rear of L
    while Q ≠ ∅
        u = DEQUEUE(Q)
        for each vertex v ∈ G.Adj[u]
            v.in-degree = v.in-degree - 1
            if v.in-degree == 0
                ENQUEUE(Q, v)
                insert v onto the rear of L
    for each vertex u ∈ G.V
        if u.in-degree ≠ 0
            error "G has cycles"
            return
    return L

由于广度优先搜索运行时间为O(n+e)，其它开销为常数，因此过程 TOPOLOGICAL-SORT 的运行时间为 O(n+e) 。

本题选B。