使用迭代dfs求完成时间的kosaraju

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的代码。我怎样才能算上完成时间？？我知道用纸和笔来计算完成时间，但我不明白完成时间的部分是代码？？我如何实施它。。只有在这之后，我才能继续我的下一部分代码。请帮忙。提前谢谢。在

在数据.txt文件包含：

^{pr2}$

请另存为数据.txt. 在

Answer 1

迭代DFS本身并不复杂，如Wikipedia所示。然而，计算每个节点的完成时间需要对算法进行一些调整。我们只在第二次遇到节点时将其从堆栈中弹出。在

下面是我的实现，我觉得它可以更清楚地说明发生了什么：

step = 0  # time counter

def dfs_visit(g, v):
    """Run iterative DFS from node V"""
    global step
    total = 0
    stack = [v]  # create stack with starting vertex
    while stack:  # while stack is not empty
        step += 1
        v = stack[-1]  # peek top of stack
        if v.color:  # if already seen
            v = stack.pop()  # done with this node, pop it from stack
            if v.color == 1:  # if GRAY, finish this node
                v.time_finish = step
                v.color = 2  # BLACK, done
        else:  # seen for first time
            v.color = 1  # GRAY: discovered
            v.time_discover = step
            total += 1
            for w in v.child:  # for all neighbor (v, w)
                if not w.color:  # if not seen
                    stack.append(w)
    return total

def dfs(g):
    """Run DFS on graph"""
    global step
    step = 0  # reset step counter
    for k, v in g.nodes.items():
        if not v.color:
            dfs_visit(g, v)

我遵循CLR Algorithm Book的约定，并在DFS搜索期间使用节点着色来指定其状态。我觉得这比使用单独的列表来跟踪节点状态更容易理解。在

所有节点以白色开始。当在搜索过程中发现它时，它被标记为灰色。当我们完成它时，它被标记为黑色。在

在while循环中，如果一个节点是白色的，我们将其保留在堆栈中，并将其颜色更改为灰色。如果它是灰色我们将其颜色更改为黑色，并设置其完成时间。如果它是黑色的，我们就忽略它。在

堆栈上的节点有可能是黑色的（即使在将其添加到堆栈之前进行了着色检查）。一个白色节点可以两次添加到堆栈中（通过两个不同的邻居）。最终会变成黑色。当我们到达堆栈上的第二个实例时，我们需要确保不会更改它已经设置的完成时间。在

以下是一些附加的支持代码：

^{pr2}$

要在反向图上运行DFS，可以在处理edges文件时为每个节点构建类似于子列表的父列表，并在DFS_visit（）中使用父列表而不是子列表。在

要在SCC计算的最后一部分减少完成时间来处理节点，可以构建节点的最大堆，并在dfs_visit（）中使用该最大堆，而不是简单的子列表。在

    while g.max_heap:
        v = heapq.heappop(g.max_heap)[1]
        if not v.color:
           size = dfs_visit(g, v)
           scc_size.append(size)

Answer 2

使用递归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推送到堆栈的上（我们在之前编写代码，将v推送到的for循环之前推送{}的邻居），否则这个技巧就行不通了。最终，我们将再次从堆栈中弹出v，再次。此时，v已完成！我们之前已经看过v，因此，我们进入else情况并计算一个新的完成时间。在

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

^{pr2}$

注意，这个dfs算法（经过finishing times修改）仍然具有O（V+E）的复杂度，尽管我们将图的每个节点压入堆栈两次。然而，还有更优雅的解决方案。 我建议阅读Magnus Lie Hetland的《Python算法：掌握Python语言的基本算法》（ISBN:14302323749781430232377）的第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.

Answer 3

我对Lawson版本的迭代DFS产生的顺序有一些问题。这是我的版本的代码，它与DFS的递归版本有一对一的映射。在

n = len(graph)
time = 0
finish_times = [0] * (n + 1)
explored = [False] * (n + 1)

# Determine if every vertex connected to v
# has already been explored
def all_explored(G, v):
    if v in G:
        for w in G[v]:
            if not explored[w]:
                return False
    return True

# Loop through vertices in reverse order
for v in xrange(n, 0, -1):
    if not explored[v]:
        stack = [v]
        while stack:
            print(stack)
            v = stack[-1]
            explored[v] = True

            # If v still has outgoing edges to explore
            if not all_explored(graph_reversed, v):
                for w in graph_reversed[v]:

                    # Explore w before others attached to v
                    if not explored[w]:
                        stack.append(w)
                        break

            # We have explored vertices findable from v
            else:
                stack.pop()
                time += 1
                finish_times[v] = time