Estructuras de Datos y Algoritmos de Grafos en Pascal: Complejidad e Implementación

Complejidad Algorítmica: Ecuaciones en Recurrencia

Ecuaciones tipo sustracción y división evaluadas según el Teorema Maestro:

• Sustracción: T(n) = a · T(n - b) + c · n^k (si 0 ≤ b)
  • Solución: O(n^k+1) si a = 1; O(a^{n div b}) si a > 1.
• División: T(n) = a · T(n / b) + c · n^k (si 1 ≤ b)
  • Solución:
    • O(n^k) si a < b^k
    • O(n^k · log_b a) si a = b^k
    • O(n^{log_b a}) si a > b^k

Definición de Tipos de Datos para Grafos en Pascal

Representación de un grafo mediante listas de adyacencia:

TYPE
  TListaAdy = ^TNodoAdy;
  TNodoAdy = RECORD
    destino: TNodo;
    peso: real;
    sig: TListaAdy;
  END;

  TGrafo = ^TNodoGrafo;
  TNodoGrafo = RECORD
    origen: TNodo;
    adyacentes: TListaAdy;
    sig: TGrafo;
  END;

Funciones de Verificación y Propiedades de Grafos

Función EsArbol

FUNCTION EsArbol(g: TGrafo): boolean;
BEGIN
  EsArbol := EsConexo(g) AND NOT TieneCiclo(g);
END;

Función EsConexo

FUNCTION EsConexo(g: TGrafo): boolean;
VAR
  l: TLista;
  c: TConjNodos;
BEGIN
  Anchura(g, l);
  Nodos(g, c);
  IF Cardinal(c) = Longitud(l) THEN
    EsConexo := TRUE
  ELSE
    EsConexo := FALSE;
END;

Función TieneCiclo

FUNCTION TieneCiclo(g: TGrafo): boolean;
VAR
  n: TNodo;
  visitados, c: TConjNodos;
BEGIN
  IF NOT EsVacio(g) THEN
  BEGIN
    Nodos(g, c);
    Elegir(c, n);
    CrearConjVacio(visitados);
    TieneCiclo := TieneAux(g, n, n, visitados);
  END
  ELSE
    TieneCiclo := FALSE;
END;

Función TieneAux

FUNCTION TieneAux(g: TGrafo; ant, actu: TNodo; VAR visit: TConjNodos): boolean;
VAR
  c: TConjNodos;
  encont: boolean;
  n: TNodo;
BEGIN
  encont := FALSE;
  Poner(actu, visit);
  Adyacentes(g, actu, c);
  Quitar(ant, c);
  WHILE NOT EsVacio(c) AND NOT encont DO
  BEGIN
    Elegir(c, n);
    Quitar(n, c);
    IF Pertenece(n, visit) THEN
      encont := TRUE
    ELSE
      encont := TieneAux(g, actu, n, visit);
  END;
  TieneAux := encont;
END;

Función ExisteCamino

FUNCTION ExisteCamino(g: TGrafo; n1, n2: TNodo): boolean;
VAR
  l: TLista;
BEGIN
  Anchura(g, n1, l);
  ExisteCamino := Pertenece(n2, l);
END;

Recorridos y Transformaciones

Procedimiento Profundidad

PROCEDURE Profundidad(g: TGrafo; n: TNodo; VAR l: TLista);
VAR
  c: TConjNodos;
  n2: TNodo;
  p: TPila;
BEGIN
  CrearVacia(l);
  Nodos(g, c);
  Elegir(c, n);
  CrearVacia(p);
  Apilar(n, p);
  WHILE NOT EsVacia(p) DO
  BEGIN
    Cima(p, n);
    Desapilar(p);
    IF NOT Pertenece(n, l) THEN
    BEGIN
      InsertarFinal(n, l);
      Adyacentes(g, n, c);
      WHILE NOT EsVacio(c) DO
      BEGIN
        Elegir(c, n2);
        Quitar(n2, c);
        Apilar(n2, p);
      END;
    END;
  END;
END;

Procedimiento Arb2Graf

Convierte un árbol binario en un grafo dirigido:

PROCEDURE Arb2Graf(a: TArbin; VAR g: TGrafo);
VAR
  hi, hd: TArbin;
  e, r: TElem;
  arco: TArco;
