拓扑排序以找到到 t 的路径数 [英] Topological sort to find the number of paths to t
问题描述
我必须开发与拓扑排序相关的 O(|V|+|E|) 算法,该算法在有向无环图 (DAG) 中确定从图的每个顶点到 t 的路径数(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
,arr[i]
表示从vi
到 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:
Base: arr[t] == 1
,并且确实有一条从 t 到 t 的路径,即空路径.
假设:对于 m <范围内的每个
k
的说法都是正确的.k <= t
证明:我们需要证明 m
的声明是正确的.
让我们看看 vm
的每个出边:(v_m,v_i)
.
因此,使用这条边(v_m,v_i)
的从v_m
开始到vt
的路径数.正是 arr[i]
(归纳假设).将 v_m
中出边的所有可能性相加,得到从 v_m
到 v_t
的路径总数——这正是算法所做的.
因此,arr[m] = #paths from v_m to 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)
这篇关于拓扑排序以找到到 t 的路径数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!