Topologisk sortering: Python, C++ Algoritme eksempel

Hvad er topologisk sorteringsalgoritme?

Topologisk sortering er også kendt som Kahns algoritme og er en populær sorteringsalgoritme. Ved at bruge en rettet graf som input sorterer Topologisk sortering noderne, så hver af dem vises før den, den peger på.

Denne algoritme anvendes på en DAG (Directed Acyclic Graph), så hver node vises i det ordnede array, før alle andre noder peges på det. Denne algoritme følger nogle regler gentagne gange, indtil sorteringen er afsluttet.

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

Her kan vi se, at "A" ikke har nogen grad. Det betyder kanten, der peger på en knude. "B" og "C" har en forudsætning for "A", så har "E" en forudsætning for "D" og "F" noder. Nogle af noderne er afhængige af andre noder.

Her er en anden repræsentation af ovenstående graf:

Så når vi sender DAG (Directed Acyclic Graph) til den topologiske sortering, vil det give os en matrix med lineær rækkefølge, hvor det første element ikke har nogen afhængighed.

Dette eksempel viser en graf med en cyklus:

Her er trinene til at gøre dette:

Trin 1) Find noden med nul indgående kanter, en node med nul grader.

Trin 2) Gem den nulstillede node i en kø eller stak og fjern noden fra grafen.

Trin 3) Slet derefter den udgående kant fra den node.

Dette vil mindske antallet af grader for den næste node.

Topologisk rækkefølge kræver, at grafens datastruktur ikke har nogen cyklus.

En graf vil blive betragtet som en DAG, hvis den følger disse krav:

• En eller flere noder med en indegree-værdi på nul.
• Grafen indeholder ingen cyklus

Så længe der er noder i grafen, og grafen stadig er DAG, kører vi ovenstående tre trin. Ellers vil algoritmen falde ind i den cykliske afhængighed, og Kahn's Algorithm vil ikke være i stand til at finde en node med nul i grader.

Sådan fungerer topologisk sortering

Her vil vi bruge "Kahn's Algorithm" til den topologiske sortering. Lad os sige, at vi har følgende graf:

Her er trinene til Kahns algoritme:

Trin 1) Beregn indegreen eller indgående kant af alle noder i grafen.

Bemærk:

• Indegree betyder de rettede kanter, der peger på noden.
• Outdegree betyder de rettede kanter, der kommer fra en node.

Her er indegreen og outgraden af ​​ovenstående graf:

Trin 2) Find noden med nul indegres eller nul indgående kanter.

Noden med nul indegree betyder, at ingen kanter kommer mod den node. Node "A" har nul grader, hvilket betyder, at der ikke er nogen kant, der peger på node "A".

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

• Fjern denne node og dens udgående kanter (udgående kanter)
• Placer noden i køen for bestilling.
• Opdater tællingen i grader for naboknudepunktet for "A".

Trin 3) Vi skal finde en node med en indegree-værdi på nul. I dette eksempel har "B" og "C" nul indegree.

Her kan vi tage en af ​​disse to. Lad os tage "B" og slette det fra grafen.

Opdater derefter indegree-værdierne for andre noder.

Efter at have udført disse operationer, vil vores graf og kø se ud som følgende:

Trin 4) Node "C" har ingen indgående kant. Så vi fjerner node "C" fra grafen og skubber den ind i køen.

Vi kan også slette kanten, der er udgående fra "C".

Nu vil vores graf se sådan ud:

Trin 5) Vi kan se, at noderne "D" og "F" har graden nul. Vi tager en node og sætter den i køen.

Lad os tage "D" ud først. Så vil indegreantælleren for node "E" være 1. Nu vil der ikke være nogen node fra D til E.

Vi skal gøre det samme for node "F", vores resultat vil være som følgende:

Trin 6) Indegreen (indgående kanter) og udgraden (udgående kanter) af node "E" blev nul. Så vi har opfyldt alle forudsætningerne for node "E".

Her sætter vi "E" for enden af ​​køen. Så vi har ingen noder tilbage, så algoritmen slutter her.

Pseudokode til topologisk sortering

Her er pseudokoden for den topologiske sortering, mens du bruger 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 hjælp af DFS (Dybde første søgning) metode. Den tilgang er dog den rekursive metode. Kahns algoritme er mere effektiv end DFS-tilgangen.

C++ Implementering af 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();
}

Produktion

0       1       2       3       5       4

Python Implementering af 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()

Produktion

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

Cykliske grafer af topologisk sorteringsalgoritme

