Kruskal

📖

El algoritmo de Kruskal sirve para crear el arbol de expansión mínima (ARM) de un grafo

A diferencia de Prim, kruskal no hace un recorrido por el grafo, sino que este partirá de un subgrafo sin aristas, e irá añadiendo aristas de forma que en cada paso se reduzca en 1 el número de componentes conexas del grafo hasta tener una sola

En caso de ser no conexo, al algoritmo parará cuando no puede encontrar una arista que reduzca el número de componentes conexas

ℹ️

Pasos

Inicialización
Se crea una lista de aristas ordenada por peso
Se crea una bolsa donde el valor de cada posición representa la componente_conexa a la que pertenece el nodo
Se crea el array de aristas que forman parte de la solucion

Bucle iterativo
Se recorrerá el bucle hasta que no queden más aristas que añadir ó hasta que ya se hayan unido todos los nodos en un única componente conexa
Se extrae la primera arista de la lista ordenada
Si los nodos que conecta la arista (origen y destino) ya pertenecen a la misma componente conexa, se hace un salto hasta la siguiente iteración
Se unifican los nodos de ambas componentes conexas en una sola
Se añade la arista al array solución

##################################################################
# Kruskal algorithm to find the minimum spanning tree of a graph #
##################################################################


def sortCandidates(graph):            
    """
    Given a graph, represented as a list of tuples, where each tuple is (weight, src, dest), this function will return a list of all the edges but sorted by weight, then by src, then by dest
    """
    # Flatten the list of edges
    sorted = [edge for vertex in graph for edge in vertex]
    # Sort by weight, then by src, then by dest
    sorted.sort()
    # Return the sorted list of edges [(weight, src, dest), ...]
    return sorted


def joinConexComponents(conexComponents, newComp, oldComp):
    """
    Being `conexComponents` a list of labels for each vertex, `newComp` and `oldComp` are the labels of the components to join, this function will rename all the components with the label `oldComp` to `newComp`
    """
    for j in range(1, len(conexComponents)):
        if conexComponents[j] == oldComp:
            conexComponents[j] = newComp


def kruskal(graph):
    """
    Greedy Kruskal algorithm
    It returns the total weight of the minimum spanning tree and the ordered edges that are part of the minimum spanning tree. 
    The graph must follow the format [(weight, src, dest), ...]
    """
    totalW = 0 # Total weight of the minimum spanning tree
    candidates = sortCandidates(graph) # List of all the edges sorted by weight, then by src, then by dest with format (weight, src, dest)
    conexComponents = list(range(len(graph))) # List of labels for each vertex
    orderedEdges = [] # List of ordered edges that are part of the minimum spanning tree
    
    # Greedy loop
    i = 0
    while i < len(candidates) and len(conexComponents) > 1:
        weight, src, dest = candidates[i]
        
        # If the current edge is not creating a cycle, then add it to the minimum spanning tree
        if conexComponents[src] != conexComponents[dest]:
            totalW += weight
            joinConexComponents(conexComponents, conexComponents[src], conexComponents[dest])
            orderedEdges.append(candidates[i])
            
        i += 1

    return totalW, orderedEdges


#################################################################### EXAMPLE ####################################################################


# Refactor the graph to fit the algorithm expected input format: [(weight, src, dest), ...]
def formatEdges(g):
    newG = []
    for i in g:
        newG.append([])
        for src, dst, w in i:
            newG[-1].append((w, src, dst))
    
    return newG


### MAIN LOOP ###
if __name__ == "__main__":
    g = [
        [],
        [(1, 3, 1), (1, 4, 2), (1, 7, 6)],
        [(2, 5, 2), (2, 6, 4), (2, 7, 7)],
        [(3, 1, 1), (3, 4, 3), (3, 7, 5)],
        [(4, 1, 2), (4, 3, 3), (4, 5, 1), (4, 6, 9)],
        [(5, 2, 2), (5, 4, 1), (5, 7, 8)],
        [(6, 2, 4), (6, 4, 9)],
        [(7, 1, 6), (7, 2, 7), (7, 3, 5), (7, 5, 8)]
    ]
    
    sol, edges = kruskal(formatEdges(g))
    print(sol, edges)