Topologische sortering: Python, C++ algoritmevoorbeeld

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 naar het volgendewing voorbeeld:

Gerichte grafiek
Gerichte grafiek

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:

Afhankelijkheid van elk knooppunt

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.

Topologisch sorteeralgoritme

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 zijn en de grafiek nog steeds DAG is, voeren we de bovenstaande drie stappen uit. Anderwise, zal het algoritme in de cyclische afhankelijkheid vallen, en zal het algoritme van Kahn geen knooppunt met een graad van nul kunnen vinden.

Hoe topologische sortering werkt

Hier zullen we "Kahn's algoritme" gebruiken voor de topologische sortering. Laten we zeggen dat we de volgende informatie hebbenwing grafiek:

Topologische sorteerwerken

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:

Topologische sorteerwerken

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.

Dus we zullen het volgende doenwing acties:

  • 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'.

Topologische sorteerwerken

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.

Na het uitvoeren van deze bewerkingen zullen onze grafiek en wachtrij er als volgt uitzienwing:

Topologische sorteerwerken

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:

Topologische sorteerwerken

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 als volgt zijnwing:

Topologische sorteerwerken

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.

Topologische sorteerwerken

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:

Cyclische grafieken van topologisch sorteeralgoritme

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 following 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. Zij zijn

  1. Tijd Complexity
  2. Ruimte Complexity

Deze complexiteiten worden weergegeven met een functie die een algemene com biedtplexheid.

Tijd Complexiteit: Altijd complexDe kwaliteit is hetzelfde voor topologische sortering. Er zijn slechtste, gemiddelde en beste scenario's voor timecomplexheid.

De tijd complexDe waarde voor topologische sortering is O(E + V), hier betekent E het aantal randen in de grafiek, en V het aantal hoekpunten in de grafiek.

Laten we deze com doorbrekenplexiteit:

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 ingraden verwijderen we dat knooppunt en verlagen we de ingraden. 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 tijdcomplexvoor elke stap van de topologische sortering of topologische ordening. We kunnen zeggen dat de tijd complexuit de bovenstaande berekening zal O( V + E ) zijn; hier betekent O de complexity-functie.

Ruimte Complexiteit: 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 space complexiteit. We moeten deze ruimtes dus tijdens de looptijd maximaliseren.

Ruimte complexity staat voor O(V), waarbij V het nummer van het hoekpunt in de grafiek betekent.

Toepassing van topologische sortering

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

  • Het wordt gebruikt wanneer Besturingssysteem 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 deadlocks.
  • 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.