Topoloogiline sortimine: Python, C++ Algoritmi näide

Mis on topoloogilise sortimise algoritm?

Topoloogilist sortimist tuntakse ka Kahni algoritmina ja see on populaarne sortimisalgoritm. Kasutades sisendina suunatud graafikut, sorteerib Topoloogiline sortimine sõlmed nii, et igaüks ilmub enne seda, millele see osutab.

Seda algoritmi rakendatakse DAG-le (Directed Acyclic Graph), nii et iga sõlm ilmub järjestatud massiivisse enne, kui kõik teised sõlmed sellele osutatakse. See algoritm järgib mõnda reeglit korduvalt, kuni sortimine on lõpetatud.

Lihtsustamiseks vaadake järgmist näidet:

Suunatud graafik
Suunatud graafik

Siin näeme, et "A"-l pole indegree. See tähendab serva, mis osutab sõlmele. “B” ja “C” eeltingimuseks on “A”, siis “E” eeltingimuseks on “D” ja “F” sõlmed. Mõned sõlmed sõltuvad teistest sõlmedest.

Siin on veel üks ülaltoodud graafiku esitus:

Iga sõlme sõltuvus

Iga sõlme sõltuvus (lineaarne järjestamine)

Seega, kui edastame DAG-i (Directed Acyclic Graph) topoloogilisele sortimisele, annab see meile lineaarse järjestusega massiivi, kus esimene element ei sõltu.

Topoloogilise sortimise algoritm

See näide näitab graafikut tsükliga:

Selleks toimige järgmiselt.

Step 1) Leidke null sissetuleva servaga sõlm, null kraadiga sõlm.

Step 2) Salvestage see nullitav sõlm järjekorda või virna ja eemaldage sõlm graafikult.

Step 3) Seejärel kustutage sellest sõlmest väljuv serv.

See vähendab järgmise sõlme astmete arvu.

Topoloogiline järjestamine eeldab, et graafiku andmestruktuuril ei oleks tsüklit.

Graafiku loetakse DAG-ks, kui see järgib järgmisi nõudeid:

  • Üks või mitu sõlme, mille inkraadi väärtus on null.
  • Graafik ei sisalda ühtegi tsüklit

Kuni graafikul on sõlmed ja graafik on endiselt DAG, teostame ülaltoodud kolme sammu. Vastasel juhul langeb algoritm tsüklilisse sõltuvusse ja Kahni algoritm ei suuda leida null-kraadiga sõlme.

Kuidas topoloogiline sortimine töötab

Siin kasutame topoloogiliseks sortimiseks “Kahni algoritmi”. Oletame, et meil on järgmine graafik:

Topoloogilised sortimistööd

Siin on Kahni algoritmi juhised:

Step 1) Arvutage graafiku kõigi sõlmede mittekraadine või sissetulev serv.

Märge:

  • Indegree tähendab sõlmele suunatud suunatud servi.
  • Outdegree tähendab suunatud servi, mis tulevad sõlmest.

Siin on ülaltoodud graafiku indegreen ja outgrade:

Topoloogilised sortimistööd

Step 2) Leidke sõlm, mille sissetulevad servad on null või null.

Nullkraadiga sõlm tähendab, et selle sõlme poole ei tule ühtegi serva. Sõlmel A on null kraadi, mis tähendab, et sõlmele A ei osutata.

Seega teeme järgmised toimingud:

  • Eemaldage see sõlm ja selle välimised servad (väljuvad servad)
  • Asetage sõlm tellimise järjekorda.
  • Värskendage "A" naabersõlme kraadide arvu.

Topoloogilised sortimistööd

Step 3) Peame leidma sõlme, mille indegree väärtus on null. Selles näites on “B” ja “C” nullaste.

Siin võime võtta ühe neist kahest. Võtame “B” ja kustutame selle graafikult.

Seejärel värskendage teiste sõlmede mittekraadiväärtusi.

Pärast nende toimingute tegemist näevad meie graafik ja järjekord välja järgmine:

Topoloogilised sortimistööd

Step 4) Sõlmel C ei ole sissetulevat serva. Seega eemaldame graafikult sõlme “C” ja lükkame selle järjekorda.

Samuti saame kustutada C-st väljuva serva.

Nüüd näeb meie graafik välja selline:

Topoloogilised sortimistööd

Step 5) Näeme, et sõlmede “D” ja “F” aste on null. Võtame sõlme ja paneme selle järjekorda.

Võtame kõigepealt välja tähe "D". Siis on sõlme “E” mittekraadide arv 1. Nüüd pole sõlme D-st E-ni.

Peame tegema sama sõlme "F" puhul, meie tulemus on järgmine:

Topoloogilised sortimistööd

Step 6) Sõlme “E” indegree (sisenevad servad) ja välimine (väljaminevad servad) muutus nulliks. Seega oleme täitnud kõik sõlme “E” eeltingimused.

Siin paneme järjekorra lõppu tähe "E". Niisiis, meil pole ühtegi sõlme alles, nii et algoritm lõpeb siin.

Topoloogilised sortimistööd

Topoloogilise sortimise pseudokood

Siin on topoloogilise sortimise pseudokood Kahni algoritmi kasutamisel.

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

Topoloogilist sortimist saab realiseerida ka DFS-i (Sügavus Esimene otsing) meetod. See lähenemisviis on aga rekursiivne meetod. Kahni algoritm on tõhusam kui DFS-i lähenemisviis.