En graf, der indeholder en cyklus, kan ikke ordnes topologisk. Som den cykliske graf har afhængigheden på en cyklisk måde.

Tjek for eksempel denne graf:

Denne graf er ikke DAG (Directed Acyclic Graph), fordi A, B og C skaber en cyklus. Hvis du bemærker, er der ingen node med nul i graders værdi.

Ifølge Kahn's Algorithm, hvis vi analyserer ovenstående graf:

• Find en node med nul grader (ingen indgående kanter).
• Fjern den node fra grafen og skub den til køen.
  Men i ovenstående graf er der ingen node med nul i grader. Hver node har en in-grad værdi større end 0.
• Returner en tom kø, da den ikke kunne finde nogen node med nul i grader.

Vi kan detektere cyklusser ved hjælp af den topologiske rækkefølge med følgende trin:

Trin 1) Udfør topologisk sortering.

Trin 2) Beregn det samlede antal elementer i den topologisk sorterede liste.

Trin 3) Hvis antallet af elementer er lig med det samlede antal toppunkter, er der ingen cyklus.

Trin 4) Hvis det ikke er lig med antallet af hjørner, så er der mindst én cyklus i den givne grafdatastruktur.

Kompleksitetsanalyse af topologisk sort

Der er to typer kompleksitet i algoritmer. Det er de

1. Tidskompleksitet
2. Rumkompleksitet

Disse kompleksiteter er repræsenteret med en funktion, der giver en generel kompleksitet.

Tidskompleksitet: Altid kompleksitet er den samme for topologisk sortering. Der er værste, gennemsnitlige og bedste scenarier for tidskompleksitet.

Tidskompleksiteten for topologisk sortering er O(E + V), her betyder E antallet af kanter i grafen, og V betyder antallet af toppunkter i grafen.

Lad os bryde igennem denne kompleksitet:

Trin 1) I begyndelsen vil vi beregne alle graderne. For at gøre det skal vi gå gennem alle kanterne, og til at begynde med vil vi tildele alle V vertex-grader til nul. Så de trinvise trin, vi gennemfører, vil være O(V+E).

Trin 2) Vi finder noden med nul indegree værdi. Vi skal søge fra toppunktets V-nummer. Så de gennemførte trin vil være O (V).

Trin 3) For hver knude med nul grader, vil vi fjerne denne node og formindske indegreen. Det vil tage at udføre denne operation for alle noderne O(E).

Trin 4) Til sidst vil vi kontrollere, om der er nogen cyklus eller ej. Vi vil kontrollere, om det samlede antal elementer i det sorterede array er lig med det samlede antal noder. Det vil tage O (1).

Så disse var den individuelle tidskompleksitet for hvert trin i den topologiske sortering eller topologiske rækkefølge. Vi kan sige, at tidskompleksiteten fra ovenstående beregning vil være O( V + E ); her betyder O kompleksitetsfunktionen.

Rumkompleksitet: Vi havde brug for O(V)-rum til at køre den topologiske sorteringsalgoritme.

Her er trinene, hvor vi havde brug for plads til programmet:

• Vi var nødt til at beregne alle de grader af noder, der er til stede i grafen. Da grafen har i alt V-noder, er vi nødt til at skabe en matrix af størrelse V. Så den nødvendige plads var O (V).
• En kødatastruktur blev brugt til at lagre noden med nul indegree. Vi fjernede noderne med nul indegree fra den originale graf og placerede dem i køen. Til dette var den nødvendige plads O (V).
• Arrayet hedder "ordre". Det lagrede noderne i topologisk rækkefølge. Det krævede også O (V) rum.

Disse var den individuelle rumkompleksitet. Så vi er nødt til at maksimere disse pladser i løbetiden.

Rumkompleksitet står for O(V), hvor V betyder nummeret på toppunktet i grafen.

Anvendelse af topologisk sort

Der er stor brug for topologisk sortering. Her er nogle af dem:

• Det bruges når Operating system skal udføre ressourceallokeringen.
• At finde en cyklus i grafen. Vi kan validere om grafen er DAG eller ej med topologisk sortering.
• Sætningsrækkefølge i autofuldførelsesapps.
• Det bruges til at opdage blokeringer.
• Forskellig type planlægning eller kursusplanlægning bruger den topologiske sortering.
• Løsning af afhængigheder. For eksempel, hvis du prøver at installere en pakke, kan den pakke muligvis også have brug for andre pakker. Topologisk bestilling finder ud af alle de nødvendige pakker for at installere den aktuelle pakke.
• Linux bruger den topologiske sortering i "apt" til at kontrollere pakkernes afhængighed.