Topoloogilise sortimise algoritm: Python, C++ 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 suunatud atsüklilise graafi (DAG) puhul nii, et iga sõlm kuvatakse järjestatud massiivis enne kõiki teisi sõlmi, millele see osutab. See algoritm järgib teatud reegleid korduvalt, kuni sortimine on lõppenud.

Lihtsustamiseks vaadake järgmist näidet:

Suunatud graafik

Siin näeme, et „A”-l puudub sõltumatu aste. Sisemine aste tähendab serva, mis osutab sõlmele. „B” ja „C” eelduseks on „A” ning „E” eelduseks on „D” ja „F” sõlmed. Mõned sõlmed sõltuvad teistest sõlmedest.

Siin on ülaltoodud graafiku teine ​​esitus:

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.

Selleks toimige järgmiselt.

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

Step 2) Salvesta see nullastmeline sõlm järjekorda või pinu ja eemalda sõlm graafikult.

Step 3) Seejärel kustuta sellest sõlmest väljuv serv. See vähendab järgmise sõlme sissetulevate kraadide arvu.

Topoloogiline järjestus eeldab, et graafi andmestruktuuril ei tohi olla tsüklit. Graafi loetakse DAG-iks, kui see vastab järgmistele nõuetele:

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

Seni kuni graafis on sõlmi ja graaf on endiselt DAG, teostame ülaltoodud kolm sammu. Vastasel juhul langeb algoritm tsüklilisse sõltuvusse ja Kahni algoritm ei suuda leida nullastmega sõlme.

Kuidas topoloogiline sortimine töötab

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

Siin on Kahni algoritmi sammud:

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 sise- ja välisaste:

Step 2) Leia sõlm, mille sisendkraadide arv on null või sissetulevate servade arv null. Null sisendkraadiga sõlm tähendab, et selle sõlme suunas ei tule ühtegi serva. Sõlmel „A“ on null sisendkraadi, mis tähendab, et ükski serv ei osuta sõlmele „A“. Seega teeme järgmised toimingud:

• Eemalda see sõlm ja selle välisservad (väljuvad servad).
• Asetage sõlm tellimise järjekorda.
• Uuenda „A” naabersõlme astmete arvu.

Step 3) Peame leidma sõlme, mille indegrade väärtus on null. Selles näites on "B" ja "C" indegrade null. Siin võime võtta ükskõik kumma neist kahest. Võtame "B" ja kustutame selle graafikult. Seejärel uuendame teiste sõlmede indegrade väärtusi. Pärast nende toimingute tegemist näevad meie graaf ja järjekord välja järgmised:

Step 4) Sõlmel „C“ puudub sisenev serv. Seega eemaldame sõlme „C“ graafikult ja lisame selle järjekorda. Samuti saame kustutada serva, mis väljub sõlmest „C“. Nüüd näeb meie graaf välja selline:

Step 5) Näeme, et sõlmede "D" ja "F" iseaste on null. Võtame ühe sõlme ja paneme selle järjekorda. Eemaldame kõigepealt sõlme "D". Siis on sõlme "E" iseastete arv 1. Nüüd ei ole sõlmest D sõlme E ühtegi sõlme. Peame sama tegema sõlme "F" jaoks ja tulemus on järgmine:

Step 6) Sõlme „E“ sisekraad (sissetulevad servad) ja väliskraad (väljuvad servad) muutusid nulliks. Seega oleme täitnud kõik sõlme „E“ eeldused. Siin paneme „E“ järjekorra lõppu. Seega pole meil ühtegi sõlme alles ja algoritm lõpeb siin.

Pseudo Code topoloogiliseks sortimiseks

Siin on Kahni algoritmi kasutava topoloogilise sortimise pseudokood.

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

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 graafi ei saa topoloogiliselt järjestada, kuna tsüklilisel graafil on sõltuvus tsüklilisel viisil. Näiteks vaadake seda graafi:

See graaf ei ole DAG (suunatud atsükliline graaf), kuna A, B ja C moodustavad tsükli. Nagu näete, pole ühtegi sõlme, mille astme väärtus oleks null. Kahni algoritmi kohaselt, kui analüüsime ülaltoodud graafi:

• Leidke null kraadiga sõlm (ilma sissetulevate servadeta).
• Eemalda see sõlm graafikult ja lisa see järjekorda. Ülaltoodud graafikul pole aga ühtegi sõlme, mille sisendkraadide väärtus oleks null. Igal sõlmel on sisendkraadide väärtus suurem kui 0.
• Tagasta tühi järjekord, kuna ei leitud ühtegi sõlme, mille sissetulevate kraadide arv 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 on võrdne tippude koguarvuga, siis tsüklit ei ole.

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

Topoloogilise sortimise keerukuse analüüs

Algoritmides on kahte tüüpi keerukust. Need on:

1. Aja keerukus
2. Ruumi keerukus

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

Aja keerukus: Topoloogilise sortimise puhul on ajaline keerukus sama. Ajalise keerukuse puhul on olemas halvim, keskmine ja parim stsenaarium. Topoloogilise sortimise ajaline keerukus on O(E + V), kus E tähistab graafi servade arvu ja V tähistab graafi tippude arvu.

Murrame selle keerukuse üle:

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

Seega olid need topoloogilise sortimise või topoloogilise järjestamise iga sammu individuaalsed ajalised keerukused. Võime öelda, et ülaltoodud arvutuse ajaline keerukus on O(V + E); siin tähendab O keerukusfunktsiooni.

Ruumi keerukus: Topoloogilise sortimise algoritmi käivitamiseks vajasime O(V) tühikuid. 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 „order“ ja see salvestas sõlmed topoloogilises järjekorras. See nõudis ka O(V) tühikud.

Need olid individuaalsed ruumi keerukused. Seega peame need ruumid jooksuaja jooksul maksimeerima. Ruumi keerukus tähistab O(V), kus V tähistab graafi tipu numbrit.

Topoloogilise sortimise rakendamine

Topoloogilisel sortimisel on tohutu kasutusala. Siin on mõned neist:

• Seda kasutatakse siis, kui Operaasjade süsteem vajab ressursside eraldamist.
• Tsükli leidmine graafis. Topoloogilise sortimise abil saame kontrollida, kas tegemist on DAG-graafiga või mitte.
• Lausete järjestamine automaatse täitmise rakendustes.
• Seda kasutatakse tuvastamiseks ummikseisud.
• Erinevat tüüpi ajakava või kursuste ajakava koostamisel kasutatakse 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".

KKK