TEMA 3: Tipos Abstractos de Datos: Árboles, Grafos.

• 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\).

• Un árbol vacío se representa por la letra griega \(\Lambda\).
• Los TADs Árbol se emplean p.e. en lugar de Listas cuando la cantidad de elementos almacenada es muy grande y el tiempo de acceso lineal es costoso.

Se suelen representar de este modo

• 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.

• Un camino de un nodo \(n_1\) a otro \(n_k\) se define como la secuencia de nodos \(n_1, n_2, ..., n_k\) tal que \(n_i\) es el padre de \(n_{i+1}\) , \(\forall i : 1 \le i < k\). Su longitud es el número de aristas que lo forman, \(k-1\).
• Existe un camino de longitud cero entre cada nodo y él mismo.
• En un Árbol hay sólo un camino de la raíz a cada nodo.

• Para un nodo \(n_i\) su profundidad es la longitud del camino único desde la raíz a ese nodo. Luego la profundidad de la raíz es \(0\).

• La altura de \(n_i\) es el camino más largo desde \(n_i\) a una hoja. Luego la altura de cualquier hoja es \(0\), y la altura de un Árbol es la altura de su raíz.
• La profundidad de un Árbol es la profundidad de la hoja más profunda, es decir, su altura.

• Si \(n_1 \ne n_2\) se dice que \(n_1\) es un antecesor propio de \(n_2\), y que \(n_2\) es un descendiente propio de \(n_1\).
• Los Árboles cuyos nodos pueden tener n hijos se denominan n-arios. El caso particular en el cual ningún nodo tiene más de dos hijos se denomina Árbol binario.
• Si hay un camino de \(n_1\) a \(n_2\) se dice que \(n_2\) es descendiente de \(n_1\) y a su vez \(n_1\) es el antecesor de \(n_2\).

• 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.

• La ordenación es útil en el caso de dos nodos cualesquiera entre los cuales no existe relación antecesor/descendiente. Entonces si a y b son hermanos y a está a la izquierda de b, entonces todos los descencientes de a están a la izquierda de b y de todos sus descendientes.

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

• Estos ordenamientos se definen recursivamente así:
  1. Si un Árbol A es nulo, entonces la lista vacía es el listado de los nodos de A en los órdenes previo, simétrico y posterior.
  2. Si A contiene un solo nodo, este único nodo es el listado de los nodos de A en los órdenes previo, simétrico y posterior.
  3. Pero si ninguno de los anteriores es el caso…

Sea A un Árbol con raíz \(n\) y subárboles \(A_1, A_2,...,A_k\) representado de este modo:

Entonces…

1. El listado en orden previo de los nodos de A está formado por la raíz de A, seguida de los nodos de \(A_1\) en orden previo, luego por los nodos de \(A_2\) en orden previo y así sucesivamente hasta los nodos de \(A_k\) en orden previo.
2. El listado en orden simétrico de los nodos de A está formado los nodos de \(A_1\) en orden simétrico, seguidos de \(n\), y detrás los nodos de \(A_2, ..., A_k\) con cada grupo de nodos en orden simétrico.

1. El listado en orden posterior de los nodos de A tiene los nodos de \(A_1\) en orden posterior, luego los de \(A_2\) en orden posterior y así sucesivamente hasta los de \(A_k\) en orden posterior y por último la raíz \(n\).

• 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.

• 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.

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;
};

Y la otra:

2. Node

class Node
{
public:
  Node                   (Element i)  { fItem = i; }
  ~Nodo                  (void)       {}

  Tree&    sibling       (int n)      { return fSiblings[n]; }
  Tree&    leftSibling   (void)       { return fSiblings[0]; }
  Tree&    rightSibling  (void)       { return fSiblings[1]; }
  Element& item          (void)       { return fItem; }

private:
  Element fItem;
  Tree fSiblings[2];            // Como máximo 2 hijos
};

• 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 órden, 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.

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

Árbol resultado de insertar por este orden: \(8, 5, 9, 4, 1, 6, 2\)

• 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.

• 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.
• Pega: excesivo consumo de memoria. Sin embargo es válida si el grafo es denso: \(\mid A \mid\ \simeq\ {\mid V \mid}^2\).

• 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.

El siguiente grafo:

Produce esta lista de adyacencia:

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;
}

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
        }
    }

Si aplicamos Dijkstra a este grafo:

• 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.

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.

Aplicar Prim al siguiente grafo:

Produce en este orden estas aristas: T = { (1,3) , (3,6), (6,4) , (3,2) , (2,5) }

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.

Aplicar Kruskal al siguiente grafo:

Produce en este orden estas aristas: T = { (1,3) , (4,6), (2,5) , (3,6) , (3,2) }

• Vamos a ver el algoritmo de búsqueda en profundidad.

• Es una generalización del recorrido en orden previo de un árbol.

  bool visited[N];               // N = numero de nodos del grafo
  for i = 0..N-1
    visited[i] = false;
  
  for i = 0..N-1
    if not visited[i]
      dfs (i);
  
  void dfs (Vertex v) {
     Vertex w;
  
     visited[v] = true;
     for w in L[v]                // Para todo nodo w adyacente a v
       if not visited[w]
         dfs (w);
  }
  

• 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.