Topológiai rendezés: Python, C++ Algoritmus példa

Mi az a topológiai rendezési algoritmus?

A topológiai rendezés Kahn-algoritmusként is ismert, és egy népszerű rendezési algoritmus. Bemenetként irányított gráfot használva a Topológiai rendezés úgy rendezi a csomópontokat, hogy mindegyik az előtt jelenjen meg, amelyre mutat.

Ezt az algoritmust egy DAG-on (Directed Acyclic Graph) alkalmazzák, így minden csomópont megjelenik a rendezett tömbben, mielőtt az összes többi csomópont rámutatna. Ez az algoritmus ismételten követ bizonyos szabályokat, amíg a rendezés be nem fejeződik.

Az egyszerűsítés érdekében nézze meg a következő példát:

Itt láthatjuk, hogy „A”-nak nincs indefokja. Azt az élt jelenti, amely egy csomópontra mutat. „B” és „C” előfeltétele „A”, majd „E” előfeltétele „D” és „F” csomópont. Egyes csomópontok más csomópontoktól függenek.

Íme a fenti grafikon egy másik ábrázolása:

Tehát amikor a DAG-ot (Directed Acyclic Graph) átadjuk a topológiai rendezésnek, akkor egy lineáris sorrendű tömböt adunk, ahol az első elemnek nincs függősége.

Ez a példa egy grafikont mutat be egy ciklussal:

Íme a lépések ehhez:

Step 1) Keresse meg a nulla bejövő élekkel rendelkező csomópontot, egy nulla fokos csomópontot.

Step 2) Tárolja a nullázó fokon belüli csomópontot egy sorban vagy veremben, és eltávolítja a csomópontot a grafikonról.

Step 3) Ezután törölje a kimenő élt a csomópontból.

Ez csökkenti a következő csomópont fokon belüli számát.

A topológiai sorrend megköveteli, hogy a gráf adatszerkezetében ne legyen ciklus.

Egy grafikon DAG-nak minősül, ha megfelel a következő követelményeknek:

• Egy vagy több csomópont nulla infok értékkel.
• A grafikon nem tartalmaz ciklust

Mindaddig, amíg vannak csomópontok a grafikonon, és a gráf továbbra is DAG, addig a fenti három lépést fogjuk végrehajtani. Ellenkező esetben az algoritmus ciklikus függőségbe esik, és a Kahn-algoritmus nem tud olyan csomópontot találni, amelynek nulla foka.

Hogyan működik a topológiai rendezés

Itt a „Kahn-algoritmust” fogjuk használni a topológiai rendezéshez. Tegyük fel, hogy a következő grafikonunk van:

Íme a Kahn-algoritmus lépései:

Step 1) Számítsa ki a Graph összes csomópontjának indokát vagy bejövő élét.

Jegyzet:

• Az indegre a csomópontra mutató irányított éleket jelenti.
• A külső fok az irányított éleket jelenti, amelyek egy csomópontból származnak.

Íme a fenti grafikon indegrade és outdegrade:

Step 2) Keresse meg a nulla fokos vagy nulla bejövő élekkel rendelkező csomópontot.

A nulla fokozatú csomópont azt jelenti, hogy nem jönnek élek a csomópont felé. Az „A” csomópont nulla fokos, ami azt jelenti, hogy nincs él, amely az „A” csomópontra mutat.

Tehát a következő műveleteket hajtjuk végre:

• Távolítsa el ezt a csomópontot és a külső széleit (kimenő éleket)
• Helyezze a csomópontot a rendelési sorba.
• Frissítse az „A” szomszédos csomópont fokon belüli számát.

Step 3) Olyan csomópontot kell találnunk, amelynek indegree értéke nulla. Ebben a példában „B” és „C” nulla fokos.

Itt a kettő közül bármelyiket vehetjük. Vegyük a „B”-t és töröljük a grafikonból.

Ezután frissítse a többi csomópont indegres értékét.

A műveletek végrehajtása után a grafikonunk és a sor a következőképpen fog kinézni:

Step 4) A „C” csomópontnak nincs bejövő éle. Tehát eltávolítjuk a „C” csomópontot a grafikonról, és benyomjuk a sorba.

A „C”-ből kimenő élt is törölhetjük.

A grafikonunk most így fog kinézni:

Step 5) Láthatjuk, hogy a „D” és „F” csomópontok zérus fokozatúak. Fogunk egy csomópontot, és betesszük a sorba.

Először vegyük ki a „D” betűt. Ekkor az „E” csomópont infokszáma 1 lesz. Most nem lesz D-től E-ig csomópont.

Ugyanezt kell tennünk az „F” csomópontnál is, az eredmény a következő lesz:

Step 6) Az „E” csomópont bemeneti foka (bemenő élek) és kilépő élei nulla lett. Tehát teljesítettük az „E” csomópont összes előfeltételét.

Itt „E” betűt teszünk a sor végére. Tehát nem maradt csomópontunk, így az algoritmus itt véget ér.

Pszeudo kód a topológiai rendezéshez

Íme a topológiai rendezés pszeudokódja a Kahn-algoritmus használata közben.

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

A topológiai rendezés is megvalósítható a DFS (Mélység első keresés) módszerrel. Ez a megközelítés azonban a rekurzív módszer. Kahn algoritmusa hatékonyabb, mint a DFS megközelítés.

