{ File: grafvis.pas } { Scopo: procedure di visita in profondita` ed in ampiezza di un grafo } { Le procedure di visita richiedono le definizioni di pile e code i cui elementi sono i nodi del grafo. } type TipoElemPila = TipoNodo; {$I PILE.PAS} { Inclusione della realizzazione del tipo di dato pila } type TipoElemCoda = TipoNodo; {$I CODE.PAS} { Inclusione della realizzazione del tipo di dato coda } { Le procedure di visita richiedono la definizione della procedura che analizza un nodo. L'analisi di un nodo puo` essere ad esempio la sua stampa: } procedure Analizza (i: TipoNodo); begin write(' ',i,' ') end; { algoritmo visita un grafo a partire dal nodo n 1. togli la marca a tutti i nodi del grafo 2. insieme dei nodi da visitare := insieme vuoto 3. metti n nell'insieme dei nodi da visitare 4. finche` l'insieme dei nodi da visitare non e' vuoto ripeti 5. estrai un nodo i dall'insieme dei nodi da visitare 6. se i non e' marcato allora 7. analizza i (stampa il valore intero i) 8. marca i 9. per ogni successore j di i che non e' marcato ripeti 10. metti j nell'insieme dei nodi da visitare } procedure VisitaInProfondita (var grafo: TipoGrafo; nodo_iniz: TipoNodo); { Effettua una visita del grafo in profondita` a partire da nodo_iniz. Utilizza una pila. } var i,j : TipoNodo; nodi_da_visitare : TipoPila; nodi_visti : array [TipoNodo] of boolean; begin { inizializzazione } { 1 } for i := 1 to NumNodi do nodi_visti[i] := FALSE; { 2 } InitPila(nodi_da_visitare); { 3 } Push(nodi_da_visitare, nodo_iniz); { cicla finche' ci sono nodi da visitare } { 4 } while not TestPilaVuota(nodi_da_visitare) do begin { prende il prossimo nodo i da visitare } { 5 } Pop(nodi_da_visitare, i); { analizza il nodo i e lo pone tra i nodi visti } { 6 } if not nodi_visti[i] then begin { 7 } Analizza(i); { 8 } nodi_visti[i] := TRUE; { aggiunge i successori non visitati del nodo i ai nodi da visitare } { 9 } for j := NumNodi downto 1 do if TestEsisteArco(grafo, i, j) and (not nodi_visti[j]) then {10 } Push(nodi_da_visitare, j) end end { while } end; { VisitaInProfondita } procedure VisitaInAmpiezza (var grafo: TipoGrafo; nodo_iniz: TipoNodo); { Effettua una visita del grafo in ampiezza a partire da nodo_iniz. Utilizza una pila. } var i,j : TipoNodo; nodi_da_visitare : TipoCoda; nodi_visti : array [TipoNodo] of boolean; begin { inizializzazione } { 1 } for i := 1 to NumNodi do nodi_visti[i] := FALSE; { 2 } InitCoda(nodi_da_visitare); { 3 } InCoda(nodi_da_visitare, nodo_iniz); { cicla finche' ci sono nodi da visitare } { 4 } while not TestCodaVuota(nodi_da_visitare) do begin { prendi il prossimo nodo i da visitare } { 5 } OutCoda(nodi_da_visitare, i); { analizza il nodo i e lo pone tra i nodi visti } { 6 } if not nodi_visti[i] then begin { 7 } Analizza(i); { 8 } nodi_visti[i] := TRUE; { aggiunge i successori non visitati del nodo i ai nodi da visitare } { 9 } for j := 1 to NumNodi do if TestEsisteArco(grafo, i, j) and (not nodi_visti[j]) then {10 } InCoda(nodi_da_visitare, j) end end end; { VisitaInAmpiezza } procedure VisitaRicInProfondita (var grafo: TipoGrafo; nodo_iniz: TipoNodo); { Effettua una visita del grafo in profondita` a partire da nodo_iniz. Utilizza una procedura ricorsiva. } var i : TipoNodo; nodi_visti : array [TipoNodo] of boolean; procedure VisitaRicorsiva (var grafo: TipoGrafo; i: TipoNodo); { Procedura ricorsiva che effettua la visita in profondita`. } var j : TipoNodo; { var globale nodi_visti : array [TipoNodo] of boolean } begin if not nodi_visti[i] then begin { analizza il nodo i e lo pone tra i nodi visti } Analizza(i); nodi_visti[i] := TRUE; { visita i successori non visitati del nodo i } for j := 1 to NumNodi do if TestEsisteArco(grafo, i, j) and (not nodi_visti[j]) then VisitaRicorsiva(grafo, j) end end; { VisitaRicorsiva } begin { VisitaRicInProfondita } { inizializzazione } for i := 1 to NumNodi do nodi_visti[i] := FALSE; { inizia la visita ricorsiva } VisitaRicorsiva(grafo, nodo_iniz); end; { VisitaRicInProfondita }