0

我编写了这个伪代码来从无向图 (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) 中计算生成树的方法。

4

2 回答 2

3

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

于 2015-02-11T16:54:14.983 回答
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')
于 2015-02-11T17:02:43.353 回答