Grafos 2ª parte: El algoritmo de Kruskal

Antes he hablado del algoritmo de Prim que nos da el árbol de recubrimiento mínimo de un grafo conexo, no dirigido y con coste para sus aristas. Y ahora hablaré del algoritmo de Kruskal que resuelve la misma clase de problema que el de Prim, salvo que en esta ocasión no partimos desde ningún nodo elegido al azar. Para resolver el mismo problema lo que hacemos es pasarle a la función una lista con las aristas ordenada de menor a mayor, e iremos tomando una para formar el ARM. En un principio cada nodo está en un digamos grupo distinto, al elegir una arista de la lista miraremos si no están los nodos conectados ya en el mismo grupo, de no estarlo fusionamos ambos grupos y comprobamos si hemos encontrado ya la solución, para devolver el resultado.

const int I = int.MaxValue; // Infinito

struct Arista {
    public int origen;
    public int destino;
    public int coste;

    public Arista(int o, int d, int c) {
        this.origen = o;
        this.destino = d;
        this.coste = c;
    }

    public override string ToString() {
        char aux = 'A';
        return "(" + (char)(aux + origen) + ", " +
                (char)(aux + destino) + "; " +
                coste.ToString() + ")";
    }
}

static IEnumerable<Arista> ObtenerLista(int[,] grafo, int tam) {
    List<Arista> lista = new List<Arista>();
    for(int i = 0; i < tam; i++) {
        for(int j = i + 1; j < tam; j++) {
            if(grafo[i, j] != I) {
                lista.Add(new Arista(i, j, grafo[i, j]));
            }
        }
    }
    return lista.OrderBy(x => x.coste);
}

public static void Resolver() {
    const int numNodos = 7;
    int[,] grafo =
    { // A  B  C   D   E   F   G
        {I, 7, I,  5,  I,  I,  I}, // A
        {7, I, 8,  9,  7,  I,  I}, // B
        {I, 8, I,  I,  5,  I,  I}, // C
        {5, 9, I,  I, 15,  6,  I}, // D
        {I, 7, 5, 15,  I,  8,  9}, // E
        {I, I, I,  6,  8,  I, 11}, // F
        {I, I, I,  I,  9, 11,  I}  // G
    };

    IEnumerable<Arista> lista = ObtenerLista(grafo, numNodos);
    List<Arista> arm = CalcKruskal(lista, numNodos);
    Console.WriteLine("ARM: " +
                      arm.Select(x => x.ToString())
                         .Aggregate((x, xs) => x + " " + xs));
}

Esta es la base del programa, con el tipo de datos Arista que ya vimos en la anterior entrada y con la función ObtenerLista, que toma la matriz de adyacencia recorriendo el triángulo superior, para obtener todas las aristas y devolverlas ordenadas por coste. Siendo un grafo no dirigido, da igual que nodo sea el origen o cuál el destino.

static bool NoConectados(Arista a, int[] cc) {
    return cc[a.origen] != cc[a.destino];
}

static void Conectar(Arista a, int[] cc, int tam) {
    int identif = cc[a.origen];
    int víctima = cc[a.destino];
    for(int i = 0; i < tam; i++) {
        if(cc[i] == víctima) {
            cc[i] = identif;
        }
    }
}

static bool Solución(int[] cc, int tam) {
    for(int i = 1; i < tam; i++) {
        if(cc[0] != cc[i]) return false;
    }
    return true;
}

static List<Arista> CalcKruskal(IEnumerable<Arista> lista,
                                int tam) {
    List<Arista> arm = new List<Arista>();
    int[] cc = Enumerable.Range(0, tam).ToArray();
    foreach(Arista a in lista) {
        if(NoConectados(a, cc)) {
            arm.Add(a);
            Conectar(a, cc, tam);
            if(Solución(cc, tam)) {
                return arm;
            }
        }
    }
    return arm;
}

Como se puede ver, este algoritmo es más sencillo, entre otras cosas porque tenemos los datos ya ordenados para procesarlos. Simplemente comprobamos si dos nodos son del mismo grupo y si no lo son, añadimos la arista y fusionamos los grupos, esto consiste en coger el número identificador de uno, para sustituir el del otro con ese valor. Si tenemos una solución antes de haber mirado todas las aristas, que es lo más probable que puede ocurrir, devolvemos el ARM y terminamos con el algoritmo. Y aquí acaban los problemas relacionados con los ARM, pero no con los grafos, porque todavía queda un último algoritmo de búsqueda de caminos bastante famoso, el algoritmo de Dijkstra.

About these ads

Deja un comentario

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: