Visualizzazione dei risultati da 1 a 6 su 6
  1. #1
    Utente bannato
    Registrato dal
    Oct 2010
    Messaggi
    1,219

    [Teoria]Visita in profondità di un grafo

    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?

  2. #2
    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

  3. #3
    Utente di HTML.it L'avatar di Alex'87
    Registrato dal
    Aug 2001
    residenza
    Verona
    Messaggi
    5,802
    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. Un albero binario è un albero binario.
    SpringSource Certified Spring Professional | Pivotal Certified Enterprise Integration Specialist
    Di questo libro e degli altri (blog personale di recensioni libri) | ​NO M.P. TECNICI

  4. #4
    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)

  5. #5
    Utente bannato
    Registrato dal
    Oct 2010
    Messaggi
    1,219
    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.

  6. #6
    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...

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.