Topologisch sorteeralgoritme: Python, C++ Voorbeeld

Wat is een topologisch sorteeralgoritme?

Topologische sortering is ook bekend als het algoritme van Kahn en is een populair sorteeralgoritme. Met behulp van een gerichte grafiek als invoer sorteert Topological Sort de knooppunten zodat ze allemaal verschijnen vóór het knooppunt waarnaar het verwijst.

Dit algoritme wordt toegepast op een DAG (gerichte acyclische graaf) zodat elk knooppunt in de gesorteerde lijst verschijnt vóór alle andere knooppunten waarnaar het verwijst. Dit algoritme volgt herhaaldelijk bepaalde regels totdat de sortering is voltooid.

Om het te vereenvoudigen, kijk eens naar het volgende voorbeeld:

Gerichte grafiek

Hier zien we dat "A" geen inkomende verbinding heeft. Een inkomende verbinding is de verbinding die naar een knooppunt wijst. "B" en "C" hebben "A" als voorwaarde, en "E" heeft "D" en "F" als voorwaarde. Sommige knooppunten zijn afhankelijk van andere knooppunten.

Hier is een andere weergave van de bovenstaande grafiek:

Afhankelijkheid van elk knooppunt (lineaire ordening)

Dus als we de DAG (Directed Acyclic Graph) doorgeven aan de topologische soort, geeft dit ons een array met lineaire ordening, waarbij het eerste element geen afhankelijkheid heeft.

Dit zijn de stappen om dit te doen:

Stap 1) Zoek het knooppunt met nul inkomende randen, een knooppunt met nul graden.

Stap 2) Plaats dat knooppunt met een inkomende graad van nul in een wachtrij of stapel en verwijder het knooppunt uit de grafiek.

Stap 3) Verwijder vervolgens de uitgaande verbinding van dat knooppunt. Hierdoor wordt de inkomende graad van het volgende knooppunt verlaagd.

Topologische ordening vereist dat de graafdatastructuur geen cycli bevat. Een graaf wordt als een gerichte acyclische graaf (DAG) beschouwd als deze aan de volgende eisen voldoet:

• Een of meer knooppunten met een indegree-waarde van nul.
• De grafiek bevat geen cyclus.

Zolang er knooppunten in de graaf aanwezig zijn en de graaf nog steeds een gerichte acyclische graaf (DAG) is, zullen we de bovenstaande drie stappen uitvoeren. Anders zal het algoritme in een cyclische afhankelijkheid terechtkomen en zal het algoritme van Kahn geen knooppunt met een in-graad van nul kunnen vinden.

Hoe topologische sortering werkt

Hier gebruiken we het algoritme van Kahn voor de topologische sortering. Stel dat we de volgende graaf hebben:

Hieronder volgen de stappen voor het algoritme van Kahn:

Stap 1) Bereken de ingraad of inkomende rand van alle knooppunten in de grafiek.

Let op:

• Indegree betekent de gerichte randen die naar het knooppunt wijzen.
• Outdegree betekent de gerichte randen die uit een knooppunt komen.

Hieronder staan ​​de inkomende en uitgaande graden van de bovenstaande grafiek:

Stap 2) Zoek het knooppunt met een inkomende graad van nul, oftewel nul inkomende kanten. Een knooppunt met een inkomende graad van nul betekent dat er geen kanten naar dat knooppunt wijzen. Knooppunt "A" heeft een inkomende graad van nul, wat betekent dat er geen kant naar knooppunt "A" wijst. We zullen daarom de volgende stappen uitvoeren:

• Verwijder dit knooppunt en de bijbehorende uitgaande verbindingen (out-gree edges).
• Plaats het knooppunt in de wachtrij voor bestelling.
• Werk het aantal inkomende knooppunten van het buurknooppunt "A" bij.

Stap 3) We moeten een knooppunt vinden met een inkomende graad van nul. In dit voorbeeld hebben "B" en "C" een inkomende graad van nul. We kunnen hier een van deze twee kiezen. Laten we "B" nemen en deze uit de graaf verwijderen. Vervolgens werken we de inkomende graden van de andere knooppunten bij. Na deze bewerkingen zien onze graaf en wachtrij er als volgt uit:

Stap 4) Knooppunt "C" heeft geen inkomende verbinding. Daarom verwijderen we knooppunt "C" uit de grafiek en plaatsen we het in de wachtrij. We kunnen ook de uitgaande verbinding van "C" verwijderen. Onze grafiek ziet er nu als volgt uit:

Stap 5) We zien dat de knooppunten "D" en "F" een inkomende graad van nul hebben. We nemen een knooppunt en plaatsen het in de wachtrij. Laten we eerst "D" eruit halen. Dan is de inkomende graad voor knooppunt "E" 1. Nu is er geen verbinding meer tussen D en E. We moeten hetzelfde doen voor knooppunt "F", en het resultaat zal er als volgt uitzien:

Stap 6) De inkomende en uitgaande graad van knooppunt "E" zijn nul geworden. We hebben dus aan alle voorwaarden voor knooppunt "E" voldaan. We plaatsen "E" nu aan het einde van de wachtrij. Er zijn geen knooppunten meer over en het algoritme eindigt hier.

Pseudo Code voor topologische sortering

Hieronder staat de pseudocode voor de topologische sortering met behulp van het algoritme van 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

Topologische sortering kan ook worden geïmplementeerd met behulp van de DFS (Diepte eerste zoekopdracht) methode. Deze benadering is echter de recursieve methode. Het algoritme van Kahn is efficiënter dan de DFS-aanpak.

