小编Str*_*ord的帖子

我必须开发一个与拓扑排序相关的O(| V | + | E |)算法,它在有向无环图(DAG)中确定从图的每个顶点到t的路径数(t是一个节点) out-degree 0).我已经开发了DFS的修改如下:

DFS(G,t):
    for each vertex u ? V do
        color(u) = WHITE
        paths_to_t(u) = 0
    for each vertex u ? V do
        if color(u) == WHITE then
            DFS-Visit(u,t)

DFS-Visit(u,t):
    color(u) = GREY
    for each v ? neighbors(u) do
        if v == t then
            paths_to_t(u) = paths_to_t(u) + 1
        else then
            if color(v) == WHITE then
                DFS-Visit(v)
            paths_to_t(u) = paths_to_t(u) + paths_to_t(v)
    color(u) = BLACK

但我不确定这个算法是否与拓扑排序有关,或者我是否应该以另一种观点重构我的工作.