Topologisk sortering: Python, C++ Algoritme eksempel

Hva er topologisk sorteringsalgoritme?

Topologisk sortering er også kjent som Kahns algoritme og er en populær sorteringsalgoritme. Ved å bruke en rettet graf som input, sorterer Topologisk sortering nodene slik at hver vises foran den den peker til.

Denne algoritmen brukes på en DAG (Directed Acyclic Graph) slik at hver node vises i den ordnede matrisen før alle andre noder peker på den. Denne algoritmen følger noen regler gjentatte ganger til sorteringen er fullført.

For å forenkle, se på følgende eksempel:

Her kan vi se at "A" ikke har noen grad. Det betyr kanten som peker til en node. "B" og "C" har en forutsetning for "A", deretter har "E" en forutsetning for "D" og "F" noder. Noen av nodene er avhengige av andre noder.

Her er en annen representasjon av grafen ovenfor:

Så når vi sender DAG (Directed Acyclic Graph) til den topologiske sorteringen, vil det gi oss en matrise med lineær rekkefølge, der det første elementet ikke har noen avhengighet.

Dette eksemplet viser en graf med en syklus:

Her er trinnene for å gjøre dette:

Trinn 1) Finn noden med null innkommende kanter, en node med null grader.

Trinn 2) Lagre nullpunktsnoden i en kø eller stabel og fjern noden fra grafen.

Trinn 3) Slett deretter den utgående kanten fra den noden.

Dette vil redusere antall grader for neste node.

Topologisk rekkefølge krever at grafdatastrukturen ikke vil ha noen syklus.

En graf vil bli betraktet som en DAG hvis den følger disse kravene:

• En eller flere noder med en indegree-verdi på null.
• Grafen inneholder ingen syklus

Så lenge det er noder i grafen og grafen fortsatt er DAG, kjører vi de tre trinnene ovenfor. Ellers vil algoritmen falle inn i den sykliske avhengigheten, og Kahns algoritme vil ikke kunne finne en node med null i grader.

Hvordan Topologisk sortering fungerer

Her vil vi bruke "Kahns algoritme" for den topologiske typen. La oss si at vi har følgende graf:

Her er trinnene for Kahns algoritme:

Trinn 1) Beregn indegreen eller innkommende kant til alle noder i grafen.

OBS:

• Indegree betyr de rettede kantene som peker mot noden.
• Outdegree betyr de rettede kantene som kommer fra en node.

Her er indegreen og outgraden av grafen ovenfor:

Trinn 2) Finn noden med null ingrader eller null innkommende kanter.

Noden med null indegree betyr at ingen kanter kommer mot den noden. Node "A" har null grader, noe som betyr at det ikke er noen kant som peker mot node "A".

Så vi vil gjøre følgende handlinger:

• Fjern denne noden og dens utgående kanter (utgående kanter)
• Plasser noden i køen for bestilling.
• Oppdater antall grader for nabonoden til "A."

Trinn 3) Vi må finne en node med en indegree-verdi på null. I dette eksemplet har "B" og "C" null indegree.

Her kan vi ta en av disse to. La oss ta "B" og slette den fra grafen.

Oppdater deretter indegree-verdiene til andre noder.

Etter å ha utført disse operasjonene, vil grafen og køen vår se slik ut:

Trinn 4) Node "C" har ingen innkommende kant. Så vi vil fjerne node "C" fra grafen og skyve den inn i køen.

Vi kan også slette kanten som er utgående fra "C".

Nå vil grafen vår se slik ut:

Trinn 5) Vi kan se at nodene "D" og "F" har nullgraden. Vi tar en node og legger den i køen.

La oss ta ut "D" først. Da vil ingradantall for node "E" være 1. Nå vil det ikke være noen node fra D til E.

Vi må gjøre det samme for node "F", resultatet vårt vil være som følgende:

Trinn 6) Indegreen (inngående kanter) og outdegree (utgående kanter) til node "E" ble null. Så vi har oppfylt alle forutsetningene for node "E".

Her setter vi "E" på slutten av køen. Så vi har ingen noder igjen, så algoritmen slutter her.

Pseudokode for topologisk sortering

Her er pseudokoden for den topologiske sorteringen mens du bruker Kahns algoritme.

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

Topologisk sortering kan også implementeres ved hjelp av DFS (Dybde første søk) metode. Den tilnærmingen er imidlertid den rekursive metoden. Kahns algoritme er mer effektiv enn DFS-tilnærmingen.

C++ Implementering av Topologisk Sortering

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

Produksjon

0       1       2       3       5       4

Python Implementering av Topologisk Sortering

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

Produksjon

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