C++ Implementatie van topologische 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();
}

uitgang

0       1       2       3       5       4

Python Implementatie van topologische 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()

uitgang

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

Cyclische grafieken van topologisch sorteeralgoritme

Een graaf die een cyclus bevat, kan niet topologisch geordend zijn, omdat de cyclische graaf een cyclische afhankelijkheid heeft. Bekijk bijvoorbeeld deze graaf:

Deze grafiek is geen DAG (Directed Acyclic Graph) omdat A, B en C een cyclus vormen. Zoals je ziet, is er geen knooppunt met een in-graad van nul. Volgens het algoritme van Kahn, als we de bovenstaande grafiek analyseren:

• Zoek een knooppunt met nul ingraden (geen inkomende randen).
• Verwijder dat knooppunt uit de grafiek en voeg het toe aan de wachtrij. In de bovenstaande grafiek is er echter geen enkel knooppunt met een in-graad van nul. Elk knooppunt heeft een in-graad die groter is dan 0.
• Retourneer een lege wachtrij, omdat er geen knooppunt met een in-graad van nul kon worden gevonden.

We kunnen cycli detecteren met behulp van de topologische ordening met de volgende stappen:

Stap 1) Voer topologische sortering uit.

Stap 2) Bereken het totale aantal elementen in de topologisch gesorteerde lijst.

Stap 3) Als het aantal elementen gelijk is aan het totale aantal hoekpunten, dan is er geen cyclus.

Stap 4) Als het niet gelijk is aan het aantal knooppunten, dan bevat de gegeven graafdatastructuur minstens één cyclus.

Complexiteitsanalyse van topologische sortering

Er zijn twee soorten complexiteit in algoritmen. Dat zijn:

1. Tijdcomplexiteit
2. Complexiteit van de ruimte

Deze complexiteiten worden weergegeven met een functie die een algemene complexiteit oplevert.

Tijdscomplexiteit: De tijdscomplexiteit is voor topologische sortering altijd gelijk. Er zijn scenario's voor de slechtste, gemiddelde en beste tijdscomplexiteit. De tijdscomplexiteit voor topologische sortering is O(E + V), waarbij E het aantal randen in de graaf is en V het aantal knooppunten in de graaf.

Laten we deze complexiteit doorbreken:

Stap 1) In het begin berekenen we alle ingraden. Om dat te doen, moeten we alle randen doorlopen, en in eerste instantie zullen we alle V-hoekpunten in graden toewijzen aan nul. De stapsgewijze stappen die we voltooien zullen dus zijn O(V+E).

Stap 2) We zullen het knooppunt vinden met een indegree-waarde van nul. We moeten zoeken vanaf het V-nummer van het hoekpunt. De voltooide stappen zullen dus zijn O (V).

Stap 3) Voor elk knooppunt met nul graden verwijderen we dat knooppunt en verlagen we de graden. Het uitvoeren van deze bewerking voor alle knooppunten duurt O(E).

Stap 4) Ten slotte zullen we controleren of er een cyclus is of niet. We zullen controleren of het totale aantal elementen in de gesorteerde array gelijk is aan het totale aantal knooppunten. Het zal nemen O (1).

Dit waren dus de individuele tijdcomplexiteiten voor elke stap van de topologische sortering of topologische ordening. We kunnen stellen dat de tijdcomplexiteit uit de bovenstaande berekening O(V + E) zal zijn; hierbij staat O voor de complexiteitsfunctie.

Ruimtecomplexiteit: We hadden O(V) geheugenruimte nodig om het topologische sorteeralgoritme uit te voeren. Hieronder volgen de stappen waarvoor we geheugenruimte nodig hadden:

• We moesten alle ingraden van knooppunten in de grafiek berekenen. Omdat de grafiek in totaal V-knooppunten heeft, moeten we een array van maat V maken. De benodigde ruimte was dus O (V).
• Er werd een wachtrijgegevensstructuur gebruikt om het knooppunt met nul graden op te slaan. We hebben de knooppunten met nul graden uit de oorspronkelijke grafiek verwijderd en in de wachtrij geplaatst. Hiervoor was de benodigde ruimte aanwezig O (V).
• De array heet "order" en slaat de knooppunten op in topologische volgorde. Dat vereiste ook... O (V) ruimten.

Dit waren de individuele ruimtecomplexiteiten. We moeten deze ruimtes dus maximaliseren tijdens de looptijd. Ruimtecomplexiteit staat voor O(V), waarbij V het aantal knooppunten in de graaf is.

Toepassing van topologische sortering

Topologische sortering kent talloze toepassingen. Hier zijn er een paar:

• Het wordt gebruikt wanneer een Operating systeem moet de toewijzing van middelen uitvoeren.
• Een cyclus in de graaf vinden. We kunnen met behulp van topologische sortering controleren of de graaf een gerichte acyclische graaf (DAG) is of niet.
• Zinsvolgorde in de apps voor automatisch aanvullen.
• Het wordt gebruikt voor het detecteren van impasses.
• Verschillende soorten roosters of cursusplanning maken gebruik van topologische sortering.
• Afhankelijkheden oplossen. Als u bijvoorbeeld een pakket probeert te installeren, heeft dat pakket mogelijk ook andere pakketten nodig. Topologische ordening ontdekt alle benodigde pakketten om het huidige pakket te installeren.
• Linux gebruikt de topologische sortering in “apt” om de afhankelijkheid van de pakketten te controleren.

Veelgestelde vragen