稀疏循环图中最长的简单路径
给定：一个不加权的有向图（G =（E，V）），它可以包含任意数量的周期。
目标：对于所有顶点，我想要V中某个目标顶点X的最长简单路径
算法思想：
For each v in V
v.distanceToTarget = DepthFirstSearch(v)
Next
DepthFirstSearch(v as Vertex)
if v = target then
'Distance towards target is 0 for target itself
return 0
elseif v.isVisitedInCurrentDFSPath then
'Cycle found -> I wont find the target when I go around in cycles -> abort
return -infinity
else
'Return the maximum Distance of all Successors + 1
return max(v.Successors.ForEach(Function(v) DepthFirstSearch(v) )) + 1
end if
这是正确的所有情况？ （假设可以从每个顶点到达目标）
我图中的边数很少。 假设| E | <= 3 * | V | 成立。 我如何计算平均时间复杂度？
谢谢！
时间复杂度是关于什么值最影响你的运行时间。 在你的情况下，你评估v和目标之间的所有可能的路径。 这基本上是O（路线数量）。 现在你需要弄清楚如何用E和V来表示所有可能路线的数量。
最有可能的结果是O（exp（E））或O（exp（V）），因为在添加新的可能路线时，通过每个节点/顶点的路线数量呈指数增长。
编辑：我错过了一个细节，你要求的平均时间复杂度，这意味着摊销复杂性。 但是，由于你的算法总是评估所有可能的路径，所以最坏情况的复杂度与平均复杂度相同。
链接地址: http://www.djcxy.com/p/39337.html