4.3.1. Recorridos sobre grafos.

Búsqueda primero en profundidad

procedure BuscaPrimeroProfundidad;

var v: integer;

begin

BorraMarcas;

for v:= 1 to num_nodos do

if marca[v]= no_visitado then

bpp (v);

end;

procedure bpp (v: nodo);

var w: integer;

begin

marca[v]:= visitado;

for cada nodo w adyacente a v do

if marca[w]= no_visitado then

bpp(w);

end;

• El orden en el que se visitan unos nodos a partir de otros puede ser visto como un árbol: árbol abarcador en profundidad asociado al grafo.

• Si el grafo es no dirigido, entonces se generará un árbol por cada componente conexa. Tendremos un bosque abarcador en profundidad.

1

2

3

4

5

6

7

9

8

1º

2º

4º

3º

6º

5º

8º

7º

9º

Grafo no dirigido, no conexo Bosque abarcador en profundidad

Arcos del árbol

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica