Topologisk sortering: Python, C++ Algoritmexempel

Vad är topologisk sorteringsalgoritm?

Topologisk sortering är även känd som Kahns algoritm och är en populär sorteringsalgoritm. Med hjälp av en riktad graf som indata, sorterar Topologisk sortering noderna så att var och en visas före den den pekar på.

Denna algoritm tillämpas på en DAG (Directed Acyclic Graph) så att varje nod visas i den ordnade arrayen innan alla andra noder pekar på den. Denna algoritm följer vissa regler upprepade gånger tills sorteringen är klar.

För att förenkla, titta på följande exempel:

Regisserad graf
Regisserad graf

Här kan vi se att "A" inte har någon grad. Det betyder kanten som pekar mot en nod. "B" och "C" har ett krav på "A", sedan har "E" ett krav på "D" och "F" noder. Vissa av noderna är beroende av andra noder.

Här är en annan representation av ovanstående graf:

Beroende för varje nod

Beroende av varje nod (linjär ordning)

Så när vi skickar DAG (Directed Acyclic Graph) till den topologiska sorteringen, kommer det att ge oss en array med linjär ordning, där det första elementet inte har något beroende.

Topologisk sorteringsalgoritm

Detta exempel visar en graf med en cykel:

Här är stegen för att göra detta:

Steg 1) Hitta noden med noll inkommande kanter, en nod med noll grader.

Steg 2) Lagra den nollställande gradnoden i en kö eller stack och tar bort noden från grafen.

Steg 3) Ta sedan bort den utgående kanten från den noden.

Detta kommer att minska antalet grader för nästa nod.

Topologisk ordning kräver att grafdatastrukturen inte har någon cykel.

En graf kommer att betraktas som en DAG om den följer dessa krav:

  • En eller flera noder med indegree-värdet noll.
  • Grafen innehåller ingen cykel

Så länge det finns noder i grafen och grafen fortfarande är DAG kommer vi att köra ovanstående tre steg. Annars kommer algoritmen att falla in i det cykliska beroendet, och Kahns algoritm kommer inte att kunna hitta en nod med noll i grader.

Hur topologisk sortering fungerar

Här kommer vi att använda "Kahns algoritm" för den topologiska sorten. Låt oss säga att vi har följande graf:

Topologiska sorteringsverk

Här är stegen för Kahns algoritm:

Steg 1) Beräkna graden eller inkommande kant för alla noder i grafen.

Notera:

  • Indegree betyder de riktade kanterna som pekar mot noden.
  • Outgrade betyder de riktade kanterna som kommer från en nod.

Här är graden och graden av ovanstående graf:

Topologiska sorteringsverk

Steg 2) Hitta noden med noll grader eller noll inkommande kanter.

Noden med noll indegree betyder att inga kanter kommer mot den noden. Nod "A" har noll grader, vilket betyder att det inte finns någon kant som pekar mot nod "A".

Så vi kommer att göra följande åtgärder:

  • Ta bort denna nod och dess utgående kanter (utgående kanter)
  • Placera noden i kön för beställning.
  • Uppdatera antalet grader för grannoden för "A."

Topologiska sorteringsverk

Steg 3) Vi måste hitta en nod med indegree-värdet noll. I det här exemplet har "B" och "C" noll grad.

Här kan vi ta någon av dessa två. Låt oss ta "B" och ta bort det från grafen.

Uppdatera sedan indegree-värdena för andra noder.

Efter att ha utfört dessa operationer kommer vår graf och kö att se ut så här:

Topologiska sorteringsverk

Steg 4) Nod "C" har ingen inkommande kant. Så vi tar bort nod "C" från grafen och skjuter in den i kön.

Vi kan också ta bort kanten som är utgående från "C".

Nu kommer vår graf att se ut så här:

Topologiska sorteringsverk

Steg 5) Vi kan se att noderna "D" och "F" har graden noll. Vi tar en nod och lägger den i kön.

Låt oss ta ut "D" först. Då blir graden av gradtal för nod "E" 1. Nu kommer det inte att finnas någon nod från D till E.

Vi måste göra samma sak för nod "F", vårt resultat blir som följande:

Topologiska sorteringsverk

Steg 6) Ingraden (ingående kanter) och utgraden (utgående kanter) för nod "E" blev noll. Så vi har uppfyllt alla förutsättningar för nod "E".

Här sätter vi "E" i slutet av kön. Så vi har inga noder kvar, så algoritmen slutar här.

Topologiska sorteringsverk

Pseudokod för topologisk sortering

Här är pseudokoden för den topologiska sorteringen när du använder Kahns algoritm.

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 också implementeras med hjälp av DFS (Djup första sökning) metod. Det tillvägagångssättet är dock den rekursiva metoden. Kahns algoritm är mer effektiv än DFS-metoden.

