生成树 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

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

Answer 2

这就是我的代码。这里 visited[] 是一个布尔数组或哈希表

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

生成树 DFS 算法不创建树

Spanning tree DFS algorithm doesn't create a tree

algorithm

theory

graph-theory

spanning-tree