TEMA 3: Tipos Abstractos de Datos

Árboles

• Es un TAD que representa una colección de elementos llamados nodos.
• Uno de estos nodos es especial, nos referimos a él como la raíz del árbol.
• Entre los nodos hay una relación de paternidad la cual impone una estructura jerárquica sobre ellos.

Definición

• El TAD Árbol se suele definir de manera recursiva:
  1. Un sólo nodo es por sí mismo un árbol. Este nodo es la raíz del árbol.
  2. Dado un nodo $n$ y una serie de árboles $A_1, A_2, ... , A_k$ con raíces $n_1, n_2, ..., n_k$, podemos crear un nuevo árbol haciendo que $n$ sea el padre de los nodos $n_1, n_2, ..., n_k$. Decimos entonces que $n$ es la raíz del nuevo árbol, $A_1, ..., A_k$ son subárboles de la raíz y a los nodos $n_1, n_2, ..., n_k$ son hijos del nodo $n$.

Aspecto

Se suelen representar de este modo

Conceptos

• Si r es la raíz de un Árbol se dice que cada subárbol es un hijo de r y que r es el padre de la raíz de cada uno de los subárboles.
• En un Árbol con $n$ nodos hay $n-1$ aristas.
• En principio cada nodo puede tener un número arbitrario de hijos, incluso $0$.
• Los nodos sin hijos se llaman hojas.
• Los nodos con el mismo padre son hermanos.

Orden de los nodos

• Los hijos de un nodo pueden estar ordenados o no.
• Caso de estarlo, se suele hacer de izquierda a derecha.
• Si no se ordenan por ningún criterio el Árbol se llama no ordenado.

Recorrido ordenado de un Árbol

• Tenemos varias formas de recorrer ordenadamente un Árbol.
• Pre-orden -orden previo- , In-orden -orden simétrico- y Post-orden -orden posterior-.

Árboles. Operaciones básicas

• Parent (n) : Devuelve el padre del nodo n. Si n es la raíz (no tiene padre) se devuelve $\Lambda$. En este caso podemos interpretar $\Lambda$ como un nodo nulo que indica que se ha salido del árbol.
• LeftMostChild (n) : Devuelve el hijo más a la izquierda del nodo n o $\Lambda$ si n es una hoja (no tiene hijos).

Árboles. Implementación

Mediante vectores

• Necesitamos numerar los nodos del árbol: $0, 1, 2, ..., n$.
• Creamos un vector $L$ de enteros donde el índice $i$ representa al nodo actual y su contenido $j$ es el índice en el vector de su padre.
• El nodo que representa la raíz tiene asignado el valor $0$.
• Según esto si $L[i] = j$, entonces $j$ es el padre del nodo $i$ y $L[i] = 0$ si el nodo $i$ es hijo de la raíz.
• Esta representación complica la implementación de determinadas operaciones, por lo que emplearemos otra.

Mediante listas de hijos

• Cada nodo mantiene una lista de sus nodos-hijo.
• Si el número máximo de hijos es fijo, podríamos incluso usar un vector de nodos.

Clases necesarias para la representación

Necesitamos al menos dos clases de Alto Nivel:

1. Tree

typedef char Element;           // Hasta que veamos genericidad...

class Tree
{
public:

  Tree        (void) { fRoot = nullptr; }
  ~Tree       (void);

  void insert (const Element &i);

private:
  NodePtr fRoot;
};

Árboles binarios

• Se trata de un tipo especial de árbol. Algunos de los ejemplos que hemos visto previamente usan este tipo de árboles.
• Un nodo tiene como máximo dos hijos.
• A estos hijos se les llama hijo izquierdo (LeftSibling) e hijo derecho (RightSibling).
• A menudo se emplean estableciendo una relación de orden, el dato del hijo izquierdo es menor que el dato de su padre, y el dato del hijo derecho es mayor que el dato del padre.

Árboles binarios

• Esto permite hacer inserciones automáticas en base a la etiqueta del nodo nuevo insertado.
• Por ejemplo, si insertamos en un árbol binario ordenado de enteros la secuencia de números ($8, 5, 9, 4, 1, 6, 2$) obtendríamos el árbol:

Árboles de otros tipos.

• Los árboles n-arios o la particularización llamada árbol binario no son los únicos tipos de árboles.
• Es interesante que eches un vistazo a estos otros tipos de árboles y que veas por qué se caracterizan:
  • Árboles AVL.
  • Árbol biselado o desplegado.
  • Árboles B.

Grafos

• En problemas de disciplinas como la informática, las matemáticas, diversas ingenierías, etc… a menudo necesitamos representar relaciones (de distinto tipo) entre objetos.
• Estas relaciones podemos plasmarlas mediante el uso de una estructura de datos conocida como Grafo.
• A grandes rasgos un grafo es un conjunto de vértices y uno de aristas que conectan esos vértices.

Grafos. Definiciones

• Un grafo $G$ se define como un par $G = ( V, E )$, donde $V$ es un conjunto de vértices y $E$ es un conjunto de aristas.
• Cada arista (o arco ) es, a su vez, un par $( v, w ) : v,w \in V$. Si este par es ordenado, entonces el grafo es dirigido (digrafo ).

• Un vértice $w$ es adyacente a otro $v$ $\iff (v, w) \in E$.
  

  Aclaración : $(p \iff q) \equiv (p \rightarrow q) \wedge (q \rightarrow p)$.

Grafos. Operaciones básicas

