Orden topológico

El ordenamiento topológico de un grafo es un orden lineal de sus vértices tal que, para cada arista dirigida $(u, v)$, el vértice $u$ aparece antes que el vértice $v$ en el orden. Este concepto es aplicable únicamente a grafos dirigidos acíclicos (DAG).

Se utiliza para resolver problemas de planificación y dependencia de tareas, donde es necesario determinar un orden en el que se deben realizar las tareas.

1Algoritmo de Kahn¶

Una forma de encontrar un ordenamiento topológico es mediante el algoritmo de Kahn (Arthur Kahn), que utiliza un enfoque basado en el grado de entrada de los vértices. Los pasos son los siguientes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ORDEN TOPOLÓGICO (G: DiGrafo)
    q = Cola vacía

    PARA CADA v EN G.nodos:
        SI v.grado_entrada == 0:
            q.encolar(v)

    MIENTRAS NO q.esta_vacia:
        v = q.desencolar()

        VISITAR v

        PARA CADA w EN v.nodos_adyacentes:
            w.grado_entrada -= 1

            SI w.grado_entrada == 0:
                q.encolar(w)

    SI quedaron nodos sin procesar:
        REPORTAR error: grafo con ciclos

Por ejemplo dado el siguiente grafo:

Un orden topológico posible es: $V_2$, $V_0$, $V_1$, $V_3$, $V_4$, $V_6$, $V_5$. Como se observa a continuación.

1.1Complejidad¶

La complejidad del algoritmo de Kahn es $O(|V|+|E|)$. Esto se debe a que cada vértice y cada arista se procesan una sola vez.

2Cálculo del orden topológico con NetworkX¶

NetworkX proporciona el método topological_sort para calcular el orden topológico de un grafo dirigido acíclico (DAG).

import networkx as nx

grafo = {
    "V0": ["V1", "V3"],
    "V1": ["V3", "V4"],
    "V2": ["V0", "V5"],
    "V3": ["V4", "V5", "V6"],
    "V4": ["V6"],
    "V5": [],
    "V6": ["V5"],
}

G = nx.DiGraph(grafo)

list(nx.topological_sort(G))