Algoritmo di ordinamento topologico: Python, C++ Esempio

Cos'è l'algoritmo di ordinamento topologico?

L'ordinamento topologico è noto anche come algoritmo di Kahn ed è un algoritmo di ordinamento popolare. Utilizzando un grafico diretto come input, l'ordinamento topologico ordina i nodi in modo che ciascuno appaia prima di quello a cui punta.

Questo algoritmo viene applicato a un DAG (grafo aciclico diretto) in modo che ogni nodo appaia nell'array ordinato prima di tutti gli altri nodi a cui punta. L'algoritmo segue ripetutamente alcune regole fino al completamento dell'ordinamento.

Per semplificare, guarda il seguente esempio:

Grafico diretto

Qui possiamo vedere che "A" non ha grado di entrata. Il grado di entrata indica l'arco che punta a un nodo. "B" e "C" hanno come prerequisito "A", mentre "E" ha come prerequisito i nodi "D" e "F". Alcuni nodi dipendono da altri nodi.

Ecco un'altra rappresentazione del grafico precedente:

Dipendenza di ciascun nodo (ordinamento lineare)

Quindi, quando passiamo il DAG (grafico aciclico diretto) all'ordinamento topologico, ci darà un array con ordinamento lineare, dove il primo elemento non ha dipendenza.

Ecco i passaggi per farlo:

Passo 1) Trova il nodo con zero bordi entranti, un nodo con zero gradi.

Passo 2) Memorizza quel nodo con grado di entrata pari a zero in una coda o in uno stack e rimuovi il nodo dal grafo.

Passo 3) Quindi elimina l'arco uscente da quel nodo. Questo decrementerà il conteggio del grado entrante per il nodo successivo.

L'ordinamento topologico richiede che la struttura dati del grafo non presenti cicli. Un grafo sarà considerato un DAG (grafo aciclico diretto) se soddisfa i seguenti requisiti:

• Uno o più nodi con un valore di grado pari a zero.
• Il grafico non contiene alcun ciclo.

Finché nel grafo sono presenti nodi e il grafo rimane un DAG, eseguiremo i tre passaggi sopra descritti. Altrimenti, l'algoritmo entrerà in una dipendenza ciclica e l'algoritmo di Kahn non sarà in grado di trovare un nodo con grado di entrata pari a zero.

Come funziona l'ordinamento topologico

Qui utilizzeremo l'algoritmo di Kahn per l'ordinamento topologico. Supponiamo di avere il seguente grafo:

Ecco i passaggi dell'algoritmo di Kahn:

Passo 1) Calcola il grado ingrado o il bordo entrante di tutti i nodi nel grafico.

Nota:

• Ingrado indica i bordi diretti che puntano al nodo.
• Per gradi esterni si intendono i bordi diretti che provengono da un nodo.

Ecco il grado di entrata e il grado di uscita del grafico sopra riportato:

Passo 2) Trova il nodo con grado di entrata pari a zero o con zero archi entranti. Un nodo con grado di entrata pari a zero significa che nessun arco entra in quel nodo. Il nodo "A" ha grado di entrata pari a zero, il che significa che non esiste alcun arco che punti al nodo "A". Pertanto, eseguiremo le seguenti azioni:

• Rimuovi questo nodo e i suoi archi uscenti.
• Posiziona il nodo nella coda per l'ordine.
• Aggiorna il conteggio del grado di entrata del nodo vicino ad "A".

Passo 3) Dobbiamo trovare un nodo con un grado di entrata pari a zero. In questo esempio, "B" e "C" hanno un grado di entrata pari a zero. Possiamo scegliere uno qualsiasi dei due. Prendiamo "B" ed eliminiamolo dal grafo. Quindi aggiorniamo i valori di entrata degli altri nodi. Dopo aver eseguito queste operazioni, il nostro grafo e la coda avranno il seguente aspetto:

Passo 4) Il nodo "C" non ha archi entranti. Pertanto, rimuoveremo il nodo "C" dal grafo e lo inseriremo nella coda. Possiamo anche eliminare l'arco uscente da "C". Ora il nostro grafo apparirà così:

Passo 5) Possiamo notare che i nodi "D" e "F" hanno un grado di entrata pari a zero. Prenderemo un nodo e lo inseriremo nella coda. Iniziamo rimuovendo "D". Il conteggio del grado di entrata per il nodo "E" sarà quindi 1. Ora non ci sarà alcun nodo da D a E. Dobbiamo fare lo stesso per il nodo "F", e il risultato sarà il seguente:

Passo 6) Il grado di entrata (archi entranti) e il grado di uscita (archi uscenti) del nodo "E" sono diventati zero. Pertanto, abbiamo soddisfatto tutti i prerequisiti per il nodo "E". A questo punto, posizioneremo "E" alla fine della coda. Non ci sono più nodi da aggiungere e l'algoritmo termina qui.

Soprannome Code per l'ordinamento topologico

Ecco lo pseudocodice per l'ordinamento topologico utilizzando l'algoritmo di 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

L'ordinamento topologico può essere implementato anche utilizzando il DFS (Prima ricerca in profondità) metodo. Tuttavia, questo approccio è il metodo ricorsivo. L'algoritmo di Kahn è più efficiente dell'approccio DFS.

