kosaraju使用迭代dfs查找完成时间

Question

这是我为Kosaraju算法做的代码的第一部分.

###### reading the data #####
with open('data.txt') as req_file:
        ori_data = []
        for line in req_file:
            line = line.split()
            if line:
                line = [int(i) for i in line]
                ori_data.append(line)

###### forming the Grev ####
revscc_dic = {}
for temp in ori_data:
    if temp[1] not in revscc_dic:
        revscc_dic[temp[1]] = [temp[0]]
    else:
        revscc_dic[temp[1]].append(temp[0])

print revscc_dic        

######## finding the G#####
scc_dic = {}
for temp in ori_data:
    if temp[0] not in scc_dic:
        scc_dic[temp[0]] = [temp[1]]
    else:
        scc_dic[temp[0]].append(temp[1])

print scc_dic        

##### iterative dfs ####
path = []
for i in range(max(max(ori_data)),0,-1):
    start = i
    q=[start]
    while q:
        v=q.pop(0)
        if v not in path:
          path.append(v)
          q=revscc_dic[v]+q
print path  

代码读取数据并正确形成Grev和G. 我已经编写了迭代dfs的代码.我怎样才能找到完成时间？我理解使用纸和笔找到完成时间,但我不明白作为代码完成时间的部分？我该如何实现它..只有在此之后我才能继续下一部分代码.请帮忙.提前致谢.

data.txt文件包含:

1 4
2 8
3 6
4 7
5 2
6 9
7 1
8 5
8 6
9 7
9 3

请将其保存为data.txt.

Answer 1

使用递归 dfs,很容易看到给定顶点何时"完成"(即当我们访问dfs树中的所有子节点时).可以在递归调用返回后立即计算完成时间.
但是对于迭代 dfs,这并不容易.现在我们使用while循环迭代地处理队列,我们​​已经丢失了一些与函数调用相关联的嵌套结构.或者更确切地说,我们不知道何时发生回溯.不幸的是,没有办法知道何时发生回溯而不向我们的顶点堆栈添加一些额外的信息.

向dfs实现添加完成时间的最快方法是这样的:

##### iterative dfs (with finish times) ####
path = []
time = 0
finish_time_dic = {}
for i in range(max(max(ori_data)),0,-1):
    start = i
    q = [start]
    while q:
        v = q.pop(0)
        if v not in path:
            path.append(v)
            q = [v] + q
            for w in revscc_dic[v]:
                if w not in path: q = [w] + q
        else:
            if v not in finish_time_dic:
                finish_time_dic[v] = time
                time += 1
print path  
print finish_time_dic

这里使用的技巧是当我们v从堆栈弹出时,如果它是我们第一次看到它,那么我们再次将它添加回堆栈.这是使用:q = [v] + q.我们必须在推送它的邻居之前推进v堆栈(我们编写在推送邻居的for循环之前推送的代码) - 否则技巧不起作用.最终我们将再次弹出堆栈.此时,v已经完成了!我们以前见过,所以,我们进入其他情况并计算一个新的完成时间.v vvv

对于提供的图表,finish_time_dic给出正确的完成时间:

{1: 6, 2: 1, 3: 3, 4: 7, 5: 0, 6: 4, 7: 8, 8: 2, 9: 5}

请注意,尽管我们正在将图形的每个节点推入堆栈两次,但此dfs算法(具有完成时间修改)仍具有 O(V + E)复杂度.但是,存在更优雅的解决方案.我建议你阅读的第5章Python的算法:掌握基本算法用Python语言通过马格努斯李赫特兰(ISBN:1430232374,9781430232377).问题5-6和5-7(第122页)完全描述了您的问题.作者回答了这些问题并提供了另一种解决方案.

问题:

5-6在递归DFS中,当您从其中一个递归调用返回时,会发生回溯.但是在迭代版本中,回溯在哪里？

5-7.编写一个可以处理确定完成时间的DFS的非递归版本.

回答:

5-6它在迭代版本中根本没有表现出来.一旦你从堆栈中弹出所有"遍历后代",它就会隐含地发生.

5-7作为练习5-6解释的,有在回溯中反复出现的DFS代码是没有意义的,所以我们不能只设置在某些特定的地方完成时间(如在递归一个).相反,我们需要在堆栈中添加标记.例如,不是将u的邻居添加到堆栈中,而是可以添加表单的边缘(u, v),在所有这些边缘之前,我们将推送(u, None),指示回溯点u.