Algoritmos de grafos

Los problemas de grafos son muy frecuentes en los concursos de programación. Para resolver un problema de grafos, la dificultad no es tanto implementar el algoritmo, sino identificar correctamente el tipo de problema de qué se trata. Los algoritmos no se necesitan memorizar, sino que se pueden llevar en forma de código al concurso (véase el "notebook").

Sin embargo, en esta clase vamos a ver un par de ejemplos de cómo implementar los algoritmos de grafos. Antes que nada, es muy común nombrar los nodos del grafo 0,...,N, ya que podemos usar el nombre de cada nodo como índice en un vector o una matriz.

Representaciones de grafos

Hay tres maneras comunes para representar los grafos; vamos a tomar el siguiente grafo como ejemplo:

Ejemplo de un grafo

  1. Matriz de adyacencia: las aristas del grafo se guardan en una matriz, indicando si un nodo tiene enlace directo con otro.

    O\D 0 1 2 3 4 5
    0 0 1 0 1 0 0
    1 0 0 1 0 1 0
    2 0 0 0 0 1 0
    3 0 1 0 0 0 0
    4 0 0 0 1 0 1
    5 0 0 1 0 0 0

    En C++, podemos usar un doble array para guardar la matriz de antes:
    
    int A[6][6];
    //inicializar todo a 0
    for(int i=0;i<6;i++)
       for(int j=0;j<6;j++)
          A[i][j] = 0;
    //1 si hay enlace origen -> destino
    A[0][1] = 1;
    A[1][2] = 1;
    A[1][4] = 1;
    A[2][4] = 1;
    A[3][1] = 1;
    A[4][3] = 1;
    A[4][5] = 1;
    A[5][2] = 1;
    

  2. Lista de adyacencia: para cada nodo, sólo se guardan sus vecinos.

    0 -> 1 3
    1 -> 2 4
    2 -> 4
    3 -> 1
    4 -> 3 5
    5 -> 2

    En C++, podemos usar un vector de vectores para guardar la lista anterior:
    
    vector<vector<int> > A(6);
    //para cada posición origen añadir vecino
    A[0].push_back(1);
    A[0].push_back(3);
    A[1].push_back(2);
    A[1].push_back(4);
    A[2].push_back(4);
    A[3].push_back(1);
    A[4].push_back(3);
    A[4].push_back(5);
    A[5].push_back(2);
    

  3. Lista de aristas: se guarda una lista de todas las aristas del grafo.

    (0,1) (0,3) (1,2) (1,4) (2,4) (3,1) (4,3) (4,5) (5,2)

    En C++, podemos usar un vector de pares de enteros para guardar la lista:
    
    //librería para utilizar pair
    #include <utility>;
    //vector de aristas
    vector<pair<int,int> > A;
    //insertamos las aristas en el vector
    A.push_back(make_pair(0, 1));
    A.push_back(make_pair(0, 3));
    A.push_back(make_pair(1, 2));
    A.push_back(make_pair(1, 4));
    A.push_back(make_pair(2, 4));
    A.push_back(make_pair(3, 1));
    A.push_back(make_pair(4, 3));
    A.push_back(make_pair(4, 5));
    A.push_back(make_pair(5, 2));
    

Para grafos con costes, en la matriz de adyacencia simplemente se puede guardar el coste de cada arista. La lista de adyacencia tiene que incluir 2 valores para cada arista: el vecino y el coste, lo que se puede representar con pares de enteros. La lista de aristas tiene que incluir 3 valores para cada arista: los dos nodos y el coste. Se puede representar por un struct o combinando pares.

Algoritmos típicos

Los algoritmos de grafos que suelen aparecer son los típicos que se enseñan en Algebra Lineal y Matemática Discreta:

Implementar el algoritmo de Kruskal

Para implementar el algoritmo de Kruskal se puede aprovechar una estructura que se llama "Union-Find" o "Merge-Find", que representa una partición de un conjunto de valores (en este caso los nodos del grafo). La idea es mantener un árbol para cada subconjunto, tal que la raíz de cada árbol es el nodo representante para el subconjunto correspondiente.

Las únicas dos operaciones de la estructura son "Merge", que combina dos árboles en uno, y "Find", que devuelve el nodo representante para un nodo cualquiero. Para implementar esta estructura es suficiente recordar cuál es el padre de cada nodo, lo que se puede hacer con un simple array de enteros. Por defecto, la raíz de un árbol es su propio padre.

Inicialmente cada nodo pertenece a su propio subconjunto, lo que quiere decir que hay un árbol por nodo con este mismo nodo como raíz:


int mf[10];
for (int i = 0; i < 10; ++i)
   mf[i] = i;

Para encontrar el nodo representante de un nodo podemos simplemente consultar el padre del nodo, y recursivamente encontrar su representante hasta encontrar un nodo que es su propio padre (es decir, la raíz). Para optimizar futuras consultas se suele actualizar el padre de cada nodo en este camino para que coincida con la raíz:


int find(int n) {
   if (mf[n] == n) return n;
   else return mf[n] = find(mf[n]);
}

Finalmente, combinar dos árboles se puede hacer de manera muy sencilla. Dadas las dos raizes r1 y r2 de los dos árboles, podemos simplemente asignar r1 como padre de r2 (o al revez):


int merge(int r1, int r2) {
   mf[r2] = r1;
}

Ahora podemos implementar el algoritmo de Kruskal de la siguiente manera:

El algoritmo de Bellman Ford

Otro algoritmo común es uno que se llama Bellman Ford, que esencialmente es un Dijkstra para el caso de que se permiten aristas con coste negativo. El problema sigue siendo encontrar un camino de coste mínimo entre dos nodos del grafo. Sin embargo, el coste mínimo podría ser -∞ si hay ciclos de coste negativo que se pueden recorrer. Este caso se tiene que tratar aparte.

Igual que Kruskal, la mejor representación para Bellman Ford es la lista de aristas. El algoritmo se puede resumir de la siguiente manera:

Resolver problemas de grafos

En general, el proceso de resolver un problema de grafos se puede resumir de la siguiente manera:

  1. Identificar el tipo de problema y el algoritmo que se aplicará
  2. Escoger la representación del grafo (normalmente depende del algoritmo)
  3. Decidir cómo nombrar los nodos del grafo (de 0 a N)
  4. Leer la entrada y construir la representación del grafo
  5. Aplicar el algoritmo elegido
  6. Imprimir el resultado en el formato que se pide

Normalmente los pasos más difíciles son 1 y 4.

Problemas para resolver esta semana

Para resolver los problemas de esta semana podéis aprovechar los ejemplos de código. También podéis aprovechar los ejercicios para familiarizaros con las estructuras en C++, por ejemplo implementando vuestra propia búsqueda BFS con la estructura "list". Los problemas para resolver esta semana son:

Sencillos:

UVa logo 118 - Mutant Flatworld Explorers
UVa logo 336 - A Node Too Far
UVa logo 1148 - The mysterious X network
OIE logo Harrichu y el laberinto

Avanzados:

UVa logo 1160 - X-Plosives
UVa logo 1174 - IP-TV
UVa logo 12176 - Bring Your Own Horse
UVa logo 12202 - Haunted Graveyard
OIE logo Velocirráptors 101