Classificação topológica: Python, C++ Exemplo de algoritmo
Sarah Chen
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 (Gráfico Acíclico Direcionado) para que cada nó apareça na matriz ordenada antes que todos os outros nós sejam apontados para ele. Este algoritmo segue algumas regras repetidamente até que a classificação seja concluída.
Para simplificar, veja o seguinte exemplo:
Aqui, podemos ver que “A” não tem grau. Significa a aresta que aponta para um nó. “B” e “C” possuem um pré-requisito de “A”, então “E” possui um pré-requisito de nós “D” e “F”. Alguns dos nós dependem de outros nós.
Aqui está outra representação do gráfico acima:
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.
Este exemplo mostra um gráfico com um ciclo:
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) Armazena que zera o nó de grau em uma fila ou pilha e remove o nó do gráfico.
Passo 3) Em seguida, exclua a borda de saída desse nó.
Isso diminuirá a contagem de graus para o próximo nó.
A ordenação topológica exige que a estrutura de dados do gráfico não tenha nenhum ciclo.
Um gráfico será considerado um DAG se atender a estes requisitos:
- Um ou mais nós com valor de indegree igual a zero.
- O gráfico não contém nenhum ciclo
Contanto que haja nós no gráfico e o gráfico ainda seja DAG, executaremos as três etapas acima. Caso contrário, o algoritmo cairá na dependência cíclica e o algoritmo de Kahn não será capaz de encontrar um nó com grau zero.
Como funciona a classificação topológica
Aqui, usaremos o “Algoritmo de Kahn” para a ordenação topológica. Digamos que temos o seguinte gráfico:
Aqui estão as etapas para o algoritmo de Kahn:
Passo 1) Calcule o grau de entrada ou borda de entrada de todos os nós no gráfico.
Nota:
- Indegree significa as arestas direcionadas apontando para o nó.
- Outdegree significa as arestas direcionadas que vêm de um nó.
Aqui está o grau de entrada e saída do gráfico acima:
Passo 2) Encontre o nó com zero graus de entrada ou zero arestas de entrada.
O nó com grau zero significa que nenhuma aresta está vindo em direção a esse nó. O nó “A” tem zero graus, o que significa que não há aresta apontando para o nó “A”.
Então, faremos 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 em graus do nó vizinho de “A”.
Passo 3) Precisamos encontrar um nó com valor de indegree igual a zero. Neste exemplo, “B” e “C” têm grau zero.
Aqui, podemos pegar qualquer um desses dois. Vamos pegar “B” e excluí-lo do gráfico.
Em seguida, atualize os valores de grau de outros nós.
Após realizar essas operações, nosso Gráfico e Fila ficarão parecidos com o seguinte:
Passo 4) O nó “C” não possui borda de entrada. Então, vamos remover o nó “C” do gráfico e colocá-lo na fila.
Também podemos deletar a aresta que sai de “C”.
Agora, nosso gráfico ficará assim:
Passo 5) Podemos ver que os nós “D” e “F” têm grau de entrada zero. Pegaremos um nó e o colocaremos na fila.
Vamos retirar “D” primeiro. Então a contagem de graus para o nó “E” será 1. Agora, não haverá nenhum nó de D a E.
Precisamos fazer o mesmo para o nó “F”, nosso resultado será assim:
Passo 6) O grau de entrada (bordas de entrada) e o grau de saída (bordas de saída) do nó “E” tornaram-se zero. Portanto, atendemos todos os pré-requisitos para o nó “E”.
Aqui, colocamos “E” no final da fila. Portanto, não temos mais nós, então o algoritmo termina aqui.
Pseudocódigo para classificação topológica
Aqui está o pseudocódigo para a classificação topológica ao usar 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 O 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 gráfico contendo um ciclo não pode ser ordenado topologicamente. Já o Gráfico cíclico tem a dependência de forma cíclica.
Por exemplo, verifique este gráfico:
Este gráfico não é DAG (gráfico acíclico direcionado) porque A, B e C criam um ciclo. Se você notar, não há nenhum nó com valor de grau zero.
De acordo com o Algoritmo de Kahn, se analisarmos o gráfico acima:
- Encontre um nó com zero graus de entrada (sem arestas de entrada).
- Remova esse nó do gráfico e envie-o para a fila.
Porém, no gráfico acima, não há nenhum nó com zero em graus. Cada nó tem um valor de grau maior que 0. - Retorna uma fila vazia, pois não foi possível encontrar nenhum nó com zero em graus.
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 há pelo menos um ciclo na estrutura de dados do gráfico fornecida.
Análise de complexidade de classificação topológica
Existem dois tipos de complexidade em algoritmos. Eles estão
- Complexidade de tempo
- Complexidade do Espaço
Essas complexidades são representadas por uma função que fornece uma complexidade geral.
Complexidade de tempo: Toda a complexidade de tempo é a mesma para classificação topológica. Existem cenários piores, médios e melhores para a complexidade do tempo.
A complexidade de tempo para classificação topológica é O (E + V), aqui, E significa o número de arestas no gráfico e V significa o número de vértices no gráfico.
Vamos romper 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).
Então, essas eram as complexidades de tempo individuais para cada etapa da classificação topológica ou ordenação topológica. Podemos dizer que a complexidade de tempo do cálculo acima será O( V + E ); aqui, O significa a função de complexidade.
Complexidade do espaço: Precisávamos de espaços O(V) para executar o algoritmo de classificação topológica.
Aqui estão as etapas em que precisávamos de espaço para o programa:
- 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).
- A matriz é chamada de “ordem”. Isso armazenou os nós em ordem topológica. Isso também exigia O (V) espaços.
Estas eram a complexidade do espaço individual. Portanto, precisamos maximizar esses espaços no tempo de execução.
Complexidade espacial significa O(V), onde V significa o número do vértice no gráfico.
Aplicação de classificação topológica
Há um grande uso para classificação topológica. Aqui estão alguns deles:
- É usado quando Operasistema ting precisa realizar a alocação de recursos.
- Encontrando um ciclo no gráfico. Podemos validar se o gráfico é DAG ou não com classificação topológica.
- Ordenação de frases nos aplicativos de preenchimento automático.
- É usado para detectar impasses.
- Diferentes tipos de agendamento ou agendamento de curso usam a classificaçã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.
