xglobusx
20-06-2007, 13:32
Applicando un algoritmo di visita in ampiezza (breadth-first-search) su un grafo, si ottiene un albero BFS, che ha come radice la sorgente (il nodo da cui è stata fatta partire la visita), come vertici quelli del grafo e un sottoinsieme degli archi del grafo.
Mi è venuto un dubbio:
se da un vertice del grafo partono 3 archi verso altri tre nodi come fa il risultato della visita in ampiezza ad essere un albero? :confused:
Da quel nodo uscirebbero sempre 3 archi, in un albero non sono al massimo 2? il figlio dx e sx?
es:
O A
/
S O -- O B
\
O C
S è la sorgente, A, B e C sono tre vertici raggiungibili da S che poi saranno a loro volta collegati ad altri vertici ecc. A, B e C nell'albero saranno tutti figli di S o mi sfugge qualcosa?
Mi è venuto un dubbio:
se da un vertice del grafo partono 3 archi verso altri tre nodi come fa il risultato della visita in ampiezza ad essere un albero? :confused:
Da quel nodo uscirebbero sempre 3 archi, in un albero non sono al massimo 2? il figlio dx e sx?
es:
O A
/
S O -- O B
\
O C
S è la sorgente, A, B e C sono tre vertici raggiungibili da S che poi saranno a loro volta collegati ad altri vertici ecc. A, B e C nell'albero saranno tutti figli di S o mi sfugge qualcosa?