Topologisk sorteringsalgoritm: Python, C++ Exempelvis

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 före alla andra noder som den pekar på. Algoritmen följer vissa regler upprepade gånger tills sorteringen är klar.

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

Regisserad graf

Här kan vi se att "A" inte har någon ingrad. Ingrad betyder kanten som pekar mot en nod. "B" och "C" har en förutsättning för "A", sedan har "E" en förutsättning för noder "D" och "F". Vissa av noderna är beroende av andra noder.

Här är en annan representation av grafen ovan:

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.

Så här gör du:

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

Steg 2) Lagra den noll-i-grader-noden i en kö eller stack och ta bort noden från grafen.

Steg 3) Ta sedan bort den utgående kanten från den noden. Detta minskar antalet grader för nästa nod.

Topologisk ordning kräver att grafens datastruktur inte har någon cykel. En graf betraktas som en DAG om den uppfyller 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 en DAG, kommer vi att köra de tre stegen ovan. Annars kommer algoritmen att hamna i det cykliska beroendet, och Kahns algoritm kommer inte att kunna hitta en nod med noll in-grad.

Hur topologisk sortering fungerar

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

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

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

Obs:

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

Här är ingraden och outgraden för grafen ovan:

Steg 2) Hitta noden med noll ingrader eller noll inkommande kanter. Noden med noll ingrader betyder att inga kanter kommer mot den noden. Nod "A" har noll ingrader, vilket betyder att det inte finns någon kant som pekar mot nod "A". Så vi kommer att göra följande:

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

Steg 3) Vi behöver hitta en nod med ett indegree-värde på noll. I det här exemplet har "B" och "C" noll indegree. Här kan vi ta endera av dessa två. Låt oss ta "B" och ta bort det från grafen. Sedan uppdatera 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:

Steg 4) Noden "C" har ingen inkommande kant. Så vi tar bort noden "C" från grafen och lägger 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:

Steg 5) Vi kan se att noderna "D" och "F" har ingraden noll. Vi tar en nod och lägger den i kön. Låt oss först ta bort "D". Då blir ingradantalet för nod "E" 1. Nu kommer det inte att finnas någon nod från D till E. Vi behöver göra detsamma för nod "F", och vårt resultat blir följande:

Steg 6) Ingraden (ingående kanter) och utgraden (utgående kanter) för noden "E" blev noll. Så vi har uppfyllt alla förutsättningar för noden "E". Här placerar vi "E" i slutet av kön. Så vi har inga noder kvar, och algoritmen slutar här.

Pseudo Code för topologisk sortering

Här är pseudokoden för den topologiska sorteringen med 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 0 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 vara topologiskt ordnad, eftersom den cykliska grafen har beroendet på ett cykliskt sätt. Se till exempel denna graf:

Denna graf är inte en DAG (Directed Acyclic Graph) eftersom A, B och C skapar en cykel. Om du märker det finns det ingen nod med noll i grader. Enligt Kahns algoritm, om vi analyserar grafen ovan:

• Hitta en nod med noll grader (inga inkommande kanter).
• Ta bort den noden från grafen och skicka den till kön. I grafen ovan finns det dock ingen nod med noll grader i tum. Varje nod har ett grader i tum som är större än 0.
• Returnera en tom kö, eftersom den inte kunde hitta någon nod med noll in-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 noder, finns det ingen cykel.

Steg 4) Om det inte är lika med antalet noder, finns det minst en cykel i den givna grafdatastrukturen.

Komplexitetsanalys av topologisk sort

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

1. Tidskomplexitet
2. Rymdkomplexitet

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

Tidskomplexitet: All tidskomplexitet är densamma för topologisk sortering. Det finns värsta tänkbara, genomsnittliga och bästa tänkbara scenarier för tidskomplexitet. Tidskomplexiteten för topologisk sortering är O(E + V), där E står för antalet kanter i grafen och V står för antalet noder 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 de individuella tidskomplexiteterna för varje steg i den topologiska sorteringen eller topologiska ordningen. Vi kan säga att tidskomplexiteten från ovanstående beräkning blir 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 utrymmet 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).
• Matrisen heter "ordning", vilket lagrar noderna i topologisk ordning. Det krävde också O (V) utrymmen.

Dessa var de individuella rumskomplexiteterna. Så vi behöver maximera dessa rum under körtiden. Rumskomplexitet står för O(V), där V betyder numret på noden 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 en Operatingssystem behöver utföra resurstilldelningen.
• Hitta en cykel i grafen. Vi kan validera om grafen är en DAG eller inte med topologisk sortering.
• Meningsordning i apparna för automatisk komplettering.
• Den används för att upptäcka dödlägen.
• Olika typer av schemaläggning eller kursschemaläggning använder topologisk sortering.
• 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.

Vanliga frågor