Algoritmo di smistamento topologico

L'algoritmo di smistamento topologico funziona con il DAG (grafico aciclico diretto). Il significato dell'ordinamento topologico è che se un nodo punta a un altro nodo, allora il nodo che punta a un altro nodo arriverà dopo. Quindi, in questo caso, se abbiamo un grafico ciclico, non possiamo prevedere quale nodo viene dopo il quale nodo. Questo è il motivo per cui l'algoritmo di tipo topologico funziona solo con il grafico aciclico e non con il grafico ciclico.

Ogni grafico ha più di una sequenza di ordinamento topologica perché dipende dal grado dei bordi dei nodi. Il primo nodo iniziale che scegliamo con un numero di nodi di grado è 0.

Comprendiamo l'algoritmo di tipo topologico con un esempio.

Passaggio 1: inseriamo quei nodi il cui conteggio dei bordi in arrivo è uguale a 0. Quindi quei nodi sono nodo 1 e nodo 4.

Passo 2:

UN. Iniziamo con il nodo 1. Possiamo scegliere qualsiasi nodo tra il nodo 1 e il nodo 4.

B. Diminuiamo ogni bordo del nodo di 1, che è collegato al nodo 1. Stiamo diminuendo il bordo dei nodi (0, 2 e 3).

C. Spostamo il nodo 1 dall'elenco all'elenco ordinato topologicamente, come mostrato di seguito.

Passaggio 3:

UN. Procediamo ora dall'elenco, che è nodo 4.

B. Diminiamo tutti i bordi in uscita dei nodi collegati al nodo 4, che sono nodi (0 e 3).

C. Ora, il nodo 3 non ha bordi in arrivo, quindi lo spingiamo nell'elenco e il nodo 4 si sposta sull'elenco topologicamente.

Passaggio 4:

UN. Procediamo ora dall'elenco, che è nodo 3.

B. Diminiamo tutti i bordi in uscita dei nodi collegati al nodo 3, che sono nodi (0 e 2).

C. Ora, i nodi 0 e il nodo 2 non hanno bordi in arrivo, quindi lo spingiamo nell'elenco e il nodo 3 si sposta nell'elenco ordinato topologicamente.

Passaggio 5:

UN. Procediamo ora dall'elenco, che è nodo 0.

B. Come nessun bordi in uscita dal nodo 0, quindi li aggiungiamo semplicemente all'elenco di ordinamento topologico.

Passaggio 6:

UN. Procediamo ora dall'elenco, che è nodo 2.

B. Come nessun bordi in uscita dal nodo 2, quindi li aggiungiamo semplicemente all'elenco di ordinamento topologico.

Passaggio 7:

Infine, abbiamo risolto l'elenco qui.

Algoritmo di ordinamento topologico

I seguenti sono i passaggi per l'algoritmo di smistamento topologico che dobbiamo seguire.

Passaggio 0: calcola il grado di ciascun nodo grafico.

Passaggio 1: dobbiamo prima trovare un nodo che ha bordi in arrivo di zero.

Passaggio 2: rimuoviamo quel nodo dal grafico e lo aggiungiamo all'elenco degli ordini di ordinamento topologico.

Passaggio 3: rimuovere quei nodi che hanno bordi in uscita.

Passaggio 4: ridurre il grado per il numero di bordi correlati che sono stati rimossi.

Passaggio 5: ripetere i passaggi 1-4 fino a quando non rimangono nodi con 0 gradi.

Passaggio 6: verificare che tutti gli elementi siano nella sequenza corretta.

Passaggio 7: ora abbiamo risolto l'ordine dal passaggio 6.

Passaggio 8: metti fine all'algoritmo.

Codice Python: Il seguente è un'implementazione di Python dell'esempio sopra.

