python - 如何为迭代深度优先搜索添加完成时间？

Question

我正在尝试创建 depth-first分配完成时间(顶点不能再扩展的时间)的算法，用于 Kosaraju's algorithm 之类的事情.我能够相当轻松地创建 DFS 的递归版本，但我很难将其转换为迭代版本。

我正在使用邻接表来表示图形:顶点字典。例如输入图 {1: [0, 4], 2: [1, 5], 3: [1], 4: [1, 3], 5: [2, 4], 6: [3, 4, 7, 8], 7: [5, 6], 8: [9], 9: [6, 11], 10: [9], 11: [10]}表示边(1,0), (1,4), (2,1), (2,5)等。下面是使用简单堆栈(LIFO)的迭代DFS的实现，但它不计算完成时间。我面临的关键问题之一是，由于顶点被弹出，一旦顶点完全展开(与递归不同)，算法就无法追溯其路径。我该如何解决这个问题？

def dfs(graph, vertex, finish, explored):
    global count

    stack = []
    stack.append(vertex)

    while len(stack) != 0:
        vertex = stack.pop()

        if explored[vertex] == False:
            explored[vertex] = True

            #add all outgoing edges to stack:
            if vertex in graph:                 #check if key exists in hash -- since not all vertices have outgoing edges
                for v in graph[vertex]:
                    stack.append(v)

        #this doesn't assign finishing times, it assigns the times when vertices are discovered:                                            
        #finish[count] = vertex
        #count += 1

注意还有一个补充 DFS 的外部循环——不过，我认为问题不在于此:

#outer loop:
for vertex in range(size, 0, -1):
    if explored[vertex] == False:
        dfs(hGraph, vertex, finish, explored)

Answer 1

将堆栈视为任务堆栈，而不是顶点。您需要完成两种类型的任务。你需要扩展顶点，你需要添加完成时间。

当你去扩展一个顶点时，首先添加计算完成时间的任务，然后添加扩展每个子顶点。

当您去添加完成时间时，您可以知道扩展已完成。