Алгоритм Spanning tree 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')