Topologisk sorteringsalgoritme: Python, C++ 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 tabellen før alle andre noder den peker til. Denne algoritmen følger noen regler gjentatte ganger til sorteringen er fullført.

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

Regissert graf

Her kan vi se at «A» ikke har noen ingrad. Ingrad betyr kanten som peker mot en node. «B» og «C» har en forutsetning av «A», deretter har «E» en forutsetning av noder av typen «D» og «F». Noen av nodene er avhengige av andre noder.

Her er en annen representasjon av grafen ovenfor:

Avhengighet av hver node (lineær rekkefølge)

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.

Her er trinnene for å gjøre dette:

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

Trinn 2) Lagre den null-i-grader-noden i en kø eller stabel, og fjern noden fra grafen.

Trinn 3) Slett deretter den utgående kanten fra den noden. Dette vil redusere antallet grader for den neste noden.

Topologisk rekkefølge krever at grafens datastruktur ikke har noen syklus. En graf vil bli ansett 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 en DAG, vil vi kjøre de tre trinnene ovenfor. Ellers vil algoritmen falle inn i den sykliske avhengigheten, og Kahns algoritme vil ikke kunne finne en node med null in-grad.

Hvordan Topologisk sortering fungerer

Her skal vi bruke «Kahns algoritme» for den topologiske sorteringen. 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 ingraden og outgraden til grafen ovenfor:

Trinn 2) Finn noden med null ingrader eller null innkommende kanter. Noden med null ingrader betyr at ingen kanter kommer mot noden. Noden «A» har null ingrader, noe som betyr at det ikke er noen kant som peker mot node «A». Så vi skal gjøre følgende:

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

Trinn 3) Vi må finne en node med en ingradverdi på null. I dette eksemplet har «B» og «C» null ingrad. Her kan vi ta en av disse to. La oss ta «B» og slette den fra grafen. Deretter oppdaterer vi ingradverdiene til de andre nodene. Etter å ha utført disse operasjonene, vil grafen og køen vår se slik ut:

Trinn 4) Noden «C» har ingen innkommende kant. Så vi fjerner noden «C» fra grafen og legger 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 ingraden null. Vi tar en node og legger den i køen. La oss først fjerne «D». Da vil ingradantallet 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», og resultatet vårt vil bli som følger:

Trinn 6) Ingraden (inngående kanter) og utgraden (utgående kanter) for noden «E» ble null. Dermed har vi oppfylt alle forutsetningene for noden «E». Her setter vi «E» på slutten av køen. Dermed har vi ingen noder igjen, og algoritmen slutter her.

Kallenavn Code for topologisk sortering

Her er pseudokoden for den topologiske sorteringen ved bruk av 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 0 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, ettersom den sykliske grafen har avhengigheten på en syklisk måte. Se for eksempel denne grafen:

Denne grafen er ikke en DAG (Directed Acyclic Graph) fordi A, B og C lager en syklus. Hvis du legger merke til det, finnes det ingen node med null verdi i grader. I følge Kahns algoritme, hvis vi analyserer grafen ovenfor:

• Finn en node med null grader (ingen innkommende kanter).
• Fjern noden fra grafen og send den til køen. I grafen ovenfor er det imidlertid ingen node med null grader i tommer. Hver node har en graders verdi større enn 0.
• Returner en tom kø, ettersom den ikke kunne finne noen node med null grader i tommer.

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 antallet elementer er lik det totale antallet hjørner, finnes det ingen syklus.

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

Kompleksitetsanalyse av topologisk sort

Det finnes to typer kompleksitet i algoritmer. De er:

1. Tidskompleksitet
2. Romkompleksitet

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

Tidskompleksitet: All tidskompleksitet er den samme for topologisk sortering. Det finnes verst tenkelige, gjennomsnittlige og beste tenkelige scenarioer for tidskompleksitet. Tidskompleksiteten for topologisk sortering er O(E + V), der E betyr antall kanter i grafen, og V betyr antall hjørner 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 de individuelle tidskompleksitetene for hvert trinn i den topologiske sorteringen eller topologiske ordningen. 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 plassen 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).
• Arrayet heter «orden», som lagret nodene i topologisk rekkefølge. Det krevde også O(V) mellomrom.

Dette var de individuelle romkompleksitetene. Så vi må maksimere disse rommene i løpet av kjøretiden. Romkompleksitet står for O(V), der V betyr nummeret på hjørnet i grafen.

Anvendelse av topologisk sortering

Topologisk sortering har stor bruk. Her er noen av dem:

• Den brukes når en Operating system trenger å utføre ressursallokeringen.
• Finne en syklus i grafen. Vi kan validere om grafen er en DAG eller ikke med topologisk sortering.
• Setningsrekkefølge i appene for automatisk fullføring.
• Den brukes til å oppdage vranglås.
• Ulike typer 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.

Spørsmål og svar