python - 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 压入堆栈 before 我们压入它的邻居(我们编写压入 v 的代码 before插入 v 的邻居的 for 循环) - 否则这个技巧不起作用。最终我们将再次从堆栈中弹出v。此时，v 已完成!我们之前见过 v，所以，我们进入 else 情况并计算新的完成时间。

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

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

请注意，尽管我们正在插入图形到堆栈上两次。然而，存在更优雅的解决方案。我推荐阅读 Magnus Lie Hetland(ISBN:1430232374、9781430232377)的 Python 算法:掌握 Python 语言中的基本算法 的第 5 章。问题 5-6 和 5-7(第 122 页)准确描述了您的问题。作者回答了这些问题并给出了问题的替代解决方案。

问题:

5-6 In recursive DFS, backtracking occurs when you return from one of the recursive calls. But where has the backtracking gone in the iterative version?

5-7. Write a nonrecursive version of DFS that can deal determine finish-times.

答案:

5-6 It’s not really represented at all in the iterative version. It just implicitly occurs once you’ve popped off all your “traversal descendants” from the stack.

5-7 As explained in Exercise 5-6, there is no point in the code where backtracking occurs in the iterative DFS, so we can’t just set the finish time at some specific place (like in the recursive one). Instead, we’d need to add a marker to the stack. For example, instead of adding the neighbors of u to the stack, we could add edges of the form (u, v), and before all of them, we’d push (u, None), indicating the backtracking point for u.