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

一尘不染

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

algorithm

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

但是我不确定该算法是否与拓扑排序有关，还是应该用另一种观点来重构我的工作。

阅读 321

2020-07-28

共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

现在，证明上述主张很容易（与您的算法相比，我不知道它是否正确以及如何证明），这是通过归纳法完成的：

Base arr[t] == 1：，的确存在从t到t的唯一路径，即空路径。
假设：该索赔对k范围内的每个索赔都是正确的m < k <= t
证明：我们需要证明该索赔是正确的m。
让我们看一下从每部边缘vm：(v_m,v_i)。
因此，vt从v_m该路径开始的路径数使用此edge
(v_m,v_i)。正是arr[i]（归纳假设）。总结v_m从v_m到的所有可能边缘，可以得出从到的路径总数，v_t而这正是算法的工作。
从而，arr[m] = #paths from v_m to v_t

优质教育

时间复杂度：
第一步（拓扑排序）需要O(V+E)。
循环将所有边缘迭代一次，并且对所有顶点迭代一次，所以也是O(V+E)如此。
这使我们的整体复杂性O(V+E)

2020-07-28