C++ Topoloogilise sorteerimise rakendamine

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

Väljund

0       1       2       3       5       4

Python Topoloogilise sorteerimise rakendamine

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

Väljund

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

Topoloogilise sortimisalgoritmi tsüklilised graafikud

Tsüklit sisaldavat graafikut ei saa topoloogiliselt järjestada. Kuna tsüklilisel graafikul on sõltuvus tsükliliselt.

Näiteks kontrollige seda graafikut:

Topoloogilise sortimisalgoritmi tsüklilised graafikud

See graafik ei ole DAG (suunatud atsükliline graafik), kuna A, B ja C loovad tsükli. Kui märkate, pole ühtegi sõlme, mille väärtus oleks null.

Kahni algoritmi järgi, kui analüüsime ülaltoodud graafikut:

  • Leidke null kraadiga sõlm (ilma sissetulevate servadeta).
  • Eemaldage see sõlm graafikult ja lükake see järjekorda.
    Ülaltoodud graafikul pole aga ühtegi sõlme, mille kraadides oleks null. Iga sõlme väärtus on suurem kui 0.
  • Tagasta tühi järjekord, kuna see ei leidnud ühtegi sõlme, mille kraadides oleks null.

Tsükleid saame tuvastada topoloogilise järjestuse abil järgmiste sammudega:

Step 1) Tehke topoloogiline sortimine.

Step 2) Arvutage topoloogiliselt sorteeritud loendi elementide koguarv.

Step 3) Kui elementide arv võrdub tipu koguarvuga, siis tsüklit pole.

Step 4) Kui see ei ole võrdne tippude arvuga, on antud graafiku andmestruktuuris vähemalt üks tsükkel.

Topoloogilise sortimise keerukuse analüüs

Algoritmide keerukus on kahte tüüpi. Nad on

  1. Aja keerukus
  2. Ruumi keerukus

Need keerukused on esitatud funktsiooniga, mis annab üldise keerukuse.

Aja keerukus: Topoloogilise sortimise puhul on kogu aja keerukus sama. Ajalise keerukuse jaoks on olemas halvimad, keskmised ja parimad stsenaariumid.

Topoloogilise sorteerimise ajaline keerukus on O(E + V), siin tähistab E graafiku servade arvu ja V graafiku tippude arvu.

Murrame sellest keerukusest läbi:

Step 1) Alguses arvutame kõik astmed. Selleks peame läbima kõik servad ja algselt määrame kõik V tipu indegreid nulliks. Niisiis, järkjärgulised sammud, mida me lõpetame, on O(V+E).

Step 2) Leiame null indegree väärtusega sõlme. Peame otsima tipu V numbri järgi. Niisiis, sammud on lõpetatud O(V).

Step 3) Iga nullkraadiga sõlme puhul eemaldame selle sõlme ja vähendame inkrementi. Selle toimingu sooritamine kõigi sõlmede jaoks võtab aega O(E).

Step 4) Lõpuks kontrollime, kas tsükkel on olemas või mitte. Kontrollime, kas sorteeritud massiivi elementide koguarv võrdub sõlmede koguarvuga. See võtab O (1).

Niisiis, need olid topoloogilise sortimise või topoloogilise järjestuse iga etapi individuaalne ajaline keerukus. Võime öelda, et ülaltoodud arvutuse ajaline keerukus on O( V + E ); siin tähendab O keerukuse funktsiooni.

Ruumi keerukus: Topoloogilise sortimisalgoritmi käitamiseks vajasime O (V) ruume.

Siin on sammud, kus vajasime programmi jaoks ruumi:

  • Pidime arvutama kõik graafikul olevate sõlmede astmed. Kuna graafikul on kokku V-sõlme, peame looma massiivi suurusega V. Seega oli vaja ruumi O(V).
  • Nullindraadiga sõlme salvestamiseks kasutati Queue andmestruktuuri. Eemaldasime algsest graafikust nullindraadiga sõlmed ja paigutasime need järjekorda. Selleks oli vaja ruumi O(V).
  • Massiivi nimi on "tellimus". See salvestas sõlmed topoloogilises järjekorras. See nõudis ka O(V) tühikud.

Need olid individuaalse ruumi keerukus. Seega peame neid ruume tööaja jooksul maksimeerima.

Ruumi keerukus tähistab O(V), kus V tähistab graafikul oleva tipu arvu.

Topoloogilise sortimise rakendamine

Topoloogilisest sortimisest on palju kasu. Siin on mõned neist:

  • Seda kasutatakse siis, kui Operaasjade süsteem vajab ressursside eraldamist.
  • Tsükli leidmine graafikult. Saame kontrollida, kas graafik on DAG või mitte, topoloogilise sortimisega.
  • Lausete järjestamine automaatse täitmise rakendustes.
  • Seda kasutatakse tuvastamiseks ummikseisud.
  • Erinevat tüüpi ajakava või kursuse ajakava kasutab topoloogilist sortimist.
  • Sõltuvuste lahendamine. Näiteks kui proovite installida paketti, võib see pakett vajada ka muid pakette. Topoloogiline järjestamine selgitab välja kõik praeguse paketi installimiseks vajalikud paketid.
  • Linux kasutab pakettide sõltuvuse kontrollimiseks topoloogilist sortimist "apt".