Passei muito tempo com esse problema. No entanto, só consigo encontrar soluções com métodos não recursivos para uma árvore:Não recursivo para árvore, ou método recursivo para o gráfico,Recursivo para gráfico.

E muitos tutoriais (eu não forneço esses links aqui) também não fornecem as abordagens. Ou o tutorial está totalmente incorreto. Por favor me ajude.

Atualizada:

É realmente difícil descrever:

Se eu tiver um gráfico não direcionado:

               1
             / |  \
            4  |   2
               3 /

1-- 2-- 3-1 é um ciclo.

Na etapa:push the neighbors of the popped vertex into the stack

WHAT'S THE ORDER OF THE VERTEXES SHOULD BE PUSHED?

Se a ordem por push for 2 4 3, o vértice na pilha é:

| |
|3|
|4|
|2|    
 _

Depois de saltar os nós, obtivemos o resultado: 1 -> 3 -> 4 -> 2 em vez de 1 -> 3 -> 2 -> 4.

É INCORRETO. QUE CONDIÇÃO DEVO ADICIONAR PARA PARAR ESTE CENÁRIO?