Ordenación Topológica

📖

La ordenación topológica de un grafo acíclico dirigido (GAD) es una ordenación lineal donde todos los nodos que tienen aristas entrantes aparecerán siempre después del nodo donde se origina la arista en la ordenación

Este tipo de ordenación es útil en situaciones donde necesitas realizar tareas en un cierto orden, como en la planificación de proyectos

ℹ️

El algorimo consiste en:

Calculamos la cantidad de aristas entrantes de cada nodo

Sacamos de la lista los nodos iniciales, los cuales son aquellos que no tienen niguna arista entrante. Estos nodos los añadiremos a la lista cola

Desde este punto, ejecutaremos en bucle un código que saque de la el primer nodo de la cola (se recomienda ordenar primero la cola)

Dicho nodo, lo añadiremos a la lista final de la ordenación
Iteraremos la lista de adyacentes del nodo, decrementando para cada uno de los vecinos el contador de aristas adyacentes (ya que al añadir el nodo en el paso a, hemos resuelto una dependencia)
Si la cantidad de aristas adyacentes del nodo vecino, ahora es cero, lo añadiremos a la cola

Este algoritmo devuelve una lista de los nodos del grafo siguiendo estos una ordenación topológica

🧠 Complejidad → $O(n)$
Siendo $n$ la suma de la cantidad de vertices y aristas

⚠️

Al ser un tipo de recorrido, si el grafo es no conexo, el recorrido solo contendrá los nodos de la misma componente conexa

💡

Este algoritmo no necesita una lista de nodos visitados, ya que los nodos solo se añaden a la cola cuando hemos resuelto todas las dependencias de esta (todas las aristas entrantes) por lo que, de forma implícita, la lista de aristas entrantes hace de lista de visitados.

Un nodo solo se recorre cuando su valor en la lista de dependencias es 0, lo cual a su vez nos asegura que ya no aparece en ninguna lista de adyacencias de los nodos que quedan por recorrer

##########################################
# Topological Sort Algorithm (iterative) #
##########################################

def topo_sort(g):
    """
    This algorithm orders de nodes based on the least dependencies from others.

    The algorithm takes as candidates the nodes that don't and in-edges, or that their parent node has been already
    added to the topological sort result list
    """
    n = len(g)              # Length of the graph
    result = []             # Resulting order calculated by the algorithm
    in_degree = [0] * n     # Array to count the number of in-edges of each node (dependency list)
    candidates = []         # Nodes that don't have in-edges, or those have been already added to the result

    # Count the in-edges of each node
    for node in range(n):
        for adj in g[node]:
            in_degree[adj] += 1

    # Fill the candidates list with its initial values (nodes with no in-edges)
    for node in range(n):
        if in_degree[node] == 0:
            candidates.append(node)

    # Main loop
    while candidates:
        candidates.sort()                   # Sort the current candidates to follow a lexicographic order
        node = candidates.pop(0)            # Get a candidate from the list
        result.append(node)                 # Add that node to the solution

        # Find new candidates after handling the current one
        for adj in g[node]:
            in_degree[adj] -= 1             # Since the current node has been already managed, reduce by one the number of dependencies in every adjacent edge of the current node
            if in_degree[adj] == 0:         # If an adjacent node is now free of dependencies
                candidates.append(adj)      # Consider the adjacent node as a candidate

    return result


if __name__ == "__main__":
    graph = [[1,2], [3], [5], [], [6], [], []]

    sol = topo_sort(graph)
    print(" ".join(map(str, sol)))