Topológiai rendezési algoritmus: Python, C++ 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 (irányított aciklikus gráf) alkalmazzák, így minden csomópont a rendezett tömbben az összes többi általa mutatott csomópont előtt jelenik meg. Az algoritmus bizonyos szabályokat ismételten követ, 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:

Irányított grafikon

Itt láthatjuk, hogy „A”-nak nincs független fokszáma. A független fok azt az élet jelenti, amely egy csomópontra mutat. „B” és „C” előfeltétele az „A”, majd „E” előfeltétele a „D” és „F” csomópontok. Néhány csomópont más csomópontoktól függ.

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

Az egyes csomópontok függősége (lineáris rendezés)

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.

Í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árold el a nulla fokszámú csomópontot egy várakozási sorban vagy veremben, majd távolítsd el a csomópontot a gráfból.

Step 3) Ezután törölje a kimenő élet az adott csomópontból. Ez csökkenti a következő csomópont bejövő fokszámát.

A topológiai sorrend megköveteli, hogy a gráf adatszerkezete ne tartalmazzon ciklust. Egy gráfot DAG-nak tekintünk, ha megfelel a következő követelményeknek:

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

Amíg vannak csomópontok a gráfban, és a gráf továbbra is DAG, addig lefuttatjuk a fenti három lépést. Ellenkező esetben az algoritmus ciklikus függőségbe esik, és Kahn algoritmusa nem lesz képes nulla befokú csomópontot találni.

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ő gráfunk 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.

Itt látható a fenti grafikon belső és külső fokszáma:

Step 2) Keresd meg a nulla bejövő fokos vagy nulla bejövő éllel rendelkező csomópontot. A nulla bejövő fokos csomópont azt jelenti, hogy nem érkeznek élek a csomópont felé. Az „A” csomópont nulla bejövő fokos, ami azt jelenti, hogy nincs olyan él, amely az „A” csomópontra mutatna. Tehát a következő műveleteket fogjuk végrehajtani:

• Távolítsd el ezt a csomópontot és a kifelé haladó éleit (kimenő éleit).
• Helyezze a csomópontot a rendelési sorba.
• Frissítse az „A” szomszédos csomópontjának fokszám szerinti számát.

Step 3) Olyan csomópontot kell találnunk, amelynek a bejövő fok értéke nulla. Ebben a példában a „B” és a „C” bejövő foka nulla. Itt bármelyiket választhatjuk. Vegyük „B”-t, és töröljük a gráfból. Ezután frissítsük a többi csomópont bejövő fokának értékeit. Ezen műveletek végrehajtása után a gráfunk és a sorunk 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 gráfból, és beillesztjük a sorba. Törölhetjük a „C” csomópontból kimenő élet is. A gráfunk most így fog kinézni:

Step 5) Láthatjuk, hogy a „D” és „F” csomópontok fokszáma nulla. Fogunk egy csomópontot, és betesszük a sorba. Először vegyük ki a „D” csomópontot. Ekkor az „E” csomópont fokszáma 1 lesz. Most nem lesz D és E között csomópont. Ugyanezt kell tennünk az „F” csomóponttal is, és az eredmény a következő lesz:

Step 6) Az „E” csomópont belső foka (bejövő élek) és külső foka (kimenő élek) nullává vált. Tehát teljesítettük az „E” csomópont összes előfeltételét. Itt az „E” csomópontot a sor végére tesszük. Tehát nem maradtak csomópontok, és az algoritmus itt véget ér.

Pszeudo Code topológiai rendezésre

Itt a topológiai rendezés pszeudokódja Kahn algoritmusának használatával.

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

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áf ciklikus módon rendelkezik a függőséggel. Nézzük meg például ezt a gráfot:

Ez a gráf nem irányított aciklikus gráf (DAG), mivel A, B és C egy ciklust alkotnak. Ha megfigyeled, nincs olyan csomópont, amelynek a fokszáma nulla lenne. Kahn algoritmusa szerint, ha elemezzük a fenti gráfot:

• Keressen egy nulla fokos csomópontot (nincs bejövő él).
• Távolítsd el ezt a csomópontot a gráfból, és helyezd át a várólistába. A fenti gráfban azonban nincs olyan csomópont, amelynek a bejövő foka nulla. Minden csomópont bejövő fok értéke nagyobb, mint 0.
• Üres várólistát ad vissza, mivel nem talált nulla in-fok értékű 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 bonyolultság létezik. Ezek a következő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ésnél minden időbonyolultság azonos. Az időbonyolultságnak létezik legrosszabb, átlagos és legjobb esete. A topológiai rendezés időbonyolultsága O(E + V), ahol E a gráf éleinek számát, V pedig a gráf csúcsainak számát jelenti.

Törjük át magunkat ezen a bonyolultságon:

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 minden egyes lépésének egyedi időbonyolultságai. Azt mondhatjuk, hogy a fenti számításból származó időbonyolultság O(V + E) lesz; itt O a komplexitásfüggvényt jelenti.

Tér összetettsége: A topológiai rendezési algoritmus futtatásához O(V) szóközre volt szükségünk. Íme a lépések, amelyek során szükségünk volt a programhoz szükséges helyre:

• 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” (order), amely a csomópontokat topológiai sorrendben tárolja. Ehhez az is szükséges volt, hogy O(V) szóközök.

Ezek voltak az egyes térbonyolultságok. Tehát futásidőben maximalizálnunk kell ezeket a tereket. A térbonyolultság O(V)-vel jelölve van, ahol V a gráfban lévő csúcs számát jelenti.

Topológiai rendezés alkalmazása

A topológiai rendezésnek hatalmas felhasználási területei vannak. Íme néhány ezek közül:

• Akkor használják, amikor egy Operadolog rendszer el kell végeznie az erőforrás-allokációt.
• Ciklus keresése a gráfban. Topológiai rendezéssel ellenőrizhetjük, hogy a gráf DAG-e vagy sem.
• Mondatsorrend az automatikus kiegészítõ alkalmazásokban.
• Az észlelésre használják holtpontok.
• A különböző ütemezési vagy kurzusütemezési típusok a topológiai rendezést használják.
• 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.

GYIK