Topologinen lajittelualgoritmi: Python, C++ esimerkki

Mikä on topologinen lajittelualgoritmi?

Topologinen lajittelu tunnetaan myös nimellä Kahnin algoritmi, ja se on suosittu lajittelualgoritmi. Käyttämällä suunnattua kuvaajaa syötteenä Topologinen lajittelu lajittelee solmut siten, että jokainen näkyy ennen sitä, johon se osoittaa.

Tätä algoritmia sovelletaan DAG-taulukkoon (Directed Acyclic Graph) siten, että jokainen solmu esiintyy järjestetyssä taulukossa ennen kaikkia muita solmuja, joihin se osoittaa. Tämä algoritmi noudattaa tiettyjä sääntöjä toistuvasti, kunnes lajittelu on valmis.

Yksinkertaistaaksesi, katso seuraava esimerkki:

Ohjattu graafi

Tässä näemme, että ”A”:lla ei ole sisäänpäin suuntautuvaa astetta. Sisäänpäin suuntautuva aste tarkoittaa reunaa, joka osoittaa solmuun. ”B”:llä ja ”C”:llä on edellytys ”A”:lle, ja ”E”:llä on edellytys ”D”:lle ja ”F”:lle. Jotkut solmut ovat riippuvaisia ​​toisista solmuista.

Tässä on toinen esitys yllä olevasta kaaviosta:

Jokaisen solmun riippuvuus (lineaarinen järjestys)

Joten kun siirrämme DAG:n (Directed Acyclic Graph) topologiseen lajitteluun, se antaa meille taulukon lineaarisella järjestyksellä, jossa ensimmäisellä elementillä ei ole riippuvuutta.

Voit tehdä tämän seuraavasti:

Vaihe 1) Etsi solmu, jolla on nolla saapuvaa reunaa, solmu, jolla on nolla astetta.

Vaihe 2) Tallenna kyseinen nolla-astesolmu jonoon tai pinoon ja poista solmu graafista.

Vaihe 3) Poista sitten kyseisen solmun lähtevä reuna. Tämä vähentää seuraavan solmun sisäänpäin suuntautuvien asteiden määrää.

Topologinen järjestys edellyttää, että graafin tietorakenteessa ei ole sykliä. Graafia pidetään DAG:na, jos se täyttää seuraavat vaatimukset:

• Yksi tai useampi solmu, jonka asteen arvo on nolla.
• Graafi ei sisällä yhtään sykliä.

Niin kauan kuin graafissa on solmuja ja graafi on edelleen DAG, suoritamme yllä olevat kolme vaihetta. Muuten algoritmi joutuu sykliseen riippuvuuteen, eikä Kahnin algoritmi löydä solmua, jonka aste on nolla.

Kuinka topologinen lajittelu toimii

Tässä käytämme Kahnin algoritmia topologiseen lajitteluun. Oletetaan, että meillä on seuraava graafi:

Tässä ovat Kahnin algoritmin vaiheet:

Vaihe 1) Laske kaavion kaikkien solmujen inaste tai sisääntuleva reuna.

Huomautus:

• Indegree tarkoittaa suunnattuja reunoja, jotka osoittavat solmuun.
• Outdegree tarkoittaa suunnattuja reunoja, jotka tulevat solmusta.

Tässä on yllä olevan graafin sisään- ja ulospäinsuuntautuminen:

Vaihe 2) Etsi solmu, jossa on nolla sisäänpäin suuntautuvaa astetta tai nolla sisäänpäin suuntautuvaa kaarraa. Solmu, jossa on nolla sisäänpäin suuntautuvaa astetta, tarkoittaa, että solmua kohti ei ole tulossa kaaria. Solmulla "A" on nolla sisäänpäin suuntautuvaa astetta, mikä tarkoittaa, että solmuun "A" ei ole osoittavaa kaarraa. Joten teemme seuraavat toimenpiteet:

