Topologisk sorteringsalgoritme: Python, C++ 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, den peger på. Denne algoritme følger visse regler gentagne gange, indtil sorteringen er fuldført.

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

Instrueret graf

Her kan vi se, at "A" ikke har nogen ingrad. Ingrad betyder den kant, der peger på en node. "B" og "C" har en forudsætning for "A", hvorefter "E" har 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:

Afhængighed af hver node (lineær rækkefølge)

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.

Her er trinnene til at gøre dette:

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

Trin 2) Gem den nul-i-graders-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 opfylder 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 en DAG, vil vi køre de ovenstående tre trin. Ellers vil algoritmen falde ind i den cykliske afhængighed, og Kahns algoritme vil ikke være i stand til at finde en node med nul in-grad.

Sådan fungerer topologisk sortering

Her vil vi bruge "Kahns algoritme" til den topologiske sortering. Lad os sige, at vi har følgende graf:

Her er trinnene 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 ingraden og outgraden af ​​ovenstående graf:

Trin 2) Find knuden med nul ingrader eller nul indgående kanter. Knuden med nul ingrader betyder, at der ikke er nogen kanter, der peger mod knuden. Knude "A" har nul ingrader, hvilket betyder, at der ikke er nogen kant, der peger mod knude "A". Så vi vil udføre følgende handlinger:

• Fjern denne node og dens udadgående kanter (udgående kanter).
• Placer noden i køen for bestilling.
• Opdater antallet af grader for nabonoden til "A".

Trin 3) Vi skal finde en node med en indegradsværdi på nul. I dette eksempel har "B" og "C" nul indegrad. Her kan vi tage en af ​​disse to. Lad os tage "B" og slette den fra grafen. Derefter opdatere indegradsværdierne for de andre noder. Efter at have udført disse operationer, vil vores graf og kø se således ud:

Trin 4) Knudepunktet “C” har ingen indgående kant. Så vi fjerner knudepunktet “C” fra grafen og sætter det i køen. Vi kan også slette den kant, 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 ingraden nul. Vi tager en node og sætter den i køen. Lad os først fjerne "D". Så vil ingradantallet 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", og vores resultat vil være som følger:

Trin 6) Indgraden (indgående kanter) og udgraden (udgående kanter) for knudepunktet "E" blev nul. Så vi har opfyldt alle forudsætningerne for knudepunktet "E". Her sætter vi "E" i slutningen af ​​køen. Så vi har ingen knudepunkter tilbage, og algoritmen slutter her.

Kaldenavn Code til topologisk sortering

Her er pseudokoden for den topologiske sortering, mens Kahns algoritme bruges.

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 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 topologisk ordnes, da den cykliske graf har afhængigheden på en cyklisk måde. Se for eksempel denne graf:

Denne graf er ikke en DAG (Directed Acyclic Graph), fordi A, B og C skaber en cyklus. Hvis du bemærker det, er der ingen node med nul værdi i grader. Ifølge Kahns algoritme, 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. I ovenstående graf er der dog ingen node med nul grader i in-grader. Hver node har en graders værdi større end 0.
• Returner en tom kø, da den ikke kunne finde nogen node med nul grader 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 hjørner, er der ingen cyklus.

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

Kompleksitetsanalyse af topologisk sort

Der er to typer kompleksitet i algoritmer. De er:

1. Tidskompleksitet
2. Rumkompleksitet

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

Tidskompleksitet: Al tidskompleksitet er den samme for topologisk sortering. Der er værst tænkelige, gennemsnitlige og bedste tænkelige scenarier for tidskompleksitet. Tidskompleksiteten for topologisk sortering er O(E + V), hvor E står for antallet af kanter i grafen, og V står for antallet af hjørner 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å dette var de individuelle tidskompleksiteter for hvert trin i den topologiske sortering eller topologiske ordning. 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 de trin, hvor vi havde brug for pladsen 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 "orden", som gemte noderne i topologisk rækkefølge. Det krævede også O (V) rum.

Dette var de individuelle rumkompleksiteter. Så vi er nødt til at maksimere disse rum i løbetid. Rumkompleksitet står for O(V), hvor V står for antallet af hjørner i grafen.

Anvendelse af topologisk sort

Der er en enorm anvendelse for topologisk sortering. Her er nogle af dem:

• Det bruges når en Operating system skal udføre ressourceallokeringen.
• Find en cyklus i grafen. Vi kan validere, om grafen er en DAG eller ej, med topologisk sortering.
• Sætningsrækkefølge i autofuldførelsesapps.
• Det bruges til at detektere blokeringer.
• Forskellige typer planlægning eller kursusplanlægning bruger topologisk 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.

Ofte Stillede Spørgsmål