拓扑排序找到的路径的数目为t [英] Topological sort to find the number of paths to t

问题描述

我要开发一个O（| V | + | E |）算法相关的拓扑排序其中，在一个有向非循环图（DAG），确定的路径数从图中的每个顶点到吨（t是一节点与出度0）。我已经开发了DFS的修改如下：

I have to develop an O(|V|+|E|) algorithm related to topological sort which, in a directed acyclic graph (DAG), determines the number of paths from each vertex of the graph to t (t is a node with out-degree 0). I have developed a modification of DFS as follow:

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

但我不知道该算法与拓扑排序或者我是否应该调整我的工作与另一个角度来看。

But I am not sure if this algorithm is related to topological sort or if should I restructure my work with another point of view.

推荐答案

它可以使用动态规划和拓扑排序如下进行：

It can be done using Dynamic Programming and topological sort as follows:

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]

当你完成后，每个我在 [1，T] ，改编[I] 表示路径的数量从六到 VT

When you are done, for each i in [1,t], arr[i] indicates the number of paths from vi to vt

现在，证明上述主张很容易（比较你的算法，我不知道，如果它的正确，以及如何证明这一点），它是通过感应完成的：

Now, proving the above claim is easy (comparing to your algorithm, which I have no idea if its correct and how to prove it), it is done by induction:

文章： 改编[T] == 1 ，确实有从T单一路径T，空单。
假设：索赔是真正的每个 K 的范围 M＆LT; K＆LT; = T
证明：我们需要展示的索赔是正确的 M 。
让我们来看看各出边从 VM ：（V_M，V-I）。
因此，路径数 VT 启动 V_M 使用此边 （V_M，V-I）。正是改编[I] （归纳假设）。总结出边所有的可能性，从 V_M ，为我们提供了路径的总数从 V_M 到 v_t - 而这正是算法做。
因此，改编[M] = #paths从V_M到v_t

Base: arr[t] == 1, and indeed there is a single path from t to t, the empty one.
Hypothesis: The claim is true for each k in range m < k <= t
Proof: We need to show the claim is correct for m.
Let's look at each out edge from vm: (v_m,v_i).
Thus, the number of paths to vt starting from v_m that use this edge (v_m,v_i). is exactly arr[i] (induction hypothesis). Summing all possibilities of out edges from v_m, gives us the total number of paths from v_m to v_t - and this is exactly what the algorithm do.
Thus, arr[m] = #paths from v_m to v_t

QED

时间复杂度：
第一步（拓扑排序）采用 O（V + E）。 维基，循环遍历所有的边一次，所有顶点一次，所以它是 O（V + E）为好。
这给了我们总 O（V + E）的复杂性

Time complexity:
The first step (topological sort) takes O(V+E).
The loop iterate all edges once, and all vertices once, so it is O(V+E) as well.
This gives us total complexity of O(V+E)

这篇关于拓扑排序找到的路径的数目为t的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！