• Poista tämä solmu ja sen ulkoreunat (lähtevät reunat).
• Aseta solmu tilausjonoon.
• Päivitä "A":n naapurisolmun asteluku.

Vaihe 3) Meidän on löydettävä solmu, jonka sisääntuloaste on nolla. Tässä esimerkissä solmuilla "B" ja "C" on sisääntuloaste nolla. Tässä voimme valita jommankumman näistä kahdesta. Otetaan "B" ja poistetaan se graafista. Päivitetään sitten muiden solmujen sisääntuloastearvot. Näiden toimintojen suorittamisen jälkeen graafi ja jono näyttävät seuraavalta:

Vaihe 4) Solmulla ”C” ei ole sisääntulevaa kaarretta. Joten poistamme solmun ”C” graafista ja siirrämme sen jonoon. Voimme myös poistaa solmusta ”C” lähtevän kaaren. Nyt graafimme näyttää tältä:

Vaihe 5) Näemme, että solmujen “D” ja “F” astearvo on nolla. Laitamme yhden solmun jonoon. Poistetaan ensin “D”. Tällöin solmun “E” astearvo on 1. Nyt solmujen D ja E välillä ei ole solmuja. Meidän on tehtävä sama solmulle “F”, ja tuloksemme on seuraavanlainen:

Vaihe 6) Solmun ”E” sisäänpäin suuntautuvat reunat ja ulospäin suuntautuvat reunat nollautuivat. Näin ollen kaikki solmun ”E” edellytykset ovat täyttyneet. Tässä solmu ”E” sijoitetaan jonon loppuun. Solmuja ei siis ole enää jäljellä, ja algoritmi päättyy tähän.

Pseudo Code topologista lajittelua varten

Tässä on pseudokoodi topologiselle lajittelulle Kahnin algoritmia käyttäen.

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

Topologinen lajittelu voidaan toteuttaa myös DFS:n (Syvyys Ensimmäinen haku) menetelmä. Tämä lähestymistapa on kuitenkin rekursiivinen menetelmä. Kahnin algoritmi on tehokkaampi kuin DFS-lähestymistapa.

C++ Topologisen lajittelun toteutus

#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();
}

ulostulo

0       1       2       3       5       4

Python Topologisen lajittelun toteutus

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()

ulostulo

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

Topologisen lajittelualgoritmin sykliset kuvaajat

Syklin sisältävää graafia ei voida topologisesti järjestää, koska syklisellä graafilla on riippuvuus syklisellä tavalla. Tarkastellaan esimerkiksi tätä graafia:

Tämä graafi ei ole DAG (Directed Acyclic Graph), koska A, B ja C muodostavat syklin. Huomaathan, ettei missään solmussa ole nollaa astearvoa. Kahnin algoritmin mukaan, jos analysoimme yllä olevaa graafia:

• Etsi solmu, jossa on nolla astetta (ei sisääntulevia reunoja).
• Poista kyseinen solmu graafista ja siirrä se jonoon. Yllä olevassa graafissa ei kuitenkaan ole solmua, jonka sisääntuloaste olisi nolla. Jokaisen solmun sisääntuloasteen arvo on suurempi kuin 0.
• Palauttaa tyhjän jonon, koska ei löytänyt solmua, jonka sisääntuloaste olisi nolla.

Voimme havaita syklit käyttämällä topologista järjestystä seuraavilla vaiheilla:

Vaihe 1) Suorita topologinen lajittelu.

Vaihe 2) Laske topologisesti järjestetyn listan elementtien kokonaismäärä.

Vaihe 3) Jos elementtien lukumäärä on yhtä suuri kuin solmujen kokonaismäärä, sykliä ei ole.

Vaihe 4) Jos se ei ole yhtä suuri kuin solmujen lukumäärä, annetussa graafin tietorakenteessa on ainakin yksi sykli.

Topologisen lajittelun monimutkaisuusanalyysi

Algoritmeja on kahdenlaisia ​​monimutkaisuuksia. Ne ovat:

