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

Question

我正在尝试创建 depth-first algorithm that assigns finishing times (the time when a vertex can no longer be expanded) which are used for things like 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 的实现一个简单的堆栈（后进先出），但它不计算完成时间。我面临的关键问题之一是，由于顶点被弹出，一旦顶点完全展开（与递归不同），算法就无法追溯其路径。我该如何解决这个问题？

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

N.b。还有一个补充 DFS 的外部循环——不过，我认为问题不在于此：

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

Answer 1

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

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

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

Answer 2

这是一个在迭代子例程中使用两个堆栈的工作解决方案。数组 traceBack 包含已探索的顶点，并与互补二维数组 stack 相关联，后者包含尚未探索的边数组。这两个数组是链接的；当我们向 traceBack 添加一个元素时，我们也会向 stack 添加一个元素（与弹出元素相同）。

count = 0
def outerLoop(hGraph, N):
    explored    = [False for iii in range(N+1)]
    finish      = {}

    for vertex in range(N, -1, -1):
        if explored[vertex] == False:
            dfs(vertex, hGraph, explored, finish)

    return finish


def dfs(vertex, graph, explored, finish):
    global count
    stack       = [[]]                              #stack contains the possible edges to explore
    traceBack   = []
    traceBack.append(vertex)

    while len(stack) > 0:
        explored[vertex] = True

        try:
            for n in graph[vertex]:
                if explored[n] == False:
                    if n not in stack[-1]:          #to prevent double adding (when we backtrack to previous vertex)
                        stack[-1].append(n)
                else:
                    if n in stack[-1]:              #make sure num exists in array before removing
                        stack[-1].remove(n)             
        except IndexError: pass

        if len(stack[-1]) == 0:                     #if current stack is empty then there are no outgoing edges:
            finish[count] = traceBack.pop()         #thus, we can add finishing times
            count += 1

            if len(traceBack) > 0:                  #to prevent popping empty array
                vertex = traceBack[-1]
            stack.pop()
        else:
            vertex = stack[-1][-1]                  #pick last element in top of stack to be new vertex

            stack.append([])
            traceBack.append(vertex)

Answer 3

这是一个方法。每次遇到下面的情况，我们就回调或者标记时间，

该节点没有出边（不可能）。
当遍历节点的parent与上次parent不同时（parent改变）。在那种情况下，我们完成最后一个 parent.
当我们到达栈尾（树尾）时。我们完成了最后一个 parent.

这是代码，

var dfs_with_finishing_time = function(graph, start, cb) {
    var explored = [];
    var parent = [];
    var i = 0;
    for(i = 0; i < graph.length; i++) {
            if(i in explored)
                    continue;
            explored[i] = 1;
            var stack = [i];
            parent[i] = -1;
            var last_parent = -1;
            while(stack.length) {
                    var u = stack.pop();
                    var k = 0;
                    var no_way = true;
                    for(k = 0; k < graph.length; k++) {
                            if(k in explored)
                                    continue;
                            if(!graph[u][k])
                                    continue;
                            stack.push(k);
                            explored[k] = 1;
                            parent[k] = u;
                            no_way = false;
                    }
                    if(no_way) {
                            cb(null, u+1); // no way, reversed post-ordering (finishing time)
                    }
                    if(last_parent != parent[u] && last_parent != -1) {
                            cb(null, last_parent+1); // parent change, reversed post-ordering (finishing time)
                    }
                    last_parent = parent[u];
            }
            if(last_parent != -1) {
                    cb(null, last_parent+1); // tree end, reversed post-ordering (finishing time)
            }
    }
}

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

How do I add finishing times for iterative depth-first search?

python

algorithm

graph-theory

depth-first-search