使用迭代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)