25-06-2014

1

Recorrido de Grafos utilizando árbolesRecorrido de Grafos utilizando árbolesAnálisis de algoritmosAnálisis de algoritmos

25-06-2014

2

• Es una estructura jerárquica aplicada sobre una colección de elementos llamados nodos.

• Uno de los cuales es llamado raíz. Los demás nodos son M conjuntos disjuntos (m >=0) cada uno de los cuales es un árbol en si los cuales reciben el nombre de sub-árboles de la raíz.

• Además se crea una relación de parentesco entre los nodos de forma que hay términos como: Padre, hijo, hermano, antecesor, sucesor, ancestro, etc.

• Para definir un árbol se necesita recursión.

• Se utilizan para representar formulas matemáticas, organizar información, árboles genealógicos, enumeración de capítulos y secciones de un libro, etc.

• No-lineal porque a cada elemento (nodo) le pueden seguir varios elementos (nodos).

Concepto de ÁrbolConcepto de Árbol

25-06-2014

3

PrePre--OrdenOrdenSe visita la raíz; se recorre el subárbol Izquierdo; se recorre el subárbol Derecho;Se visita la raíz; se recorre el subárbol Izquierdo; se recorre el subárbol Derecho;

Recorrido = Recorrido = A B E K F C G L M D H I J N O A B E K F C G L M D H I J N O A

B C D

E F G H I J

K L M N O

25-06-2014

4

Igual que los recorridos en árboles, se parte de un nodo dado y sirvenpara visitar los vértices y los arcos de manera sistemática.

Existen dos tipos de recorridos:

– Búsqueda en amplitud o anchura. Es equivalente arecorrer un árbol por niveles. Dado un nodo v, se visitan primero todoslos nodos adyacentes a v, luego todos los que están a distancia 2 (y novisitados), a distancia 3, y así sucesivamente hasta recorrer todos losnodos.

– Búsqueda en profundidad. Es equivalente a un recorridoen preorden de un árbol. Se elige un nodo v de partida. Se marcacomo visitado y se recorren los nodos no visitados adyacentes a v,usando recursivamente la búsqueda primero en profundidad.

• El recorrido puede ser para grafos dirigidos o no dirigidos.

Recorrido de GRAFOSRecorrido de GRAFOS

25-06-2014

5

Recorrido por AnchuraRecorrido por Anchura

A B D

H

T R

C

Recorrido desde Vertice por anchura desde vertice D ={D, B, C, H, R, A, T }

D

B C

RH

A T

1°

2° 3°

4° 5°

6° 7°

Nivel 1

Nivel 2

Nivel 3

Nivel 4

25-06-2014

6

Recorrido por profundidadRecorrido por profundidad

A B D

H

T R

C

Recorrido por profundidad desde Vértice D= {D, C, R, H, T, A, B}

1°

2°

3°

4°

5°

6° 7°

Grafo Dirigido, por lo tanto necesitamos

buscar la ruta que incluya más nodos.

En este tipo de grafos se asume en algunos

casos que el recorrido esta sujeto a los

supuestos de:

Peso y Orden alfabético.

25-06-2014

7

Test

Recorrido de un grafo en anchura.

A-B-C-D-E-G-H-I-J-K-F

1°Nivel

2°Nivel

3°Nivel

4°Nivel

5°Nivel

A

B C D

E

I

F

G H

J K

1°

2°3°

4°

5° 6° 7°

8° 9° 10°

11°

25-06-2014

8

Recorrido de un grafo en profundidad

Solución: A-B-E-I-F-C-G-J-K-H-D

Pre-Orden

Se visita la raíz; se recorre el subárbol Izquierdo; se recorre el subárbol DerechoSe visita la raíz; se recorre el subárbol Izquierdo; se recorre el subárbol Derecho

1°2°

3°

4°

5°

6°

7°

8° 9°

10°

11°

Como es un grafo no dirigido, podemos utilizar el principio de Pre-Orden para abarcar el máximo de nodos