antes de todo hablaremos primero del concepto de arboles:
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).
ejemplo de un arbol
ejemplo de arboles por que a su vez existen varios tipos de arboles
ahora veremos los tipos de búsquedas:
Pre-Orden
Se visita la raíz; se recorre el subárbol Izquierdo; se recorre el subárbol Derecho.
Recorrido = A B E K F C G L M D H I J N O
Recorrido de GRAFOS
Igual que los recorridos en árboles, se parte de un nodo dado y sirven
para visitar los vértices y los arcos de manera sistemática.
Existen dos tipos de recorridos:
Búsqueda en amplitud o anchura:Es equivalente a
recorrer un árbol por niveles. Dado un nodo v, se visitan primero todos
los nodos adyacentes a v, luego todos los que están a distancia 2 (y no
visitados), a distancia 3, y así sucesivamente hasta recorrer todos los
nodos.
aqui un video de busqueda por amplitud
ejemplo:
Búsqueda en profundidad: Es equivalente a un recorrido
en preorden de un árbol. Se elige un nodo v de partida. Se marca
como visitado y se recorren los nodos no visitados adyacentes a v,
usando recursivamente la búsqueda primero en profundidad.
video de busqueda por profundidad
ejemplo:
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.
Recorrido por profundidad desde Vértice D= {D, C, R, H, T, A, B}
PD: El recorrido puede ser para grafos dirigidos o no dirigidos
ejemplos de grafos por videos: