Algoritmo de ordenación topológica: Python, C++ Ejemplo

¿Qué es el algoritmo de clasificación topológica?

La clasificación topológica también se conoce como algoritmo de Kahn y es un algoritmo de clasificación popular. Utilizando un gráfico dirigido como entrada, Topological Sort ordena los nodos para que cada uno aparezca antes del que apunta.

Este algoritmo se aplica a un DAG (grafo acíclico dirigido) de manera que cada nodo aparezca en el arreglo ordenado antes que todos los demás nodos a los que apunta. Este algoritmo sigue ciertas reglas repetidamente hasta que se completa la ordenación.

Para simplificar, observe el siguiente ejemplo:

Gráfico dirigido

Aquí podemos ver que “A” no tiene grado de entrada. El grado de entrada se refiere a la arista que apunta a un nodo. “B” y “C” tienen como prerrequisito a “A”, y “E” tiene como prerrequisito a los nodos “D” y “F”. Algunos nodos dependen de otros nodos.

Aquí hay otra representación del gráfico anterior:

Dependencia de cada nodo (Ordenamiento lineal)

Entonces, cuando pasamos el DAG (Gráfico acíclico dirigido) al ordenamiento topológico, nos dará una matriz con ordenamiento lineal, donde el primer elemento no tiene dependencia.

Estos son los pasos para hacer esto:

Paso 1) Encuentre el nodo con cero aristas entrantes, un nodo con cero grados.

Paso 2) Almacena ese nodo de grado de entrada cero en una cola o pila y elimina el nodo del grafo.

Paso 3) Luego, elimina la arista saliente de ese nodo. Esto disminuirá el conteo de grados de entrada para el siguiente nodo.

El orden topológico requiere que la estructura de datos del grafo no tenga ningún ciclo. Un grafo se considerará un DAG si cumple con estos requisitos:

• Uno o más nodos con un valor de grado cero.
• El gráfico no contiene ningún ciclo.

Mientras haya nodos en el grafo y este siga siendo un DAG, ejecutaremos los tres pasos anteriores. De lo contrario, el algoritmo caerá en una dependencia cíclica y el algoritmo de Kahn no podrá encontrar un nodo con grado de entrada cero.

Cómo funciona la clasificación topológica

Aquí utilizaremos el algoritmo de Kahn para la ordenación topológica. Supongamos que tenemos el siguiente grafo:

Estos son los pasos del algoritmo de Kahn:

Paso 1) Calcule el grado interno o el borde entrante de todos los nodos en el gráfico.

Nota:

• Engrado significa los bordes dirigidos que apuntan al nodo.
• Grado exterior significa los bordes dirigidos que provienen de un nodo.

Aquí están el grado de entrada y el grado de salida del gráfico anterior:

Paso 2) Encuentra el nodo con grado de entrada cero o con aristas entrantes cero. Un nodo con grado de entrada cero significa que no hay aristas que apunten hacia él. El nodo "A" tiene grado de entrada cero, lo que significa que no hay ninguna arista que apunte al nodo "A". Por lo tanto, realizaremos las siguientes acciones:

• Elimine este nodo y sus aristas de salida.
• Coloque el nodo en la cola para realizar pedidos.
• Actualizar el conteo de grado de entrada del nodo vecino de “A”.

Paso 3) Necesitamos encontrar un nodo con un grado de entrada de cero. En este ejemplo, “B” y “C” tienen grado de entrada cero. Podemos tomar cualquiera de los dos. Tomemos “B” y eliminémoslo del grafo. Luego, actualizamos los grados de entrada de los demás nodos. Después de realizar estas operaciones, nuestro grafo y cola se verán así:

Paso 4) El nodo “C” no tiene aristas entrantes. Por lo tanto, eliminaremos el nodo “C” del grafo y lo agregaremos a la cola. También podemos eliminar la arista saliente de “C”. Ahora, nuestro grafo se verá así:

Paso 5) Podemos observar que los nodos “D” y “F” tienen un grado de entrada de cero. Tomaremos un nodo y lo agregaremos a la cola. Primero, extraigamos “D”. Entonces, el grado de entrada del nodo “E” será 1. Ahora, no habrá ningún nodo de D a E. Debemos hacer lo mismo con el nodo “F”, y el resultado será el siguiente:

Paso 6) El grado de entrada (aristas entrantes) y el grado de salida (aristas salientes) del nodo “E” se redujeron a cero. Por lo tanto, cumplimos con todos los requisitos previos para el nodo “E”. Ahora, colocaremos “E” al final de la cola. Así, no quedan nodos y el algoritmo finaliza aquí.

Apodo Code para la ordenación topológica

Aquí está el pseudocódigo para la ordenación topológica utilizando el algoritmo de Kahn.

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  while node with 0 indegree present:
    topological_list.append(node)
    G.remove(node)
    // Update indegree of present nodes
  return topological_list

