Topolojik Sıralama: Python, C++ Algoritma Örneği

Topolojik Sıralama Algoritması Nedir?

Topolojik Sıralama aynı zamanda Kahn algoritması olarak da bilinir ve popüler bir Sıralama Algoritmasıdır. Yönlendirilmiş bir grafiği girdi olarak kullanan Topolojik Sıralama, düğümleri, her biri işaret ettiği düğümden önce görünecek şekilde sıralar.

Bu algoritma bir DAG (Yönlendirilmiş Asiklik Grafik) üzerine uygulanır, böylece her düğüm, diğer tüm düğümler ona işaret edilmeden önce sıralı dizide görünür. Bu algoritma, sıralama tamamlanana kadar bazı kuralları tekrar tekrar takip eder.

Basitleştirmek için aşağıdaki örneğe bakalım:

Burada “A”nın derecesinin olmadığını görüyoruz. Bir düğüme işaret eden kenar anlamına gelir. “B” ve “C”, “A” ön koşuluna sahiptir, ardından “E”, “D” ve “F” düğümlerinin ön koşuluna sahiptir. Bazı düğümler diğer düğümlere bağımlıdır.

Yukarıdaki Grafiğin başka bir temsili:

Yani DAG'ı (Yönlendirilmiş Asiklik Grafik) topolojik sıralamaya geçirdiğimizde, bize ilk elemanın hiçbir bağımlılığının olmadığı, doğrusal sıralamaya sahip bir dizi verecektir.

Bu örnekte döngü içeren bir grafik gösterilmektedir:

Bunu yapmanın adımları şunlardır:

) 1 Adım Gelen kenarları sıfır olan düğümü, sıfır dereceli bir düğümü bulun.

) 2 Adım Dereceli düğümü bir Kuyrukta veya Yığında sıfırlayanı saklayın ve düğümü Grafikten kaldırın.

) 3 Adım Daha sonra o düğümden giden kenarı silin.

Bu, bir sonraki düğümün derece sayısını azaltacaktır.

Topolojik sıralama, grafik veri yapısının herhangi bir döngüye sahip olmamasını gerektirir.

Bir grafik şu gereksinimleri karşılıyorsa DAG olarak kabul edilecektir:

• Derece değeri sıfır olan bir veya daha fazla düğüm.
• Grafik herhangi bir döngü içermiyor

Grafikte düğümler olduğu ve Grafik hala DAG olduğu sürece, yukarıdaki üç adımı uygulayacağız. Aksi takdirde, algoritma döngüsel bağımlılığa düşecek ve Kahn'ın Algoritması sıfır dereceli bir düğüm bulamayacaktır.

Topolojik Sıralama Nasıl Çalışır?

Burada topolojik sıralama için "Kahn'ın Algoritmasını" kullanacağız. Diyelim ki aşağıdaki Graph'a sahibiz:

Kahn Algoritmasının adımları şunlardır:

) 1 Adım Grafikteki tüm düğümlerin derecesini veya gelen kenarını hesaplayın.

Not:

• Derece, düğüme işaret eden yönlendirilmiş kenarlar anlamına gelir.
• Outdegree, bir düğümden gelen yönlendirilmiş kenarlar anlamına gelir.

Yukarıdaki Grafiğin derece ve dış derecesi:

) 2 Adım Sıfır dereceli veya sıfır gelen kenarlı düğümü bulun.

Derecesi sıfır olan düğüm, o düğüme doğru hiçbir kenar gelmediği anlamına gelir. “A” düğümünün derecesi sıfırdır, yani “A” düğümünü gösteren bir kenar yoktur.

O halde şu işlemleri yapacağız:

• Bu düğümü ve onun dış derece kenarlarını (giden kenarlar) kaldırın
• Düğümü sipariş için Kuyruğa yerleştirin.
• “A”nın komşu düğümünün derece cinsinden sayısını güncelleyin.

) 3 Adım Derece değeri sıfır olan bir düğüm bulmamız gerekiyor. Bu örnekte “B” ve “C”nin derecesi sıfırdır.