Sykliske grafer av topologisk sorteringsalgoritme

En graf som inneholder en syklus kan ikke ordnes topologisk. Som den sykliske grafen har avhengigheten på en syklisk måte.

Sjekk for eksempel denne grafen:

Denne grafen er ikke DAG (Directed Acyclic Graph) fordi A, B og C lager en syklus. Hvis du legger merke til det, er det ingen node med null i graders verdi.

I følge Kahns algoritme, hvis vi analyserer grafen ovenfor:

• Finn en node med null grader (ingen innkommende kanter).
• Fjern den noden fra grafen og skyv den til køen.
  Imidlertid, i grafen ovenfor, er det ingen node med null i grader. Hver node har en gradsverdi større enn 0.
• Returner en tom kø, siden den ikke kunne finne noen node med null i grader.

Vi kan oppdage sykluser ved å bruke den topologiske rekkefølgen med følgende trinn:

Trinn 1) Utfør topologisk sortering.

Trinn 2) Beregn det totale antallet elementer i den topologisk sorterte listen.

Trinn 3) Hvis antall elementer er lik det totale antallet toppunkt, er det ingen syklus.

Trinn 4) Hvis det ikke er lik antall toppunkter, er det minst én syklus i den gitte grafdatastrukturen.

Kompleksitetsanalyse av topologisk sort

Det er to typer kompleksitet i algoritmer. Det er de

1. Tidskompleksitet
2. Romkompleksitet

Disse kompleksitetene er representert med en funksjon som gir en generell kompleksitet.

Tidskompleksitet: Hele tidens kompleksitet er den samme for topologisk sortering. Det er verste, gjennomsnittlige og beste scenarioer for tidskompleksitet.

Tidskompleksiteten for topologisk sortering er O(E + V), her betyr E antall kanter i grafen, og V betyr antall toppunkter i grafen.

La oss bryte gjennom denne kompleksiteten:

Trinn 1) Til å begynne med vil vi beregne alle gradene. For å gjøre det må vi gå gjennom alle kantene, og til å begynne med vil vi tilordne alle V toppunktingrader til null. Så de trinnvise trinnene vi fullfører vil være O(V+E).

Trinn 2) Vi vil finne noden med null indegree verdi. Vi må søke fra V-tallet til toppunktet. Så trinnene som er fullført vil være O(V).

Trinn 3) For hver node med null grader, vil vi fjerne den noden og redusere graden. Det vil ta å utføre denne operasjonen for alle nodene O(E).

Trinn 4) Til slutt vil vi sjekke om det er noen syklus eller ikke. Vi vil sjekke om det totale antallet elementer i den sorterte matrisen er lik det totale antallet noder. Det vil ta O (1).

Så dette var den individuelle tidskompleksiteten for hvert trinn i den topologiske sorteringen eller topologiske rekkefølgen. Vi kan si at tidskompleksiteten fra beregningen ovenfor vil være O( V + E ); her betyr O kompleksitetsfunksjonen.

Romkompleksitet: Vi trengte O(V)-rom for å kjøre den topologiske sorteringsalgoritmen.

Her er trinnene der vi trengte plass til programmet:

• Vi måtte beregne alle gradene av noder som er tilstede i grafen. Siden grafen har totalt V-noder, må vi lage en matrise med størrelse V. Så plassen som kreves var O(V).
• En kødatastruktur ble brukt til å lagre noden med null indegree. Vi fjernet nodene med null indegree fra den originale grafen og plasserte dem i køen. For dette var nødvendig plass O(V).
• Arrayen heter «ordre». Det lagret nodene i topologisk rekkefølge. Det krevde også O(V) mellomrom.

Dette var den individuelle romkompleksiteten. Så vi må maksimere disse plassene i løpet av tiden.

Romkompleksitet står for O(V), der V betyr nummeret på toppunktet i grafen.

Anvendelse av topologisk sortering

Det er stor bruk for topologisk sortering. Her er noen av dem:

• Den brukes når Operating system trenger å utføre ressursallokeringen.
• Finne en syklus i grafen. Vi kan validere om grafen er DAG eller ikke med topologisk sortering.
• Setningsrekkefølge i appene for automatisk fullføring.
• Det brukes til å oppdage vranglås.
• Ulik type planlegging eller kursplanlegging bruker topologisk sortering.
• Løse avhengigheter. For eksempel, hvis du prøver å installere en pakke, kan den pakken også trenge andre pakker. Topologisk bestilling finner ut alle nødvendige pakker for å installere den gjeldende pakken.
• Linux bruker den topologiske sorteringen i "apt" for å sjekke avhengigheten til pakkene.