[Algoritmi] chiarimento su visita in profondità con la pila

[mathix1]

non ho ben compreso come lavora questo algoritmo di visita in profondità di un grafo con la pila

1)abbiamo una pila vuota, tramite push inseriamo il vertice del grafo
2) lo marchiamo come visitato
3)finche la pila non è vuota, eseguiamo un pop e salviamo il risultato in "r".
4) per ogni figlio s di r non marcato, lo marchiamo e lo mettiamo nella pila
ora qui sorgono i dubbi:
quando mettiamo i figli di r nella pila, mette prima il sinistro e poi il destro? però tornando al pop l'elemento estratto è il figlio destro e non il sinistro.

qualcuno può farmi capire dove sbaglio?

[Rggb1]

Non vedo il tuo sbaglio, o per meglio dire non ho capito il tuo dubbio.

PS. E cosa intendi con "sinistro", "destro"...? Questo algoritmo va bene per qualunque grafo connesso non orientato, non solo per gli alberi (e non solo per gli alberi binari).

[mathix1]

non mi è chiaro il passo in cui dice "per ogni vertice s non marcato collegato a r"
la visita in profondità dopo aver visitato un vertice s dovrebbe continuare a scorrere, invece a me quella condizione fa pensare che marca ogni s collegato a r (cioè come nella visità in ampiezza).
inoltre con quale criterio viene scelto uno dei tanti s collegati a r?

[Rggb1]

"mathix":la visita in profondità dopo aver visitato un vertice s dovrebbe continuare a scorrere, invece a me quella condizione fa pensare che marca ogni s collegato a r (cioè come nella visità in ampiezza).

Dubbio legittimo: forse si potrebbe prendere una condizione differente, tipo "esiste un vertice..." invece di "per ogni vertice..." eccetera, anche se si deve modificare leggermente l'algoritmo.

"mathix":inoltre con quale criterio viene scelto uno dei tanti s collegati a r?

Questo è ininfluente: l'algoritmo è puramente descrittivo, e non prende in considerazione il tipo di struttura dati usato per memorizzare il grafo.