algorithm - 拓扑排序找到到 t 的路径数

Question

我必须开发一个与拓扑排序相关的 O(|V|+|E|) 算法，该算法在有向无环图 (DAG) 中确定从图的每个顶点到 t 的路径数(t 是出度为 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]

完成后，对于每个 i在[1,t] , arr[i]指示来自 vi 的路径数至 vt

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

基地: 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)