PDA

Visualizza la versione completa : [OT] Visita in profondità di un grafo


ramy89
08-12-2011, 15:05
Non ho capito bene una cosa.
La visita in profondità deve visitare tutti i nodi, partendo dalla radice, allontanandosi sempre di più dalla radice.
Però l' algoritmo della visita in profondità è questo:
-Visita la radice;
-Per ogni nodo adiacente, se non è già stato visitato, visitalo (ricorsivo).

Ma in questo modo non è detto che si visitino i nodi allontanandosi sempre di più dalla radice, perchè se io ad esempio ho i nodo A,B,C (in un grafo non orientato).
Stabilisco che A e B sono collegati, A e C sono collegati, B e C sono collegati.
Allora la visita dipenderà da quale nodo adiacente viene scelto per primo, applico l' algoritmo:

-Visito A;
-B e C sono adiacenti, supponiamo venga scelto prima C, allora visito C;
-Poi visito B.

Però in questo caso i nodi non sono stati visitati allontanandosi sempre di più dalla radice.
Questa è allora considerata una visita dfs o l' algoritmo è sbagliato? Se si, come fare per evitare di "riavvicinarsi" alla radice visitandoli tutti in ordine di distanza crescente dalla radice?

grimaldello
09-12-2011, 16:49
Se per grafo intendi anche albero binario, quando li avevo studiati avevo imparato alcune cose, che però non so se fanno al caso tuo... comunque te le scrivo lo stesso :)

Pecorrere un albero in profondità significa scendere lungo qualche cammino fin dove è possibile e poi risalire e così via. Ci sono 3 metodi per fare questo:

Ordine prefisso: ogni nodo viene considerato prima che vengano considerati i suoi sottoalberi e per questi si visita prima il sinistro e poi il destro.

Ordine infisso: si considera prima il sottoalbero sinistro di ogni nodo, poi il nodo stesso ed infine il sottoalbero destro.

Ordine postfisso: si considera prima il sottoalbero sinistro, poi il sottoalbero destro ed infine il nodo stesso

Spero di averti chiarito le idee

Alex'87
09-12-2011, 17:36
Originariamente inviato da grimaldello
Se per grafo intendi anche albero binario, quando li avevo studiati avevo imparato alcune cose, che però non so se fanno al caso tuo... comunque te le scrivo lo stesso :) Un grafo è un grafo (http://en.wikipedia.org/wiki/Graph_(mathematics)). Un albero binario è un albero binario.

grimaldello
09-12-2011, 17:45
Quando li avevo studiati per l'esame di Matematica Discreta gli alberi mi ricordo c'entravano qualcosa con i grafi... e comunque:

http://it.wikipedia.org/wiki/Albero_(grafo)

ramy89
09-12-2011, 17:54
Un albero è un grafo orientato, privo di cicli.
Ma non tutti i grafi sono alberi.

Vorrei sapere se secondo voi, nell' esempio che ho fatto, visitando prima A poi C poi B ho fatto una visita in profondità o se l' algoritmo che ho applicato è errato.

grimaldello
09-12-2011, 18:16
Sincerametne di algoritmi per percorrere i grafi non ne ho mai fatti e visti.... quindi non saprei aiutarti...

Tuttavia secondo me usando la ricorsione dovrai per forza "ritornare in su" quando sei arrivato alla fine di un cammino visto che si verificherà un caso base della tua funzione ricorsiva e quindi tornerai all'invocazione precedente della funzione...

Loading