C++ Topológiai rendezés megvalósítása

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

teljesítmény

0       1       2       3       5       4

Python Topológiai rendezés megvalósítása

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

teljesítmény

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

Topológiai rendezési algoritmus ciklikus grafikonjai

Egy ciklust tartalmazó gráf nem rendezhető topológiailag. Mivel a ciklikus gráfnak ciklikus módon van a függősége.

Például ellenőrizze ezt a grafikont:

Ez a grafikon nem DAG (Directed Acyclic Graph), mert A, B és C ciklust hoz létre. Ha észreveszi, nincs nulla fokos értékkel rendelkező csomópont.

Kahn algoritmusa szerint, ha elemezzük a fenti grafikont:

• Keressen egy nulla fokos csomópontot (nincs bejövő él).
• Távolítsa el a csomópontot a grafikonról, és tolja be a sorba.
  A fenti grafikonon azonban nincs nulla fokos csomópont. Minden csomópont 0-nál nagyobb fokos értékkel rendelkezik.
• Üres sor visszaadása, mivel nem talált nulla fokos csomópontot.

A ciklusokat topológiai sorrendben tudjuk észlelni, a következő lépésekkel:

Step 1) Végezze el a topológiai rendezést.

Step 2) Számítsa ki a topológiailag rendezett lista elemeinek teljes számát.

Step 3) Ha az elemek száma megegyezik a csúcsok teljes számával, akkor nincs ciklus.

Step 4) Ha nem egyenlő a csúcsok számával, akkor legalább egy ciklus van az adott gráf adatstruktúrában.

Topológiai rendezés komplexitáselemzése

Az algoritmusokban kétféle összetettség létezik. Ők

1. Idő komplexitás
2. Tér komplexitás

Ezeket a komplexitásokat egy általános komplexitást biztosító függvény ábrázolja.

Idő összetettsége: A topológiai rendezés minden időbeli összetettsége azonos. Léteznek a legrosszabb, az átlagos és a legjobb forgatókönyvek az idő bonyolultságára vonatkozóan.

A topológiai rendezés időbonyolultsága O(E + V), itt E a gráf éleinek számát, V pedig a gráf csúcsainak számát jelenti.

Törjük át ezt a bonyolultságot:

Step 1) Kezdetben kiszámoljuk az összes fokot. Ehhez át kell mennünk az összes élen, és kezdetben az összes V csúcsindefot nullához rendeljük. Tehát az általunk végrehajtott fokozatos lépések a következők lesznek O(V+E).

Step 2) Megtaláljuk a nulla indegree értékű csomópontot. A csúcs V számából kell keresnünk. Tehát a lépések befejeződnek O(V).

Step 3) Minden nulla fokos csomópontnál eltávolítjuk azt a csomópontot, és csökkentjük az infokát. Ennek a műveletnek az összes csomóponton történő végrehajtása szükséges O(E).

Step 4) Végül ellenőrizzük, hogy van-e ciklus vagy nincs. Ellenőrizzük, hogy a rendezett tömb elemeinek teljes száma megegyezik-e a csomópontok teljes számával. El fog tartani O (1).

Tehát ezek voltak a topológiai rendezés vagy topológiai rendezés egyes lépéseinek egyéni időbonyolítása. Azt mondhatjuk, hogy az időbonyolultság a fenti számításból O( V + E ); itt az O a komplexitásfüggvényt jelenti.

Tér összetettsége: A topológiai rendezési algoritmus futtatásához O(V) terekre volt szükségünk.

Itt vannak azok a lépések, ahol szükségünk volt a programhelyre:

• Ki kellett számítanunk a grafikonon lévő csomópontok összes fokát. Mivel a grafikon összesen V csomópontot tartalmaz, létre kell hoznunk egy V méretű tömböt. Tehát a szükséges hely O(V).
• Egy Queue adatszerkezetet használtunk a csomópont nulla fokozatú tárolására. Eltávolítottuk a nulla fokos csomópontokat az eredeti grafikonból, és a sorba helyeztük őket. Ehhez a szükséges hely volt O(V).
• A tömb neve „order”. Ez a csomópontokat topológiai sorrendben tárolta. Ez is kellett O(V) szóközök.

Ezek voltak az egyéni térkomplexitás. Tehát maximalizálnunk kell ezeket a tereket a futásidőben.

A térbonyolultság az O(V) rövidítése, ahol V a gráf csúcsának számát jelenti.

Topológiai rendezés alkalmazása

Óriási haszna van a topológiai rendezésnek. Itt van néhány közülük:

• Akkor használják, amikor Operadolog rendszer el kell végeznie az erőforrás-allokációt.
• Ciklus keresése a grafikonon. Topológiai rendezéssel ellenőrizhetjük, hogy a gráf DAG-e vagy sem.
• Mondatsorrend az automatikus kiegészítõ alkalmazásokban.
• Felismerésre használják holtpontok.
• Különböző típusú ütemezés vagy pályaütemezés a topológiai rendezést használja.
• Függőségek feloldása. Például, ha megpróbál telepíteni egy csomagot, annak más csomagokra is szüksége lehet. A topológiai rendezés megtalálja az összes szükséges csomagot az aktuális csomag telepítéséhez.
• Linux a topológiai rendezést használja az „apt”-ban a csomagok függőségének ellenőrzésére.