daCollectionsimportDefaultDict
Classbuildgraph:
def__init __ (self, nodi: int):
se stesso.nodi = nodi
# Ora stiamo archiviando il grafico nel formato dell'elenco adiacente
se stesso.adjListDetails = defaultDict (elenco)
# Memorizza le informazioni su un particolare nodo in arrivo
# bordi in un grafico
se stesso.count_numbers_of_incoming_edge_of_a_node = []
# Memorizza i nodi ordinati in ordine topologico
se stesso.topological_sorted_order = []
# Memorizza le informazioni di tutti quei nodi
# avere i bordi in arrivo in un grafico
se stesso.nodes_have_zero_incoming_edges = []
# Ora stiamo creando un elenco adiacente di tutti i grafici da ordinare
defaddgraphedge (self, fonte: int, destinazione: int):
se stesso.adjListDetails [fonte].append (destinazione)
se stesso.count_numbers_of_incoming_edge_of_a_node [destinazione] += 1
deftopologicalsortalgorithm (self):
per il nodo inrange (self.nodi):
iuSelf.count_numbers_of_incoming_edge_of_a_node [nodo] == 0:
se stesso.nodes_have_zero_incoming_edges.append (nodo)
Strefelf.nodes_have_zero_incoming_edges:
se stesso.nodes_have_zero_incoming_edges.ordinare()
fonte = self.nodes_have_zero_incoming_edges.pop (0)
# Iterazione dell'elenco adiacente
Se la fonte inseli.adjListDetails:
per inseli di nodo.adjListDetails [Fonte]:
se stesso.count_numbers_of_incoming_edge_of_a_node [nodo] -= 1
iuSelf.count_numbers_of_incoming_edge_of_a_node [nodo] == 0:
se stesso.nodes_have_zero_incoming_edges.append (nodo)
se stesso.topological_sorted_order.append (fonte)
Stampa ("Ordine di smistamento topologico:"+STR (self.topological_sorted_order))
defmain ():
Number_of_nodes = 7
grafico = buildGraph (numero_of_nodes)
grafico.count_numbers_of_incoming_edge_of_a_node = [0] *NUMBER_OF_NODES
grafico.AddGrapHedge (0,2)
grafico.AddGrapHedge (0,5)
grafico.AddGrapHedge (1,3)
grafico.AddGrapHedge (1,6)
grafico.AddGrapHedge (2,4)
grafico.AddGrapHedge (3,5)
grafico.AddGrapHedge (5,2)
grafico.AddGrapHedge (5,4)
grafico.AddGrapHedge (6,2)
grafico.TopologicalSortalGorithm ()
Se __Name__ == "__ Main__":
principale()

Produzione:

Ordine di ordinamento topologico: [0, 1, 3, 5, 6, 2, 4]

Algoritmo di smistamento topologico Complessità temporale:

Il tempo totale per elaborare l'algoritmo è O (E + N), dove E rappresenta il numero di bordi e n rappresenta il numero di nodi nel grafico. Quindi, nel passaggio seguente, dobbiamo calcolare il grado di ciascun nodo, che generalmente richiede volte O (E), quindi inserire tutti quei nodi in un elenco ordinato in cui il loro grado è zero, che prende O (n) volte. Quindi la complessità del tempo totale dell'algoritmo di smistamento topologico è O (E+N).

Ma la complessità spaziale dell'algoritmo di smistamento topologico è O (n), che è il numero totale di nodi nel grafico.

Applicazione :

1. L'ordinamento topologico è molto utile per trovare il ciclo del grafico.

2. L'algoritmo di ordinamento topologico viene utilizzato per determinare le condizioni di deadlock in un sistema operativo.

3. L'algoritmo di ordinamento topologico viene utilizzato per trovare il percorso più corto in un grafico aciclico ponderato.

Conclusione:

Questo articolo ha imparato su un altro algoritmo importante, smistamento topologico. Abbiamo visto che questo algoritmo funziona solo con grafici aciclici. L'algoritmo di smistamento topologico aiuta anche a determinare l'ordine di compilazione dell'attività. L'algoritmo di smistamento topologico ha molti vantaggi in tempo reale, come trovare il percorso più breve. Poiché il tipo topologico è estremamente utile, ogni programmatore e studente devono comprendere a fondo questo algoritmo.