algorithm - 生成树 DFS 算法不创建树

Question

我编写此伪代码是为了从无向图 (G,V) 创建生成树，其中 S 是堆栈，v 是我们要开始计算的顶点:

PROCEDURE SPANNING-TREE(G,v)
    S := {v}   
    while S is not empty 
        u := pop(S)
        visit u
        for each u' connected to u
            if u' is not visited
                s.push(u')
                add-edge(u,u')

由于某种原因，这个算法是错误的。例如，让我们考虑这个简单的无向图:

如果我们从第一个顶点开始，我们访问它，然后将 2 和 3 压入堆栈并创建两条边:(1,2) 和 (1,3)。然后我们访问 3，因为它连接到尚未访问过的 2，我们还创建了一条边 (3,2)，但这会创建一个循环，因此计算出的生成树不是树。错在哪里？我想不出另一种在 O(n) 中计算生成树的方法。

Answer 1

您可以在将顶点插入堆栈时将其标记为已访问，而不是在将其弹出时标记为已访问。