Download - Recorrido de grafos 1ra parte
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