我必须开发一个与拓扑排序相关的 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
但我不确定这个算法是否与拓扑排序有关,或者我是否应该从另一个角度重新组织我的工作。
最佳答案
可以使用动态规划和拓扑排序来完成,如下所示:
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
现在,证明上述说法很容易(与你的算法相比,我不知道它是否正确以及如何证明它),它是通过归纳完成的:
基地: arr[t] == 1
,并且确实存在从 t 到 t 的单一路径,即空路径。
假设:声明对每个k
都是正确的在范围 m < k <= t
证明:我们需要证明m
的声明是正确的.
让我们看看vm
的每条出边。 : (v_m,v_i)
.
因此,到vt
的路径数从 v_m
开始使用此边缘的 (v_m,v_i)
.正是arr[i]
(归纳假设)。总结 v_m
中所有可能的出边, 给了我们来自 v_m
的路径总数至 v_t
- 这正是算法所做的。
因此,arr[m] = #paths from v_m to v_t
QED
时间复杂度:
第一步(拓扑排序)取O(V+E)
.
循环遍历所有边一次,所有顶点一次,所以它是O(V+E)
以及。
这给了我们总复杂度 O(V+E)
关于algorithm - 拓扑排序找到到 t 的路径数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18087559/