1. Ajan monimutkaisuus
2. Avaruuden monimutkaisuus

Nämä monimutkaisuudet esitetään funktiolla, joka tarjoaa yleisen monimutkaisuuden.

Ajan monimutkaisuus: Topologisessa lajittelussa aikakompleksisuus on aina sama. Aikakompleksisuudelle on olemassa pahin, keskimääräinen ja paras tapaus. Topologisen lajittelun aikakompleksisuus on O(E + V), jossa E tarkoittaa graafin kaarien lukumäärää ja V tarkoittaa graafin solmujen lukumäärää.

Murtaudutaanpa tämän monimutkaisuuden läpi:

Vaihe 1) Aluksi laskemme kaikki asteet. Tätä varten meidän täytyy käydä läpi kaikki reunat, ja aluksi määritämme kaikki V-pistein asteet nollaan. Joten suorittamamme vaiheet ovat O(V+E).

Vaihe 2) Löydämme solmun, jonka inastearvo on nolla. Meidän täytyy etsiä kärjen V-numerosta. Joten vaiheet on suoritettu O (V).

Vaihe 3) Jokaisen solmun, jolla on nolla astetta, poistamme kyseisen solmun ja vähennämme astetta. Tämän toiminnon suorittaminen kaikille solmuille kestää O(E).

Vaihe 4) Lopuksi tarkistamme, onko sykliä vai ei. Tarkistamme, onko lajitellun taulukon elementtien kokonaismäärä yhtä suuri kuin solmujen kokonaismäärä. Se tulee ottamaan O (1).

Nämä olivat siis topologisen lajittelun tai topologisen järjestämisen kunkin vaiheen yksittäiset aikakompleksisuudet. Voimme sanoa, että yllä olevan laskelman mukainen aikakompleksisuus on O(V + E); tässä O tarkoittaa kompleksisuusfunktiota.

Avaruuden monimutkaisuus: Tarvitsimme O(V) avaruuksia topologisen lajittelualgoritmin suorittamiseen. Tässä ovat vaiheet, joissa tarvitsimme tilaa ohjelmalle:

• Meidän piti laskea kaikki kaaviossa olevien solmujen asteet. Koska kaaviossa on yhteensä V-solmuja, meidän on luotava joukko, jonka koko on V. Tarvittava tila oli siis O (V).
• Jonotietorakennetta käytettiin solmun tallentamiseen nolla-asteella. Poistimme nolla-astetta sisältävät solmut alkuperäisestä kaaviosta ja asetimme ne jonoon. Tätä varten tarvittava tila oli O (V).
• Taulukon nimi on ”order”, ja se tallentaa solmut topologisessa järjestyksessä. Tämä edellytti myös O (V) tilat.

Nämä olivat yksittäisiä avaruuskompleksisuuksia. Joten meidän täytyy maksimoida nämä avaruudet suorituksen aikana. Avaruuskompleksisuus on lyhenne O(V):stä, jossa V tarkoittaa graafin solmun numeroa.

Topologisen lajittelun soveltaminen

Topologiselle lajittelulle on valtavasti käyttöä. Tässä on joitakin niistä:

• Sitä käytetään, kun Operating-järjestelmä täytyy suorittaa resurssien allokointi.
• Syklin löytäminen graafista. Voimme varmistaa topologisella lajittelulla, onko graafi DAG vai ei.
• Lausejärjestys automaattisen täydennyksen sovelluksissa.
• Sitä käytetään havaitsemiseen umpikujaan.
• Erilaiset aikataulutustyypit tai kurssien aikataulutus käyttävät topologista lajittelua.
• Riippuvuuden ratkaiseminen. Jos esimerkiksi yrität asentaa paketin, se saattaa tarvita myös muita paketteja. Topologinen järjestys selvittää kaikki nykyisen paketin asentamiseen tarvittavat paketit.
• Linux käyttää topologista lajittelua "apt":ssa tarkistaakseen pakettien riippuvuuden.

UKK