• First (v): Devuelve el índice del primer vértice adyacente a v. Si no hay ninguno, se devuelve un valor que represente un vértice nulo.
• Next (v, i): Devuelve el índice posterior a i de entre los vértices adyacentes a v. Si i es el último índice de los vertices adyacentes a v se devuelve un valor que represente un vértice nulo.
• Vertex (v, i): Devuelve el vértice cuyo índice i está entre los vértices adyacentes a v.

Grafos. Implementación

Usaremos grafos dirigidos, los no dirigidos se pueden representar de manera similar.

Matriz de adyacencia

• Una primera representación consiste en hacer uso de una matriz de adyacencia.
• Se trata de una matriz bidimensional, llamése $a$, donde para cada arista $(u,v)$ del grafo hacemos $a[u][v] = 1$, y si no existe dicha arista $a[u][v] = 0$.
• Si la arista tiene un peso asociado $p$ : $a[u][v] = p$. En estos casos podemos usar un peso muy grande o muy pequeño ($\infty, -\infty$) para indicar que una arista no existe.

Lista de adyacencia

• Si el grafo no es denso (disperso ) se usa una lista de adyacencia.
• Cada vértice mantiene una lista de todos los vértices adyacentes.
• Por lo tanto el espacio necesario de almacenamiento pasa a ser $\simeq\ \mid A \mid + \mid V \mid$.
• De este modo, una operación muy habitual en grafos como es encontrar todos los vértices adyacentes a uno dado consiste en recorrer la lista de adyacencia del vértice en cuestión.

Ejemplo

El siguiente grafo:

Grafos. Tipos de problemas

Conectividad:

Consiste en saber decir si un grafo es conexo o no. Se trata de un problema básico ya que la solución a algunos otros problemas dependen de esta respuesta.

Alcanzabilidad:

El problema de la alcanzabilidad está relacionado con la conexión. En él se nos dan un grafo $G(V, E)$, un vértice origen $s \in V$ y un vértice destino $d \in V$ y tenemos que decir si existe un camino de $s$ a $d$ ($s \rightsquigarrow d$).

Grafos. Algoritmos

Ordenación topologica

Asigna un orden lineal a los vértices de un GDA de manera que si existe una arista de $i \rightarrow j$, entonces $i$ aparece antes que $j$ en el ordenamiento lineal.

Algoritmo:

int[] topologicalOrder (Graph g) {
   for cont = 0..|V|-1 {
      v = vertInDegree0();      // Nuevo vertice grado entrada == 0
      if (v < 0) error ("ciclo");
      else {
        num_top[v] = cont;      // Vertice 'v' ocupa la posicion 'cont' en el orden topologico
        for w adjacent to v     // Eliminamos 'v' del grafo.
          --inDegree[w];
      }
   }
   return num_top;
}

Camino más corto en grafo ponderado desde un sólo origen

Algoritmo:¹

// Asume que no hay etiquetas negativas asociadas a ninguna arista
    void Dijkstra(Graph G, vector<Weight>& D) { // Comenzamos en 1 el indice en vectores y matrices
        S = {1};                   // Nodo 1 guardado en conjunto S
        for i = 2 .. n
             D[i] = C[1][i];       // Inicializamos D con el coste de ir de 1..i
        for i = 1 .. n-1 {
             -seleccionamos w en V-S tal que D[w] es un minimo;
             -añadimos w a S;
             foreach vertex v en V-S
                  D[v] = min(D[v], D[w] + C[w][v]); // C[w][v] == INFTY si no existe w->v
        }
    }

Árbol de expansión mínima

• Un árbol de expansión de un grafo no dirigido $G = (V, E)$ es un árbol formado por todos los vértices de $G$ y algunas de (pueden ser todas) las aristas de $G$, de manera que no hay ciclos.
• Si cada arista $(u, v)$ $\in E$ tiene asociado un peso ($G$ es ponderado), al árbol de expansión cuyas aristas pesan lo mínimo, se le llama arbol de expansión mínima.

Árbol de expansión mínima. Prim

Algoritmo: La entrada al agoritmo la constituyen el grafo $G$ y la salida se devuelve en T que es un conjunto de aristas.

void Prim (Graph G, set<Edge>& T) {
  set<Vertex> U;
  Vertex u, v;

  T = {};
  U = {1};
  while U != V {
    (u, v) arista con coste mínimo tal que u esta en U y v en V-U;
    T = T + {(u, v)};
    U = U + {v};
  }
}

• Y aquí encontrarás una explicación de su funcionamiento.

Árbol de expansión mínima. Kruskal

Algoritmo:

void Kruskal (Graph G, set<Edge>& T)
{
   T = {};
   V;                           // todos los Arcos del grafo G
   Mientras (T contenga menos de n-1 arcos y V != {}) {
      De las aristas en E seleccionar la de menor coste (i,j)
      V = V - {(i,j)};
      Si el nodo-i y el nodo-j no están en el mismo árbol entonces
         T = T + {(i,j)}
   }
}

• Y aquí encontrarás una explicación de su funcionamiento.

Recorrido. Búsqueda en profundidad

• Vamos a ver el algoritmo de búsqueda en profundidad.
• Es una generalización del recorrido en orden previo de un árbol.

Visualización de grafos

• Te puede resultar interesante este software: Graphviz.
• Con él puedes describir mediante un lenguaje formal grafos y otros tipos de información estructural.
• Echa un vistazo a la colección de ejemplos que hay en su página.
• Los grafos y árboles que aparecen en este tema están hechos con Graphviz. La herramienta empleada ha sido dot.

Aclaraciones

• Este contenido no es la bibliografía completa de la asignatura, por lo tanto debes estudiar, aclarar y ampliar los conceptos que en ellas encuentres empleando los enlaces web y bibliografía recomendada que puedes consultar en la página web de la ficha de la asignatura y en la web propia de la asignatura.