Burada bu ikisinden birini alabiliriz. “B”yi alıp Grafikten silelim.

Daha sonra diğer düğümlerin derece değerlerini güncelleyin.

Bu işlemleri yaptıktan sonra Grafiğimiz ve Kuyruğumuz aşağıdaki gibi görünecektir:

) 4 Adım “C” düğümünün gelen kenarı yoktur. Böylece “C” düğümünü Grafikten kaldıracağız ve Kuyruğa iteceğiz.

Ayrıca “C”den çıkan kenarı da silebiliriz.

Artık Grafiğimiz şöyle görünecek:

) 5 Adım “D” ve “F” düğümlerinin derecesinin sıfır olduğunu görebiliriz. Bir düğüm alıp Kuyruğa koyacağız.

Önce “D”yi çıkaralım. O zaman “E” düğümünün derece sayısı 1 olacaktır. Artık D'den E'ye hiçbir düğüm olmayacaktır.

Aynı işlemi “F” nodu için de yapmamız gerekiyor, sonucumuz aşağıdaki gibi olacaktır:

) 6 Adım “E” düğümünün indegree (giden kenarlar) ve outdegree (giden kenarlar) sıfır oldu. Böylece “E” düğümü için tüm önkoşulları karşıladık.

Burada sıranın sonuna “E” koyuyoruz. Yani elimizde hiç düğüm kalmadı, dolayısıyla algoritma burada bitiyor.

Topolojik Sıralama için Sahte Kod

Kahn Algoritmasını kullanırken topolojik sıralamanın sözde kodunu burada bulabilirsiniz.

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

Topolojik sıralama DFS (Derinlik öncelikli arama) yöntem. Ancak bu yaklaşım özyinelemeli yöntemdir. Kahn'ın algoritması DFS yaklaşımından daha verimlidir.

C++ Topolojik Sıralamanın Uygulanması

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

Çıktı

0       1       2       3       5       4

Python Topolojik Sıralamanın Uygulanması

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

Çıktı

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

Topolojik Sıralama Algoritmasının Döngüsel Grafikleri

Döngü içeren bir grafik topolojik olarak sıralanamaz. Döngüsel Grafik, döngüsel bir şekilde bağımlılığa sahip olduğundan.

Örneğin, şu Grafiği kontrol edin:

Bu Grafik DAG (Yönlendirilmiş Döngüsel Olmayan Grafik) değildir çünkü A, B ve C bir döngü oluşturur. Dikkat ederseniz derece değeri sıfır olan bir düğüm yok.

Yukarıdaki Grafiği Kahn Algoritmasına göre analiz edersek:

• Sıfır dereceli (gelen kenarları olmayan) bir düğüm bulun.
• Bu düğümü Grafikten kaldırın ve Kuyruğa itin.
  Ancak yukarıdaki Grafikte derecesi sıfır olan bir düğüm bulunmamaktadır. Her düğümün 0'dan büyük bir derece değeri vardır.
• Derece olarak sıfır olan herhangi bir düğüm bulamadığı için boş bir sıra döndürün.

Topolojik sıralamayı kullanarak döngüleri aşağıdaki adımlarla tespit edebiliriz:

) 1 Adım Topolojik Sıralama gerçekleştirin.

) 2 Adım Topolojik olarak sıralanmış listedeki toplam öğe sayısını hesaplayın.

) 3 Adım Eleman sayısı toplam köşe sayısına eşitse döngü yoktur.

) 4 Adım Köşe sayısına eşit değilse, verilen grafik veri yapısında en az bir döngü vardır.

Topolojik Sıralamanın Karmaşıklık Analizi

Algoritmalarda iki tür karmaşıklık vardır. Bunlar

1. Zaman Karmaşıklığı
2. Uzay Karmaşıklığı

