Topologisk sorteringsalgoritme

Den topologiske sorteringsalgoritmen fungerer med DAG (direkte acyklisk graf). Betydningen av den topologiske typen er at hvis noen node peker på en annen node, vil noden som peker på en annen node komme etter det. Så i dette tilfellet, hvis vi har en syklisk graf, kan vi ikke forutsi hvilken node som kommer etter den. Så det er grunnen til at den topologiske sorteringsalgoritmen bare fungerer med den acykliske grafen og ikke med den sykliske grafen.

Hver graf har mer enn en topologisk sorteringssekvens fordi den avhenger av nodegraden på kantene på nodene. Den første startnoden som vi velger med et antall noder er 0.

La oss forstå den topologiske sorteringsalgoritmen med et eksempel.

Trinn 1: Vi setter inn nodene hvis innkommende kantantall er lik 0. Så disse nodene er node 1 og node 4.

Steg 2:

en. Vi begynner med node 1. Vi kan velge hvilken som helst node mellom node 1 og node 4.

b. Vi reduserer hver nodekant med 1, som er koblet til node 1. Vi reduserer kanten av nodene (0, 2 og 3).

c. Vi flytter node 1 fra listen til den topologisk sorterte listen, som vist nedenfor.

Trinn 3:

en. Vi fortsetter nå fra listen, som er node 4.

b. Vi reduserer alle utgående kanter på nodene koblet til node 4, som er noder (0 og 3).

c. Nå har Node 3 ingen innkommende kanter, så vi skyver den inn i listen, og Node 4 skifter til den topologisk sorterte listen.

Trinn 4:

en. Vi fortsetter nå fra listen, som er node 3.

b. Vi reduserer alle utgående kanter på nodene koblet til node 3, som er noder (0 og 2).

c. Nå har noder 0 og node 2 ingen innkommende kanter, så vi skyver den inn i listen, og node 3 skifter til den topologisk sorterte listen.

Trinn 5:

en. Vi fortsetter nå fra listen, som er node 0.

b. Som ingen utgående kanter fra Node 0, så legger vi dem ganske enkelt til den topologiske sorteringslisten.

Trinn 6:

en. Vi fortsetter nå fra listen, som er node 2.

b. Som ingen utgående kanter fra Node 2, så legger vi dem ganske enkelt til den topologiske sorteringslisten.

Trinn 7:

Endelig har vi sortert listen her.

Topologisk sorteringsalgoritme

Nedenfor er trinnene for den topologiske sorteringsalgoritmen som vi må følge.

Trinn 0: Beregn graden av hver grafnode.

Trinn 1: Vi må først finne en node som har innkommende kanter på null.

Trinn 2: Vi fjerner den noden fra grafen og legger den til listen over topologiske sorteringsordrer.

Trinn 3: Fjern nodene som har utgående kanter.

Trinn 4: Reduser graden med antall relaterte kanter som ble fjernet.

Trinn 5: Gjenta trinn 1-4 til ingen noder med 0 i graden gjenstår.

Trinn 6: Kontroller at alle elementene er i riktig sekvens.

Trinn 7: Nå har vi sortert ordren fra trinn 6.

Trinn 8: Slutt med algoritmen.

Python -kode: Nedenfor er en Python -implementering av eksemplet ovenfor.

fra ColleksjonsimportDefaultDict
ClassbuildGraph:
def__init __ (selv, noder: int):
selv-.noder = noder
# Vi lagrer nå grafen i tilstøtende listeformat
selv-.adjlistDetails = StandardDict (liste)
# Den vil lagre informasjonen om en bestemt node innkommende
# kanter i en graf
selv-.count_numbers_of_incoming_edge_of_a_node = []
# Vi lagrer de sorterte nodene i topologisk rekkefølge
selv-.topological_sorted_order = []
# Vi lagrer informasjonen om alle disse nodene som ikke gjør det
# Ha noen innkommende kanter i en graf
selv-.noder_have_zero_incoming_edges = []
# Nå lager vi en tilstøtende liste over alle grafene som skal sorteres
DefaddgraphEdge (selv, kilde: int, destinasjon: int):
selv-.AdjlistDetails [kilde].vedlegg (destinasjon)
selv-.count_numbers_of_incoming_edge_of_a_node [destinasjon] += 1
DeftopologicalSortalgoritme (selv):
for node inrange (selv.noder):
hvis selv.count_numbers_of_incoming_edge_of_a_node [node] == 0:
selv-.noder_have_zero_incoming_edges.vedlegg (node)
Whileself.noder_have_zero_incoming_edges:
selv-.noder_have_zero_incoming_edges.sortere()
kilde = selv.noder_have_zero_incoming_edges.pop (0)
# tilstøtende liste iterasjon
Hvis kilde er selv.AdjlistDetails:
for node Inself.AdjlistDetails [kilde]:
selv-.count_numbers_of_incoming_edge_of_a_node [node] -= 1
hvis selv.count_numbers_of_incoming_edge_of_a_node [node] == 0:
selv-.noder_have_zero_incoming_edges.vedlegg (node)
selv-.topological_sorted_order.vedlegg (kilde)
Print ("Topologisk sorteringsrekkefølge:"+Str (selv.topological_sorted_order)))
Defmain ():
NUMMER_OF_NODES = 7
graf = buildgraph (number_of_nodes)
kurve.count_numbers_of_incoming_edge_of_a_node = [0] *number_of_nodes
kurve.AddGraphEdge (0,2)
kurve.AddGraphEdge (0,5)
kurve.AddGraphEdge (1,3)
kurve.AddGraphEdge (1,6)
kurve.AddGraphEdge (2,4)
kurve.AddGraphEdge (3,5)
kurve.AddGraphEdge (5,2)
kurve.AddGraphEdge (5,4)
kurve.AddGraphEdge (6,2)
kurve.TopologicalSortalgoritme ()
if __name__ == "__ main__":
hoved()

Produksjon:

Topologisk sorteringsrekkefølge: [0, 1, 3, 5, 6, 2, 4]

Topologisk sorteringsalgoritm Tidskompleksitet:

Den totale tiden for å behandle algoritmen er O (E + N), der E representerer antall kanter og n representerer antall noder i grafen. Deretter må vi i det følgende trinn beregne hver nodeens grad, som vanligvis tar O (e) ganger, og deretter plassere alle disse nodene i en sortert liste der deres grad er null, som tar O (N) ganger. Så den totale tidskompleksiteten til den topologiske sorteringsalgoritmen er O (E+N).

Men romkompleksiteten til den topologiske sorteringsalgoritmen er O (n), som er det totale antallet noder i grafen.

applikasjon :

1. Topologisk slags er veldig nyttig for å finne grafens syklus.

2. Topologisk sorteringsalgoritme brukes til å bestemme deadlock -forholdene i et operativsystem.

3. Topologisk sorteringsalgoritme brukes til å finne den korteste banen i en vektet acyklisk graf.

Konklusjon:

Denne artikkelen har lært om en mer viktig algoritme, topologisk sortering. Vi har sett at denne algoritmen bare fungerer med acykliske grafer. Den topologiske sorteringsalgoritmen hjelper også med å bestemme oppgavesamlingsrekkefølgen. Den topologiske sorteringsalgoritmen har mange fordeler i sanntid, som å finne den korteste banen. Fordi den topologiske typen er ekstremt nyttig, må enhver programmerer og student forstå denne algoritmen grundig.