BEGIN
  IF NOT EsVacio(a) THEN
  BEGIN
    Raiz(a, r);
    HI(a, hi);
    HD(a, hd);
    InsertarNodo(r, g);
    IF NOT EsVacio(hi) THEN
    BEGIN
      Raiz(hi, e);
      CrearArco(r, e, arco);
      InsertarArco(g, arco);
      Arb2Graf(hi, g);
    END;
    IF NOT EsVacio(hd) THEN
    BEGIN
      Raiz(hd, e);
      CrearArco(r, e, arco);
      InsertarArco(g, arco);
      Arb2Graf(hd, g);
    END;
  END;
END;

Operaciones de Modificación del Grafo

Procedimiento InsertarArco

PROCEDURE InsertarArco(VAR g: TGrafo; a: TArco);
VAR
  n1, n2: TNodo;
  encon: boolean;
  aux: TGrafo;
  aux2, nuevo: TListaAdy;
BEGIN
  Ex1(a, n1);
  Ex2(a, n2);
  InsertarNodo(g, n1);
  InsertarNodo(g, n2);
  aux := g;
  WHILE NOT Igual(n1, aux^.origen) DO
    aux := aux^.sig;
  encon := FALSE;
  aux2 := aux^.adyacentes;
  WHILE (aux2 <> NIL) AND NOT encon DO
  BEGIN
    IF Iguales(aux2^.destino, n2) THEN
      encon := TRUE
    ELSE
      aux2 := aux2^.sig;
  END;
  IF encon THEN
    aux2^.peso := Valor(a)
  ELSE
  BEGIN
    new(nuevo);
    Asignar(n2, nuevo^.destino);
    nuevo^.peso := Valor(a);
    nuevo^.sig := aux^.adyacentes;
    aux^.adyacentes := nuevo;
  END;
END;

Procedimiento Arcos

PROCEDURE Arcos(g: TGrafo; VAR c: TConjArcos);
VAR
  aux: TGrafo;
  aux2: TListaAdy;
  a: TArco;
BEGIN
  CrearVacio(c);
  aux := g;
  WHILE aux <> NIL DO
  BEGIN
    aux2 := aux^.adyacentes;
    WHILE aux2 <> NIL DO
    BEGIN
      CrearArco(aux^.origen, aux2^.destino, aux2^.peso, a);
      Poner(a, c);
      aux2 := aux2^.sig;
    END;
    aux := aux^.sig;
  END;
END;

Procedimiento BorrarNodo

PROCEDURE BorrarNodo(VAR g: TGrafo; n: TNodo);
VAR
  c: TConjArcos;
  n1, n2: TNodo;
  arco: TArco;
  ant, exp: TGrafo;
  encon: boolean;
BEGIN
  Arcos(g, c);
  WHILE NOT EsVacio(c) DO
  BEGIN
    Elegir(c, arco);
    Quitar(arco, c);
    Ex1(arco, n1);
    Ex2(arco, n2);
    IF Igual(n1, n) OR Igual(n2, n) THEN
      BorrarArco(g, arco);
  END;
  exp := g;
  ant := NIL;
  encon := FALSE;
  WHILE (exp <> NIL) AND NOT encon DO
  BEGIN
    IF Igual(n, exp^.origen) THEN
      encon := TRUE
    ELSE
    BEGIN
      ant := exp;
      exp := exp^.sig;
    END;
  END;
  IF encon THEN
  BEGIN
    IF ant = NIL THEN
      g := g^.sig
    ELSE
      ant^.sig := exp^.sig;
    dispose(exp);
  END;
END;

Procedimiento BorrarArco

PROCEDURE BorrarArco(VAR g: TGrafo; a: TArco);
VAR
  n1, n2: TNodo;
  aux: TGrafo;
  encon: boolean;
  exp, ant: TListaAdy;
BEGIN
  Ex1(a, n1);
  Ex2(a, n2);
  aux := g;
  encon := FALSE;
  WHILE (aux <> NIL) AND NOT encon DO
  BEGIN
    IF Igual(aux^.origen, n1) THEN
      encon := TRUE
    ELSE
      aux := aux^.sig;
  END;
  IF encon THEN
  BEGIN
    encon := FALSE;
    exp := aux^.adyacentes;
    ant := NIL;
    WHILE (exp <> NIL) AND NOT encon DO
    BEGIN
      IF Igual(n2, exp^.destino) THEN
        encon := TRUE
      ELSE
      BEGIN
        ant := exp;
        exp := exp^.sig;
      END;
    END;
    IF encon THEN
    BEGIN
      IF ant = NIL THEN
        aux^.adyacentes := exp^.sig
      ELSE
        ant^.sig := exp^.sig;
      dispose(exp);
    END;
  END;
END;