Bu karmaşıklıklar genel bir karmaşıklık sağlayan bir fonksiyonla temsil edilir.

Zaman Karmaşıklığı: Topolojik Sıralama için tüm zaman karmaşıklığı aynıdır. Zaman karmaşıklığı için en kötü, ortalama ve en iyi durum senaryoları vardır.

Topolojik Sıralama için zaman karmaşıklığı O(E + V)'dir, burada E, Grafikteki Kenar sayısını, V ise Grafikteki köşe sayısını ifade eder.

Bu karmaşıklığı aşalım:

) 1 Adım Başlangıçta tüm dereceleri hesaplayacağız. Bunu yapmak için tüm kenarlardan geçmemiz gerekiyor ve başlangıçta tüm V köşe derecelerini sıfıra atayacağız. Yani tamamladığımız artan adımlar Ç(V+E).

) 2 Adım Sıfır derece değerine sahip düğümü bulacağız. Köşenin V numarasından arama yapmamız gerekiyor. Yani, tamamlanan adımlar Ç(V).

) 3 Adım Derecesi sıfır olan her düğüm için o düğümü kaldıracağız ve dereceyi azaltacağız. Bu işlemin tüm düğümler için gerçekleştirilmesi, Ç(E).

) 4 Adım Son olarak herhangi bir döngü olup olmadığını kontrol edeceğiz. Sıralanan dizideki toplam eleman sayısının toplam düğüm sayısına eşit olup olmadığını kontrol edeceğiz. Sürer O (1).

Yani, bunlar topolojik Sıralama veya topolojik sıralamanın her adımı için bireysel zaman karmaşıklığıydı. Yukarıdaki hesaplamadan zaman karmaşıklığının O(V + E) olacağını söyleyebiliriz; burada, O karmaşıklık fonksiyonunu ifade eder.

Uzay Karmaşıklığı: Topolojik sıralama algoritmasını çalıştırmak için O(V) uzaylarına ihtiyacımız vardı.

Program için alana ihtiyaç duyduğumuz adımlar şunlardır:

• Grafikte bulunan düğümlerin tüm derecelerini hesaplamamız gerekiyordu. Grafiğin toplam V düğümü olduğundan, V boyutunda bir dizi oluşturmamız gerekir. Yani gerekli alan şuydu: Ç(V).
• Düğümü sıfır derece ile depolamak için Kuyruk veri yapısı kullanıldı. Derecesi sıfır olan düğümleri orijinal Grafiğinden çıkarıp Kuyruğa yerleştirdik. Bunun için gerekli alan Ç(V).
• Dizinin adı "düzen"dir. Bu, düğümleri topolojik sırayla depoladı. Bu da gerekliydi Ç(V) alanlarda.

Bunlar bireysel alan karmaşıklığıydı. Bu yüzden, çalışma zamanında bu alanları en üst düzeye çıkarmamız gerekiyor.

Uzay karmaşıklığı O(V)'yi ifade eder; burada V, Grafikteki tepe noktasının numarasını ifade eder.

Topolojik Sıralamanın Uygulanması

Topolojik Sıralamanın çok büyük bir kullanımı var. Bunlardan bazıları:

• Ne zaman kullanılır Operating sistemi kaynak tahsisini gerçekleştirmesi gerekmektedir.
• Grafikte bir döngü bulma. Grafiğin DAG olup olmadığını topolojik sıralama ile doğrulayabiliriz.
• Otomatik tamamlama uygulamalarında cümle sıralaması.
• Tespit etmek için kullanılır kilitlenmeler.
• Farklı türde Planlama veya ders planlama, topolojik sıralamayı kullanır.
• Bağımlılıkları çözme. Örneğin bir paket kurmaya çalışırsanız o paketin başka paketlere de ihtiyacı olabilir. Topolojik sıralama, mevcut paketi kurmak için gerekli tüm paketleri bulur.
• Linux paketlerin bağımlılığını kontrol etmek için “apt” içindeki topolojik sıralamayı kullanır.