11

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

但我不确定这个算法是否与拓扑排序有关，或者我是否应该从另一个角度重构我的工作。

4

1 回答 1

10

它可以使用动态规划和拓扑排序来完成，如下所示：

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)。 因此，从那个开始
的路径数使用这条边。正是（归纳假设）。将所有出边的可能性相加，得到从到的路径总数- 这正是算法所做的。 因此，vtv_m(v_m,v_i)arr[i]v_mv_mv_t
arr[m] = #paths from v_m to v_t

量子点

时间复杂度：
第一步（拓扑排序）需要O(V+E).
循环迭代所有边一次，所有顶点一次，所以它也是O(V+E)如此。
这使我们的总复杂度为O(V+E)

于 2013-08-06T18:24:12.653 回答