我正在尝试创建 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) 等。 下面是使用简单堆栈的迭代 DFS 的实现( LIFO)，但它不计算完成时间。我面临的一个关键问题是，由于顶点被弹出，一旦顶点完全扩展(与递归不同)，算法就无法追溯其路径。我该如何解决？
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)
最佳答案
将您的堆栈视为一堆任务，而不是顶点。您需要执行两种类型的任务。您需要扩展顶点，并且需要添加完成时间。
当你去扩展一个顶点时，你首先添加计算完成时间的任务，然后添加扩展每个子顶点。
当您添加完成时间时，您可以知道扩展已完成。
关于python - 如何为迭代深度优先搜索添加完成时间？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28879510/