Download topicosalgortclase6

Árboles
Grafo que no contiene ciclos, es
decir es un grafo también acíclico,
pero a su vez es conexo.
Bosques
• Los bosques de árboles son
un caso similar a los árboles,
son acíclicos, pero no son
conexos
Grafo Conexo
• Un grafo conexo es un
grafo no dirigido de modo
que para cualquier par de
nodos existe al menos un
camino que los une".
Árbol enraizado
• Un árbol enraizado es un árbol
libre con un vértice (o nodo)
distinguido denominado raíz.
• Si existe un camino de
nodo x a un nodo y en
árbol T, se dice que x
antecesor de y, y que y
sucesor de x.
un
un
es
es
• Si (x, y) es el último arco en el
camino desde la raíz r del árbol T
hasta el nodo y, entonces x es el
padre de y, e y es el hijo de x.
• La raíz es el único nodo en T que
no tiene padre.
• Si dos nodos
tienen el mismo
padre
son
hermanos.
• Un nodo sin hijos lo
denominaremos hoja.
• El resto son nodos internos.
• El grado de un nodo es el número
de hijos que tiene.
• Se llama profundidad de un nodo a
la longitud del camino desde la raíz
hacia ese nodo.
• La altura de un árbol es la
profundidad
del
nodo
más
profundo.
ÁRBOLES BINARIOS
Un árbol binario es un árbol en el que el
máximo número de hijos de cada nodo
es 2 (hijo izquierdo e hijo derecho).
Representación de expresiones
algebraicas ((a-6)*b)/(c-a)
Árbol y árbol ordenado
• Un árbol binario es:
–Lleno si todos los nodos tienen
2 hijos no vacíos excepto los
del último nivel que son hojas.
–Completo
• cada nivel i, o<i<h-1 tiene 2
nodos
• Los nodos del nivel h-1 con
hijos están a la izquierda.
• No existen hijos únicos
Un árbol binario es:
• Homogéneo si cada nodo
tiene 0 o 2 hijos
Recorridos de árboles binarios
• A veces puede interesar un
recorrido sistemático y eficiente
de todos los nodos del árbol
Coste de todos los algoritmos q(n),
siendo n el número de nodos del árbol
después de la llamada inicial, la
función se llama recursivamente
exactamente 2 veces para cada nodo
del árbol: una vez para su hijo
izquierdo y otra para su hijo derecho.
Recorridos de árboles binarios:
Inorden
• La clave de la raíz se imprime
entre los valores de su
subárbol izquierdo y derecho.
Inorden
Recorridos de árboles binarios
Postorden
• La clave de la raíz se imprime
después de los valores de sus
subárboles
Postorden
Recorrido de árboles binarios:
Preorden
• La clave de la raíz se
imprime antes de los
valores de sus subárboles.
Recorrido en
preorden
Ejemplo de árboles binarios: árbol
de expresiones
• Utilización de la estructura AB
para representar expresiones
aritméticas con operadores
binarios
• Raíz: operador principal
• Nodos internos: operadores de
subexpresiones
• Hojas: operandos
• (niveles: precedencia relativa de
evaluación)
Recorridos de grafos
• Método para recorrer de forma
sistemática y eficiente un grafo.
•Recorrido en profundidad:
Generalización del recorrido en
preorden de un árbol
•Recorrido en amplitud:
Generalización del recorrido en
niveles de un árbol
• En todos los algoritmos de
recorrido
de
grafos
supondremos que el grafo está
implementado con listas de
adyacencia
Recorrido en profundidad de un grafo
Dado un grafo G = (V,A) y un v´ertice v 2 V ,
la estrategia de recorrido en profundidad
(Depth-First
Search
(DFS)),
explora
sistemáticamente las aristas de G de
manera que primero se visitan los vértices
adyacentes
a
los
visitados
más
recientemente.
De
esta
forma,
se
va
profundizando en el grafo; es decir,
alejándose progresivamente de v.
Este proceso continúa hasta
que
todos
los
vértices
alcanzables desde el vértice de
la llamada original han sido
descubiertos.
Esta
estrategia
admite
una
implementación simple de forma
recursiva y proporciona:
•Ordenamientos de los vértices.
•Clasificación de las aristas.
• Algunas aplicaciones:
• Calcular
un
posible
orden
topológico y comprobar si el grafo
es acíclico.
• Encontrar
las
componentes
fuertemente conexas de un grafo.
Recorrido en amplitud de un grafo
Dado un grafo G = (V,A) y un vértice s∊ V,
la estrategia de recorrido en amplitud o
en anchura (Breadth-First Search (BFS)),
explora sistemáticamente las aristas de
G de manera que primero se visitan los
vértices más cercanos a v.
Algunos algoritmos importantes de
grafos tienen una estructura similar
al BFS. Por ejemplo, el algoritmo
de Dijkstra para encontrar los
caminos más cortos desde un
vértice dado.
a distancia k + 1. El algoritmo BFS
explora todos los vértices a
distancia k del vértice origen s
antes de empezar a explorar los
vértices
Al igual que DFS, se utiliza un
vector de tipo “color” para marcar
los vértices del grafo como no
visitados (WHITE), visitándose
(GRAY) o ya visitados (BLACK)
También se genera un vector de
predecesores para obtener un
árbol.