我要开发一个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)
相关推荐
最新文章