Algoritmo de ordenação topológica: Python, C++ Exemplo

O que é algoritmo de classificação topológica?

A classificação topológica também é conhecida como algoritmo de Kahn e é um algoritmo de classificação popular. Usando um gráfico direcionado como entrada, a classificação topológica classifica os nós para que cada um apareça antes daquele para o qual aponta.

Este algoritmo é aplicado em um DAG (Grafo Acíclico Direcionado) de forma que cada nó apareça na matriz ordenada antes de todos os outros nós para os quais ele aponta. O algoritmo repete algumas regras até que a ordenação seja concluída.

Para simplificar, veja o seguinte exemplo:

Gráfico direcionado

Aqui, podemos ver que “A” não possui grau de entrada. Grau de entrada significa a aresta que aponta para um nó. “B” e “C” têm como pré-requisito “A”, e “E” tem como pré-requisito os nós “D” e “F”. Alguns dos nós são dependentes de outros nós.

Aqui está outra representação do gráfico acima:

Dependência de cada nó (ordenação linear)

Assim, ao passarmos o DAG (Directed Acíclico Graph) para a ordenação topológica, ele nos dará um array com ordenação linear, onde o primeiro elemento não possui dependência.

Aqui estão as etapas para fazer isso:

Passo 1) Encontre o nó com zero arestas de entrada, um nó com zero graus.

Passo 2) Armazene esse nó de grau de entrada zero em uma fila ou pilha e remova o nó do grafo.

Passo 3) Em seguida, exclua a aresta de saída desse nó. Isso diminuirá o grau de entrada para o próximo nó.

A ordenação topológica exige que a estrutura de dados do grafo não possua ciclos. Um grafo será considerado um DAG (grafo acíclico dirigido) se atender a esses requisitos:

• Um ou mais nós com valor de indegree igual a zero.
• O gráfico não contém nenhum ciclo.

Enquanto houver nós no grafo e o grafo ainda for um DAG (Grafo Acíclico Dirigido), executaremos os três passos acima. Caso contrário, o algoritmo entrará em dependência cíclica e o Algoritmo de Kahn não conseguirá encontrar um nó com grau de entrada zero.

Como funciona a classificação topológica

Aqui, utilizaremos o “Algoritmo de Kahn” para a ordenação topológica. Suponhamos que temos o seguinte grafo:

Aqui estão os passos do Algoritmo de Kahn:

Passo 1) Calcule o grau de entrada ou borda de entrada de todos os nós no gráfico.

Observação:

• Indegree significa as arestas direcionadas apontando para o nó.
• Outdegree significa as arestas direcionadas que vêm de um nó.

Aqui estão os graus de entrada e saída do grafo acima:

Passo 2) Encontre o nó com grau de entrada zero, ou seja, nenhuma aresta chegando até ele. O nó "A" tem grau de entrada zero, o que significa que não há nenhuma aresta apontando para ele. Portanto, realizaremos as seguintes ações:

• Remova este nó e suas arestas de saída (arestas de saída).
• Coloque o nó na fila para pedido.
• Atualize a contagem de graus de entrada do nó vizinho de “A”.

Passo 3) Precisamos encontrar um nó com grau de entrada igual a zero. Neste exemplo, “B” e “C” têm grau de entrada zero. Aqui, podemos escolher qualquer um dos dois. Vamos escolher “B” e removê-lo do grafo. Em seguida, atualizamos os valores de grau de entrada dos outros nós. Após realizar essas operações, nosso grafo e fila ficarão assim:

Passo 4) O nó “C” não possui aresta de entrada. Portanto, removeremos o nó “C” do grafo e o adicionaremos à fila. Também podemos excluir a aresta de saída de “C”. Agora, nosso grafo ficará assim:

Passo 5) Podemos ver que os nós “D” e “F” têm grau de entrada zero. Vamos pegar um nó e colocá-lo na fila. Vamos remover “D” primeiro. Então, o grau de entrada para o nó “E” será 1. Agora, não haverá nenhum nó de D para E. Precisamos fazer o mesmo para o nó “F”, e nosso resultado será o seguinte:

Passo 6) O grau de entrada (arestas de entrada) e o grau de saída (arestas de saída) do nó “E” tornaram-se zero. Portanto, atendemos a todos os pré-requisitos para o nó “E”. Aqui, colocaremos “E” no final da fila. Assim, não temos mais nós e o algoritmo termina aqui.

Apelido Code para ordenação topológica

Segue o pseudocódigo para a ordenação topológica utilizando o 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

A classificação topológica também pode ser implementada usando o DFS (Profundidade primeira pesquisa) método. No entanto, essa abordagem é o método recursivo. O algoritmo de Kahn é mais eficiente que a abordagem DFS.

