Topologinen lajittelu: Python, C++ Algoritmi 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 käytetään DAG:ssa (Directed Acyclic Graph) niin, että jokainen solmu näkyy järjestetyssä taulukossa ennen kuin kaikki muut solmut osoitetaan siihen. Tämä algoritmi noudattaa joitain sääntöjä toistuvasti, kunnes lajittelu on valmis.

Yksinkertaistaaksesi, katso seuraava esimerkki:

Tässä voimme nähdä, että "A":lla ei ole arvoa. Se tarkoittaa reunaa, joka osoittaa solmuun. "B":n ja "C:n" edellytyksenä on "A", sitten "E:n" edellytyksenä on "D" ja "F"-solmut. Jotkut solmuista ovat riippuvaisia ​​muista solmuista.

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

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.

Tässä esimerkissä on kaavio ja sykli:

Tässä on ohjeet tämän tekemiseen:

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

Vaihe 2) Tallenna tämä nollaa asteen solmu jonoon tai pinoon ja poistaa solmun kaaviosta.

Vaihe 3) Poista sitten lähtevä reuna kyseisestä solmusta.

Tämä vähentää seuraavan solmun asteen määrää.

Topologinen järjestys edellyttää, että graafin tietorakenteessa ei ole sykliä.

Kaaviota pidetään DAG:na, jos se noudattaa näitä vaatimuksia:

• Yksi tai useampi solmu, jonka asteen arvo on nolla.
• Kaavio ei sisällä jaksoa

Niin kauan kuin kaaviossa on solmuja ja graafi on edelleen DAG, suoritamme edellä mainitut kolme vaihetta. Muuten algoritmi putoaa sykliseen riippuvuuteen, eikä Kahnin algoritmi löydä solmua, jolla on nolla-aste.

Kuinka topologinen lajittelu toimii

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

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 kaavion epä- ja ulko-aste:

Vaihe 2) Etsi solmu, jossa on nolla astetta tai nolla saapuvaa reunaa.

Solmu, jonka astetta on nolla, tarkoittaa, että mitään reunoja ei tule tätä solmua kohti. Solmussa "A" on nolla astetta, mikä tarkoittaa, että siellä ei ole reunaa, joka osoittaa solmuun "A".

Joten teemme seuraavat toimet:

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

Vaihe 3) Meidän on löydettävä solmu, jonka inaste-arvo on nolla. Tässä esimerkissä "B" ja "C" ovat nolla-astetta.

Tässä voimme ottaa jommankumman näistä kahdesta. Otetaan "B" ja poistetaan se kaaviosta.

Päivitä sitten muiden solmujen inastearvot.

Kun olet suorittanut nämä toiminnot, kaaviomme ja jonomme näyttävät tältä:

Vaihe 4) Solmulla "C" ei ole sisääntulevaa reunaa. Joten poistamme solmun "C" kaaviosta ja työnnämme sen jonoon.

Voimme myös poistaa C:stä lähtevän reunan.

Nyt kaaviomme näyttää tältä:

Vaihe 5) Näemme, että solmujen “D” ja “F” astetta on nolla. Otamme solmun ja laitamme sen jonoon.

Otetaan ensin "D" pois. Sitten solmun "E" inasteluku on 1. Nyt ei ole solmua D:stä E:hen.

Meidän on tehtävä sama solmulle "F", tuloksemme on seuraava:

Vaihe 6) Solmun “E” inaste (sisääntulevat reunat) ja ulkoaste (lähtevät reunat) muuttuivat nollaksi. Olemme siis täyttäneet kaikki solmun "E" edellytykset.

Tässä laitamme "E" jonon loppuun. Meillä ei siis ole enää yhtään solmua jäljellä, joten algoritmi päättyy tähän.

Pseudokoodi topologiselle lajittelulle

Tässä on pseudokoodi topologiselle lajittelulle käytettäessä Kahnin algoritmia.

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

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

Jakson sisältävää kuvaajaa ei voida järjestää topologisesti. Koska syklisellä Graafilla on riippuvuus syklisellä tavalla.

Tarkista esimerkiksi tämä kaavio:

Tämä kuvaaja ei ole DAG (Directed Acyclic Graph), koska A, B ja C luovat syklin. Jos huomaat, ei ole solmua, jonka asteen arvo on nolla.

Kahnin algoritmin mukaan, jos analysoimme yllä olevaa kuvaajaa:

• Etsi solmu, jossa on nolla astetta (ei sisääntulevia reunoja).
• Poista kyseinen solmu kaaviosta ja työnnä se jonoon.
  Yllä olevassa kaaviossa ei kuitenkaan ole solmua, jossa on nolla asteina. Jokaisen solmun asteen arvo on suurempi kuin 0.
• Palauta tyhjä jono, koska se ei löytänyt solmua, jonka asteina 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 kärjen kokonaismäärä, sykliä ei ole.

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

Topologisen lajittelun monimutkaisuusanalyysi

Algoritmeissa on kahta tyyppiä monimutkaisuutta. He ovat

1. Ajan monimutkaisuus
2. Avaruuden monimutkaisuus

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

Ajan monimutkaisuus: Kaikki aika monimutkaisuus on sama topologisessa lajittelussa. Ajan monimutkaisuudesta on olemassa pahin, keskimääräinen ja paras tapaus.

Topologisen lajittelun aikamonimutkaisuus on O(E + V), tässä E tarkoittaa graafin reunojen määrää ja V kuvaa graafin kärkien määrää.

Murretaan tämä monimutkaisuus:

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 yksilöllinen aika monimutkaisuus jokaiselle topologisen lajittelun tai topologisen järjestyksen vaiheelle. Voimme sanoa, että aika monimutkaisuus yllä olevasta laskelmasta on O( V + E ); tässä O tarkoittaa monimutkaisuusfunktiota.

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 "järjestys". Se tallensi solmut topologisessa järjestyksessä. Sitäkin vaadittiin O (V) tilat.

Nämä olivat yksilöllisen tilan monimutkaisuus. Joten meidän on maksimoitava nämä tilat ajon aikana.

Avaruuden kompleksisuus tarkoittaa O(V), jossa V tarkoittaa graafin kärjen numeroa.

Topologisen lajittelun soveltaminen

Topologiselle lajittelulle on valtavasti hyötyä. Tässä muutama niistä:

• Sitä käytetään kun Operating-järjestelmä täytyy suorittaa resurssien allokointi.
• Syklin etsiminen kaaviosta. Voimme vahvistaa, onko Graafi DAG vai ei topologisella lajittelulla.
• Lausejärjestys automaattisen täydennyksen sovelluksissa.
• Sitä käytetään havaitsemiseen umpikujaan.
• Erityyppinen aikataulutus tai kurssin ajoitus käyttää 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.