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) の 2 つのエッジを作成します。次に 3 を訪問し、まだ訪問していない 2 に接続されているため、エッジ (3,2) も作成しますが、これによりサイクルが作成されるため、計算されたスパニング ツリーはツリーではありません。どこが間違い？O(n) でスパニング ツリーを計算する別の方法がわかりません。

Answer 1

頂点をポップするときではなく、スタックにプッシュするときに、頂点を訪問済みとしてマークすることができます。