C++ Implementação de classificação 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();
}

saída

0       1       2       3       5       4

Python Implementação de classificação 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()

saída

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

Gráficos cíclicos do algoritmo de classificação topológica

Um grafo que contém um ciclo não pode ser ordenado topologicamente, pois o grafo cíclico possui dependências de forma cíclica. Por exemplo, observe este grafo:

Este grafo não é um DAG (Grafo Acíclico Direcionado) porque A, B e C formam um ciclo. Observe que não há nenhum nó com grau de entrada igual a zero. De acordo com o Algoritmo de Kahn, se analisarmos o grafo acima:

• Encontre um nó com zero graus de entrada (sem arestas de entrada).
• Remova esse nó do grafo e adicione-o à fila. No entanto, no grafo acima, não há nenhum nó com grau de entrada zero. Todos os nós têm um valor de grau de entrada maior que 0.
• Retorna uma fila vazia, pois não foi possível encontrar nenhum nó com grau de entrada zero.

Podemos detectar ciclos usando a ordenação topológica com as seguintes etapas:

Passo 1) Execute a classificação topológica.

Passo 2) Calcule o número total de elementos na lista ordenada topologicamente.

Passo 3) Se o número de elementos for igual ao número total de vértices, então não há ciclo.

Passo 4) Se não for igual ao número de vértices, então existe pelo menos um ciclo na estrutura de dados do grafo em questão.

Análise de complexidade de classificação topológica

Existem dois tipos de complexidade em algoritmos. São eles:

1. Complexidade de tempo
2. Complexidade do Espaço

Essas complexidades são representadas por uma função que fornece uma complexidade geral.

Complexidade de tempo: A complexidade de tempo para a ordenação topológica é a mesma para todos os casos. Existem cenários de pior caso, caso médio e caso melhor para a complexidade de tempo. A complexidade de tempo para a ordenação topológica é O(E + V), onde E representa o número de arestas no grafo e V representa o número de vértices no grafo.

Vamos desvendar essa complexidade:

Passo 1) No início, calcularemos todos os graus. Para fazer isso, precisamos percorrer todas as arestas e, inicialmente, atribuiremos todos os graus dos vértices V a zero. Portanto, as etapas incrementais que completamos serão O(V+E).

Passo 2) Encontraremos o nó com valor de grau zero. Precisamos pesquisar a partir do número V do vértice. Assim, as etapas concluídas serão O (V).

Passo 3) Para cada nó com zero indegrees, removeremos esse nó e decrementaremos o indegree. Executar esta operação para todos os nós levará O(E).

Passo 4) Por fim, verificaremos se existe algum ciclo ou não. Verificaremos se o número total de elementos na matriz classificada é igual ao número total de nós. Vai levar O (1).

Portanto, essas foram as complexidades de tempo individuais para cada etapa da ordenação topológica. Podemos afirmar que a complexidade de tempo, com base no cálculo acima, será O(V + E); aqui, O representa a função de complexidade.

Complexidade do espaço: Precisávamos de espaço O(V) para executar o algoritmo de ordenação topológica. Aqui estão os passos em que o programa precisou de espaço:

• Tivemos que calcular todos os graus de nós presentes no gráfico. Como o Grafo possui um total de V nós, precisamos criar um array de tamanho V. Portanto, o espaço necessário foi O (V).
• Uma estrutura de dados Queue foi usada para armazenar o nó com grau zero. Removemos os nós com grau zero do gráfico original e os colocamos na fila. Para isso, o espaço necessário foi O (V).
• O array se chama “order”, que armazena os nós em ordem topológica. Isso também exigia O (V) espaços.

Essas eram as complexidades de espaço individuais. Portanto, precisamos maximizar esses espaços em tempo de execução. A complexidade de espaço é representada por O(V), onde V significa o número de vértices no grafo.

Aplicação de classificação topológica

A ordenação topológica tem inúmeras aplicações. Aqui estão algumas delas:

• É usado quando um Operasistema ting precisa realizar a alocação de recursos.
• Encontrando um ciclo no grafo. Podemos validar se o grafo é um DAG (grafo acíclico direcionado) ou não com a ordenação topológica.
• Ordenação de frases nos aplicativos de preenchimento automático.
• É utilizado para detecção impasses.
• Diferentes tipos de agendamento ou planejamento de cursos utilizam a ordenação topológica.
• Resolvendo dependências. Por exemplo, se você tentar instalar um pacote, esse pacote também poderá precisar de outros pacotes. A ordenação topológica descobre todos os pacotes necessários para instalar o pacote atual.
• Linux usa a classificação topológica no “apt” para verificar a dependência dos pacotes.

Perguntas Frequentes