La clasificación topológica también se puede implementar utilizando DFS (Primera búsqueda en profundidad) método. Sin embargo, ese enfoque es el método recursivo. El algoritmo de Kahn es más eficiente que el enfoque DFS.

C++ Implementación de clasificación topológica

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

Resultado

0       1       2       3       5       4

Python Implementación de clasificación topológica

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list)
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

Resultado

[0, 1, 2, 3, 5, 4]

Gráficos cíclicos del algoritmo de clasificación topológica

Un grafo que contiene un ciclo no puede ordenarse topológicamente, ya que el grafo cíclico tiene la dependencia de forma cíclica. Por ejemplo, observe este grafo:

Este grafo no es un DAG (grafo acíclico dirigido) porque A, B y C forman un ciclo. Si observas, no hay ningún nodo con grado de entrada cero. Según el algoritmo de Kahn, si analizamos el grafo anterior:

• Encuentre un nodo con cero grados (sin aristas entrantes).
• Elimina ese nodo del grafo y agrégalo a la cola. Sin embargo, en el grafo anterior, no hay ningún nodo con grado de entrada cero. Todos los nodos tienen un grado de entrada mayor que 0.
• Devuelve una cola vacía, ya que no pudo encontrar ningún nodo con grado de entrada cero.

Podemos detectar ciclos utilizando el ordenamiento topológico con los siguientes pasos:

Paso 1) Realizar clasificación topológica.

Paso 2) Calcule el número total de elementos en la lista ordenada topológicamente.

Paso 3) Si el número de elementos es igual al número total de vértices, entonces no hay ciclo.

Paso 4) Si no es igual al número de vértices, entonces hay al menos un ciclo en la estructura de datos del grafo dada.

Análisis de complejidad de la ordenación topológica

En los algoritmos existen dos tipos de complejidad. Son los siguientes:

1. Complejidad de tiempo
2. Complejidad espacial

Estas complejidades se representan con una función que proporciona una complejidad general.

Complejidad del tiempo: La complejidad temporal es la misma para la ordenación topológica. Existen escenarios de complejidad temporal óptimo, promedio y pesimista. La complejidad temporal para la ordenación topológica es O(E + V), donde E representa el número de aristas del grafo y V el número de vértices.

Superemos esta complejidad:

Paso 1) Al principio calcularemos todos los grados. Para hacer eso, necesitamos pasar por todos los bordes e inicialmente, asignaremos todos los grados de los vértices V a cero. Entonces, los pasos incrementales que completemos serán O (V + E).

Paso 2) Encontraremos el nodo con valor de grado cero. Necesitamos buscar desde el número V del vértice. Entonces, los pasos completados serán O (V).

Paso 3) Para cada nodo con cero grados de entrada, eliminaremos ese nodo y disminuiremos el grado de entrada. Realizar esta operación para todos los nodos llevará O(E).

Paso 4) Finalmente comprobaremos si hay algún ciclo o no. Comprobaremos si el número total de elementos en la matriz ordenada es igual al número total de nodos. Tomará O (1).

Así pues, estas fueron las complejidades temporales individuales para cada paso de la ordenación topológica. Podemos decir que la complejidad temporal del cálculo anterior será O(V + E); aquí, O representa la función de complejidad.

Complejidad espacial: Necesitábamos espacios O(V) para ejecutar el algoritmo de ordenación topológica. Estos son los pasos en los que necesitábamos espacio para el programa:

• Tuvimos que calcular todos los grados de los nodos presentes en el gráfico. Como el gráfico tiene un total de V nodos, necesitamos crear una matriz de tamaño V. Entonces, el espacio requerido fue O (V).
• Se utilizó una estructura de datos de cola para almacenar el nodo con grado cero. Eliminamos los nodos con grado cero del gráfico original y los colocamos en la cola. Para ello se preparó el espacio necesario O (V).
• El arreglo se llama “orden”, que almacenaba los nodos en orden topológico. Eso también requería O (V) espacios

Estas eran las complejidades espaciales individuales. Por lo tanto, necesitamos maximizar estos espacios en el tiempo de ejecución. La complejidad espacial se expresa como O(V), donde V representa el número de vértices en el grafo.

Aplicación de ordenación topológica

La ordenación topológica tiene muchísimas aplicaciones. Aquí te mostramos algunas:

• Se utiliza cuando un Operasistema de ting necesita realizar la asignación de recursos.
• Encontrar un ciclo en el grafo. Podemos validar si el grafo es un DAG o no mediante la ordenación topológica.
• Orden de oraciones en las aplicaciones de autocompletar.
• Se utiliza para detectar deadlocks.
• Los diferentes tipos de programación o planificación de cursos utilizan la ordenación topológica.
• Resolviendo dependencias. Por ejemplo, si intenta instalar un paquete, es posible que ese paquete también necesite otros paquetes. El ordenamiento topológico descubre todos los paquetes necesarios para instalar el paquete actual.
• Linux utiliza la clasificación topológica en "apt" para verificar la dependencia de los paquetes.

Preguntas Frecuentes