生成树DFS算法不创建树

我写了这个伪代码来创建一个从非定向图（G，V）的生成树，其中S是一个堆栈，v是我们想要从中启动的顶点计算：生成树DFS算法不创建树

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')

由于某种原因，这种算法是错误的。例如，让我们考虑一下这个简单的无向图：
enter image description here

如果我们从第一个顶点开始，我们参观一下，然后我们推2,3入堆栈，我们创建了两个边：（1,2）和（1,3）。然后我们访问3，并且由于它连接到尚未访问过的2，我们还创建了边（3,2），但是这会创建一个循环，因此计算的生成树不是树。哪里错了？我无法想象在O（n）中计算生成树的另一种方式。

来源

2015-02-11 Ramy Al Zuhouri

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

来源

2015-02-11 16:54:14 kraskevich

这将是我的代码。这里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-11 17:02:43

生成树DFS算法不创建树

回答

相关问题