C++ Implementazione dell'ordinamento topologico

#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();
}

Uscita

0       1       2       3       5       4

Python Implementazione dell'ordinamento topologico

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()

Uscita

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

Grafici ciclici dell'algoritmo di ordinamento topologico

Un grafo contenente un ciclo non può essere ordinato topologicamente, poiché il grafo ciclico presenta una dipendenza ciclica. Ad esempio, osserva questo grafo:

Questo grafo non è un DAG (grafo aciclico diretto) perché A, B e C formano un ciclo. Come si può notare, non esiste alcun nodo con grado di entrata pari a zero. Secondo l'algoritmo di Kahn, se analizziamo il grafo sopra riportato:

• Trova un nodo con zero gradi (nessun arco entrante).
• Rimuovi quel nodo dal grafo e aggiungilo alla coda. Tuttavia, nel grafo sopra, non c'è nessun nodo con grado di entrata pari a zero. Ogni nodo ha un valore di grado di entrata maggiore di 0.
• Restituisce una coda vuota, poiché non è stato possibile trovare alcun nodo con grado di entrata pari a zero.

Possiamo rilevare i cicli utilizzando l'ordinamento topologico con i seguenti passaggi:

Passo 1) Eseguire l'ordinamento topologico.

Passo 2) Calcolare il numero totale di elementi nell'elenco ordinato topologicamente.

Passo 3) Se il numero di elementi è uguale al numero totale di vertici, allora non c'è alcun ciclo.

Passo 4) Se non è uguale al numero di vertici, allora nella struttura dati del grafo data è presente almeno un ciclo.

Analisi della complessità dell'ordinamento topologico

Esistono due tipi di complessità negli algoritmi. Essi sono:

1. Complessità temporale
2. Complessità spaziale

Queste complessità sono rappresentate da una funzione che fornisce una complessità generale.

Complessità temporale: La complessità temporale per l'ordinamento topologico è sempre la stessa. Esistono scenari di complessità temporale peggiore, media e migliore. La complessità temporale per l'ordinamento topologico è O(E + V), dove E rappresenta il numero di archi nel grafo e V il numero di vertici nel grafo.

Cerchiamo di superare questa complessità:

Passo 1) All'inizio calcoleremo tutti gli ingradi. Per fare ciò, dobbiamo passare attraverso tutti gli spigoli e inizialmente assegneremo a zero tutti gli gradi del vertice V. Quindi, i passaggi incrementali che completeremo saranno O(V+E).

Passo 2) Troveremo il nodo con valore di grado zero. Dobbiamo cercare dal numero V del vertice. Quindi, i passaggi completati saranno O(V).

Passo 3) Per ogni nodo con zero gradi, rimuoveremo quel nodo e decrementeremo il grado. Sarà necessario eseguire questa operazione per tutti i nodi O(E).

Passo 4) Infine, controlleremo se è presente o meno un ciclo. Controlleremo se il numero totale di elementi nell'array ordinato è uguale al numero totale di nodi. Ci vorrà O (1).

Questi erano quindi i tempi di complessità individuali per ogni fase dell'ordinamento topologico. Possiamo affermare che la complessità temporale derivante dal calcolo precedente sarà O(V + E); dove O indica la funzione di complessità.

Complessità spaziale: Per eseguire l'algoritmo di ordinamento topologico, avevamo bisogno di spazi di tipo O(V). Ecco i passaggi in cui era necessario lo spazio per il programma:

• Dovevamo calcolare tutti gli gradi dei nodi presenti nel Grafico. Poiché il grafico ha un totale di nodi V, dobbiamo creare un array di dimensioni V. Quindi, lo spazio richiesto era O(V).
• Per memorizzare il nodo con grado zero è stata utilizzata una struttura dati coda. Abbiamo rimosso i nodi con grado zero dal grafico originale e li abbiamo inseriti nella coda. Per questo, lo spazio richiesto era O(V).
• L'array è denominato "order", che memorizza i nodi in ordine topologico. Ciò richiedeva anche O(V) spazi.

Queste erano le singole complessità spaziali. Pertanto, dobbiamo massimizzare questi spazi in fase di esecuzione. La complessità spaziale è O(V), dove V indica il numero di vertici nel grafo.

Applicazione dell'ordinamento topologico

L'ordinamento topologico ha moltissime applicazioni. Eccone alcune:

• Si usa quando un Operasistema di ting deve eseguire l’allocazione delle risorse.
• Individuazione di un ciclo nel grafo. Possiamo verificare se il grafo è un DAG o meno tramite l'ordinamento topologico.
• Ordinamento delle frasi nelle app di completamento automatico.
• Viene utilizzato per rilevare situazioni di stallo.
• Diversi tipi di pianificazione o programmazione dei corsi utilizzano l'ordinamento topologico.
• Risoluzione delle dipendenze. Ad esempio, se provi a installare un pacchetto, quel pacchetto potrebbe richiedere anche altri pacchetti. L'ordinamento topologico individua tutti i pacchetti necessari per installare il pacchetto corrente.
• Linux utilizza l'ordinamento topologico in "apt" per verificare la dipendenza dei pacchetti.

DOMANDE FREQUENTI