Topologische sortering: Python, C++ Algoritme 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 (Directed Acyclic Graph), zodat elk knooppunt in de geordende array verschijnt voordat alle andere knooppunten ernaar verwijzen. Dit algoritme volgt herhaaldelijk enkele regels totdat het sorteren is voltooid.

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

Hier kunnen we zien dat “A” geen indegree heeft. Het betekent de rand die naar een knooppunt wijst. “B” en “C” hebben als voorwaarde “A”, en “E” heeft als voorwaarde “D” en “F” knooppunten. Sommige knooppunten zijn afhankelijk van andere knooppunten.

Hier is nog een weergave van de bovenstaande grafiek:

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 voorbeeld toont een grafiek met een cyclus:

Hier zijn de stappen om dit te doen:

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

Stap 2) Bewaar dat knooppunt in graden in een wachtrij of stapel op nul en verwijder het knooppunt uit de grafiek.

Stap 3) Verwijder vervolgens de uitgaande rand van dat knooppunt.

Hierdoor wordt het aantal graden voor het volgende knooppunt verlaagd.

Topologische ordening vereist dat de grafiekgegevensstructuur geen enkele cyclus heeft.

Een grafiek wordt als een DAG beschouwd als deze aan deze vereisten voldoet:

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

Zolang er knooppunten in de grafiek staan ​​en de grafiek nog steeds DAG is, voeren we de bovenstaande drie stappen uit. Anders zal het algoritme in de cyclische afhankelijkheid vallen en zal Kahn's algoritme geen knooppunt met nul in-degree kunnen vinden.

Hoe topologische sortering werkt

Hier gebruiken we "Kahn's Algorithm" voor de topologische sortering. Laten we zeggen dat we de volgende grafiek hebben:

Hier zijn de stappen voor het Kahn-algoritme:

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

Opmerking:

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

Hier zijn de indegree en outdegree van de bovenstaande grafiek:

Stap 2) Zoek het knooppunt met nul ingraden of nul inkomende randen.

Het knooppunt met nul graden betekent dat er geen randen naar dat knooppunt komen. Knooppunt “A” heeft nul graden, wat betekent dat er geen rand is die naar knooppunt “A” wijst.

We zullen dus de volgende acties uitvoeren:

• Verwijder dit knooppunt en zijn uitgaande randen (uitgaande randen)
• Plaats het knooppunt in de wachtrij voor bestelling.
• Werk het aantal graden bij van het aangrenzende knooppunt van 'A'.

Stap 3) We moeten een knooppunt vinden met een indegree-waarde van nul. In dit voorbeeld hebben “B” en “C” een graad van nul.

Hier kunnen we een van deze twee nemen. Laten we “B” nemen en deze uit de grafiek verwijderen.

Werk vervolgens de indegree-waarden van andere knooppunten bij.

Nadat u deze bewerkingen hebt uitgevoerd, zien onze grafiek en wachtrij er als volgt uit:

Stap 4) Knooppunt “C” heeft geen inkomende flank. We zullen dus knooppunt “C” uit de grafiek verwijderen en in de wachtrij plaatsen.

We kunnen ook de rand verwijderen die uitgaand is van “C”.

Nu zal onze grafiek er als volgt uitzien:

Stap 5) We kunnen zien dat knooppunten “D” en “F” de ingraad nul hebben. We nemen een knooppunt en plaatsen het in de wachtrij.

Laten we eerst “D” verwijderen. Dan is de indegree-telling voor knooppunt “E” 1. Nu is er geen knooppunt van D naar E.

We moeten hetzelfde doen voor knooppunt “F”, ons resultaat zal er als volgt uitzien:

Stap 6) De indegree (ingaande randen) en outdegree (uitgaande randen) van knooppunt “E” werden nul. We hebben dus aan alle vereisten voor knooppunt “E” voldaan.

Hier plaatsen we “E” aan het einde van de wachtrij. We hebben dus geen knooppunten meer, dus het algoritme eindigt hier.

Pseudocode voor topologische sortering

Hier is de pseudocode voor de topologische sortering tijdens het gebruik van Kahn's 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

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 grafiek met een cyclus kan niet topologisch geordend worden. Omdat de cyclische grafiek de afhankelijkheid op een cyclische manier heeft.

Bekijk bijvoorbeeld deze grafiek:

Deze grafiek is geen DAG (Directed Acyclic Graph) omdat A, B en C een cyclus creëren. Als je het opmerkt: er is geen knooppunt met een waarde van nul graden.

Als we de bovenstaande grafiek analyseren volgens het algoritme van Kahn:

• Zoek een knooppunt met nul ingraden (geen inkomende randen).
• Verwijder dat knooppunt uit de grafiek en duw het naar de wachtrij.
  In de bovenstaande grafiek is er echter geen knooppunt met nul in graden. Elk knooppunt heeft een in-gradenwaarde groter dan 0.
• Retourneert een lege wachtrij, omdat er geen enkel knooppunt met nul in graden 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, is er geen sprake van een cyclus.

Stap 4) Als het niet gelijk is aan het aantal hoekpunten, dan is er minstens één cyclus in de gegeven grafiekgegevensstructuur.

Complexiteitsanalyse van topologische sortering

Er zijn twee soorten complexiteit in algoritmen. Ze zijn

1. Tijdcomplexiteit
2. Complexiteit van de ruimte

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

Tijdscomplexiteit: Alle tijdcomplexiteit is hetzelfde voor Topological Sorting. Er zijn worst-, average- en best-case-scenario's voor tijdcomplexiteit.

De tijdcomplexiteit voor topologische sortering is O(E + V), waarbij E het aantal randen in de grafiek aangeeft en V het aantal hoekpunten in de grafiek.

Laten we deze complexiteit eens 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 tijdcomplexiteit voor elke stap van de topologische sortering of topologische ordening. We kunnen zeggen dat de tijdcomplexiteit van de bovenstaande berekening O( V + E ) zal zijn; hierbij betekent O de complexiteitsfunctie.

Ruimtecomplexiteit: We hadden O(V)-ruimten nodig voor het uitvoeren van het topologische sorteeralgoritme.

Dit zijn de stappen waarbij we de ruimte voor het programma 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’. Dat bewaarde de knooppunten in topologische volgorde. Dat was ook nodig O (V) ruimten.

Dit waren de individuele ruimtecomplexiteit. Dus moeten we deze ruimtes maximaliseren in de runtime.

Ruimtecomplexiteit staat voor O(V), waarbij V het nummer van het hoekpunt in de grafiek aangeeft.

Toepassing van topologische sortering

Er is een enorm nut voor topologische sortering. Hier zijn er een aantal:

• Het wordt gebruikt wanneer Operating systeem moet de toewijzing van middelen uitvoeren.
• Een cyclus zoeken in de grafiek. We kunnen valideren of de grafiek DAG is of niet met topologische sortering.
• Zinsvolgorde in de apps voor automatisch aanvullen.
• Het wordt gebruikt voor detectie impasses.
• Verschillende soorten planning of cursusplanning gebruiken de 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.