拓扑排序以查找到t的路径数

Question

我必须开发一个与拓扑排序相关的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

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

Answer 1

可以使用动态编程和拓扑排序完成,如下所示:

Topological sort the vertices, let the ordered vertices be v1,v2,...,vn
create new array of size t, let it be arr
init: arr[t] = 1
for i from t-1 to 1 (descending, inclusive):
    arr[i] = 0  
    for each edge (v_i,v_j) such that i < j <= t:
         arr[i] += arr[j]

完成后,对于每个iin [1,t],arr[i]表示从中vi到的路径数vt

现在,证明上述说法很容易(与您的算法相比,我不知道它是否正确以及如何证明它),它是通过归纳完成的:

Base arr[t] == 1:,确实从t到t有一条路径,空路径.
假设:每个k范围内的声明都是正确的m < k <= t
证明:我们需要证明声明是正确的m.
让我们看看每一个边缘vm:(v_m,v_i).
因此,vt从v_m那个边缘开始的路径数量(v_m,v_i).确切地说arr[i](归纳假设).总结出边缘的所有可能性v_m,给出了从v_m到的总路径数v_t- 这正是算法所做的.
从而,arr[m] = #paths from v_m to v_t

QED

时间复杂度:
第一步(拓扑排序)需要O(V+E).
循环迭代所有边一次,所有顶点迭代一次,所以也是O(V+E)如此.
这给了我们完全的复杂性O(V+E)