将DFS的迭代实现转换为拓扑类型并不容易，因为对于递归实现而言，需要进行的更改更加自然。但是您仍然可以做到，只需要实现自己的堆栈即可。

首先，这是您的代码的稍有改进的版本（效率更高，复杂程度也不高）：

def iterative_dfs_improved(graph, start):
    seen = set()  # efficient set to look up nodes in
    path = []     # there was no good reason for this to be an argument in your code
    q = [start]
    while q:
        v = q.pop()   # no reason not to pop from the end, where it's fast
        if v not in seen:
            seen.add(v)
            path.append(v)
            q.extend(graph[v]) # this will add the nodes in a slightly different order
                               # if you want the same order, use reversed(graph[v])

    return path

这是我修改该代码以进行拓扑排序的方式：

def iterative_topological_sort(graph, start):
    seen = set()
    stack = []    # path variable is gone, stack and order are new
    order = []    # order will be in reverse order at first
    q = [start]
    while q:
        v = q.pop()
        if v not in seen:
            seen.add(v) # no need to append to path any more
            q.extend(graph[v])

            while stack and v not in graph[stack[-1]]: # new stuff here!
                order.append(stack.pop())
            stack.append(v)

    return stack + order[::-1]   # new return value!

我用“这里有新东西”评论的部分是确定堆栈上移顺序的部分。它检查找到的新节点是否为先前节点的子节点（位于堆栈顶部）。如果不是，它将弹出堆栈的顶部并将其值添加到order。在执行DFS时，order将从最后一个值开始，以相反的拓扑顺序进行。我们在函数末尾将其取反，并将其与堆栈上的剩余值（方便地已经按正确的顺序）连接起来。

因为此代码需要检查v not in graph[stack[-1]]很多次，所以如果graph设置字典中的值而不是列表，则效率会更高。图通常不关心边缘的保存顺序，因此，即使生成或更新图的代码可能需要修复，进行此类更改也不会导致大多数其他算法出现问题。如果您打算扩展图形代码以支持加权图形，则可能最终还是将列表更改为从节点映射到权重的字典，这对于此代码同样适用（字典查找O(1)就像设置查找一样）。另外，如果graph不能直接修改，我们可以构建自己需要的集合。

作为参考，这是DFS的递归版本，并对它进行了修改以进行拓扑排序。实际上，所需的修改非常小：

def recursive_dfs(graph, node):
    result = []
    seen = set()

    def recursive_helper(node):
        for neighbor in graph[node]:
            if neighbor not in seen:
                result.append(neighbor)     # this line will be replaced below
                seen.add(neighbor)
                recursive_helper(neighbor)

    recursive_helper(node)
    return result

def recursive_topological_sort(graph, node):
    result = []
    seen = set()

    def recursive_helper(node):
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                recursive_helper(neighbor)
        result.insert(0, node)              # this line replaces the result.append line

    recursive_helper(node)
    return result

而已！删除一行，在另一位置添加类似的行。如果您关心性能，则可能也应该result.append在第二个辅助函数中执行，而return result[::-1]在顶层recursive_topological_sort函数中执行。但是使用insert(0, ...)是一个最小的更改。

还需要注意的是，如果要整个图的拓扑顺序，则无需指定起始节点。实际上，可能没有单个节点可以遍历整个图，因此您可能需要进行多次遍历才能获得所有内容。在迭代拓扑排序中实现此目的的一种简单方法是初始化q为list(graph)（所有图的键的列表）而不是仅包含一个起始节点的列表。对于递归版本，请将的调用替换为recursive_helper(node)一个循环，该循环在图中的每个节点上都尚未调用时，会调用该图中的每个节点上的helper函数seen。