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

Question

我正在尝试创建深度优先算法,该算法指定完成时间(顶点无法再展开的时间),这些算法用于Kosaraju算法等事情.我能够相当容易地创建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

Nb还有一个外部循环补充DFS - 但是,我不认为问题出在那里:

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

Answer 1

将堆栈视为一堆任务,而不是顶点.您需要执行两种类型的任务.您需要扩展顶点,并且需要添加完成时间.

当您扩展顶点时,首先添加计算完成时间的任务,然后添加扩展每个子顶点.

当你去添加完成时间时,你可以知道扩展完成了.