C++ Implementering av 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 av 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]

Cykliska grafer för topologisk sorteringsalgoritm

En graf som innehåller en cykel kan inte ordnas topologiskt. Som den cykliska grafen har beroendet på ett cykliskt sätt.

Kolla till exempel denna graf:

Cykliska grafer för topologisk sorteringsalgoritm

Denna graf är inte DAG (Directed Acyclic Graph) eftersom A, B och C skapar en cykel. Om du märker att det inte finns någon nod med noll i graders värde.

Enligt Kahn's Algorithm, om vi analyserar ovanstående graf:

  • Hitta en nod med noll grader (inga inkommande kanter).
  • Ta bort den noden från grafen och skjut den till kön.
    Men i ovanstående graf finns det ingen nod med noll i grader. Varje nod har ett gradvärde som är större än 0.
  • Returnera en tom kö, eftersom den inte kunde hitta någon nod med noll i grader.

Vi kan upptäcka cykler med hjälp av den topologiska ordningen med följande steg:

Steg 1) Utför topologisk sortering.

Steg 2) Beräkna det totala antalet element i den topologiskt sorterade listan.

Steg 3) Om antalet element är lika med det totala antalet vertex, så finns det ingen cykel.

Steg 4) Om det inte är lika med antalet hörn, så finns det åtminstone en cykel i den givna grafdatastrukturen.

Komplexitetsanalys av topologisk sort

Det finns två typer av komplexitet i algoritmer. Det är de

  1. Tidskomplexitet
  2. Rymdkomplexitet

Dessa komplexiteter representeras med en funktion som ger en generell komplexitet.

Tidskomplexitet: Hela tidens komplexitet är densamma för topologisk sortering. Det finns värsta, genomsnittliga och bästa scenarier för tidskomplexitet.

Tidskomplexiteten för topologisk sortering är O(E + V), här betyder E antalet kanter i grafen och V betyder antalet hörn i grafen.

Låt oss bryta igenom denna komplexitet:

Steg 1) I början kommer vi att beräkna alla grader. För att göra det måste vi gå igenom alla kanter, och initialt kommer vi att tilldela alla V vertexgrader till noll. Så de inkrementella stegen vi slutför kommer att vara O(V+E).

Steg 2) Vi kommer att hitta noden med noll gradvärde. Vi måste söka från V-talet på vertexet. Så, stegen som slutförs kommer att vara O (V).

Steg 3) För varje nod med noll grader tar vi bort den noden och minskar graden. Att utföra denna operation för alla noder kommer att ta O(E).

Steg 4) Slutligen kommer vi att kontrollera om det finns någon cykel eller inte. Vi kommer att kontrollera om det totala antalet element i den sorterade arrayen är lika med det totala antalet noder. Det kommer ta O (1).

Så dessa var den individuella tidskomplexiteten för varje steg i den topologiska sorteringen eller topologiska ordningen. Vi kan säga att tidskomplexiteten från ovanstående beräkning kommer att vara O( V + E ); här betyder O komplexitetsfunktionen.

Rymdkomplexitet: Vi behövde O(V)-utrymmen för att köra den topologiska sorteringsalgoritmen.

Här är stegen där vi behövde utrymme för programmet:

  • Vi var tvungna att beräkna alla grader av noder som fanns i grafen. Eftersom grafen har totalt V-noder måste vi skapa en array av storlek V. Så det utrymme som krävdes var O (V).
  • En ködatastruktur användes för att lagra noden med noll indegree. Vi tog bort noderna med noll indegree från den ursprungliga grafen och placerade dem i kön. För detta var det utrymme som krävdes O (V).
  • Arrayen heter "order". Det lagrade noderna i topologisk ordning. Det krävdes också O (V) utrymmen.

Dessa var den individuella rymdkomplexiteten. Så vi måste maximera dessa utrymmen under körtiden.

Rymdkomplexitet står för O(V), där V betyder numret på hörnet i grafen.

Tillämpning av topologisk sort

Det finns en enorm användning för topologisk sortering. Här är några av dem:

  • Den används när Operatingssystem behöver utföra resurstilldelningen.
  • Hitta en cykel i grafen. Vi kan validera om grafen är DAG eller inte med topologisk sortering.
  • Meningsordning i apparna för automatisk komplettering.
  • Det används för att upptäcka dödlägen.
  • Olika typer av schemaläggning eller kursschemaläggning använder den topologiska sorteringen.
  • Att lösa beroenden. Om du till exempel försöker installera ett paket kan det paketet också behöva andra paket. Topologisk ordning tar reda på alla nödvändiga paket för att installera det aktuella paketet.
  • Linux använder den topologiska sorteringen i "apt" för att kontrollera paketens beroende.