Topolojik Sıralama Algoritması: Python, C++ Örnek E-posta

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, her düğümün, işaret ettiği diğer tüm düğümlerden önce sıralı dizide yer almasını sağlayacak şekilde yönlendirilmiş döngüsel olmayan bir grafik (DAG) üzerinde uygulanır. Bu algoritma, sıralama tamamlanana kadar bazı kuralları tekrar tekrar izler.

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

Yönlendirilmiş grafik

Burada, "A" düğümünün içe doğru bağlantı noktası olmadığını görüyoruz. İçe doğru bağlantı noktası, bir düğüme işaret eden kenar anlamına gelir. "B" ve "C" düğümlerinin "A" düğümüne ön koşulu vardır, dolayısıyla "E" düğümünün de "D" ve "F" düğümlerine ön koşulu vardır. Bazı düğümler diğer düğümlere bağımlıdır.

Yukarıdaki grafiğin bir başka gösterimi şöyledir:

Her düğümün bağımlılığı (Doğrusal Sıralama)

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.

Bunu yapmak için 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 Sıfır giriş derecesine sahip düğümü bir Kuyruk veya Yığına kaydedin ve düğümü Grafikten kaldırın.

) 3 Adım Ardından o düğümden çıkan kenarı silin. Bu, bir sonraki düğüm için gelen bağlantı sayısını azaltacaktır.

Topolojik sıralama, grafik veri yapısının herhangi bir döngü içermemesini gerektirir. Bir grafik, aşağıdaki şartları karşılıyorsa yönlendirilmiş döngüsüz grafik (DAG) olarak kabul edilir:

• Derece değeri sıfır olan bir veya daha fazla düğüm.
• Grafikte herhangi bir döngü bulunmamaktadır.

Grafta düğümler olduğu ve graf hala bir yönlendirilmiş döngüsüz grafik (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 algoritması sıfır giriş derecesine sahip bir düğüm bulamayacaktır.

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

Burada, topolojik sıralama için “Kahn Algoritması”nı kullanacağız. Diyelim ki aşağıdaki grafımız var:

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 gelen ve giden bağlantı sayıları aşağıdadır:

) 2 Adım Sıfır gelen bağlantıya veya sıfır gelen kenara sahip düğümü bulun. Sıfır gelen bağlantıya sahip düğüm, o düğüme doğru gelen hiçbir kenar olmadığı anlamına gelir. "A" düğümünün sıfır gelen bağlantısı vardır, yani "A" düğümüne işaret eden hiçbir kenar yoktur. Bu nedenle, aşağıdaki işlemleri yapacağız:

• Bu düğümü ve ona bağlı dış bağlantıları (çıkış bağlantıları) kaldırın.
• Düğümü sipariş için Kuyruğa yerleştirin.
• “A” düğümünün komşu düğümünün gelen bağlantı sayısını güncelleyin.

) 3 Adım Sıfır giriş derecesine sahip bir düğüm bulmamız gerekiyor. Bu örnekte, "B" ve "C" düğümlerinin giriş dereceleri sıfırdır. Burada, bu ikisinden birini seçebiliriz. "B" düğümünü seçip grafikten silelim. Ardından diğer düğümlerin giriş derecesi değerlerini güncelleyelim. Bu işlemleri gerçekleştirdikten sonra, grafiğimiz ve kuyruğumuz aşağıdaki gibi görünecektir:

) 4 Adım “C” düğümünün gelen kenarı yok. Bu nedenle, “C” düğümünü Grafikten kaldırıp Kuyruğa ekleyeceğiz. Ayrıca “C”den çıkan kenarı da silebiliriz. Şimdi, Grafiğimiz şöyle görünecek:

) 5 Adım D ve F düğümlerinin giriş derecesinin sıfır olduğunu görüyoruz. Bir düğüm alıp kuyruğa koyacağız. Önce D düğümünü alalım. O zaman E düğümünün giriş derecesi 1 olacaktır. Şimdi D'den E'ye hiçbir düğüm kalmayacak. Aynı işlemi F düğümü için de yapmamız gerekiyor ve sonuç aşağıdaki gibi olacak:

) 6 Adım “E” düğümünün gelen (giriş) ve giden (çıkış) dereceleri sıfır oldu. Dolayısıyla, “E” düğümü için tüm ön koşulları yerine getirdik. Burada, “E” düğümünü kuyruğun sonuna koyacağız. Bu nedenle, geriye hiçbir düğüm kalmadı ve algoritma burada sona eriyor.

Sözde Code Topolojik Sıralama için

İşte Kahn algoritmasını kullanarak topolojik sıralama için sözde kod.

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

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, döngüsel bir şekilde bağımlılığa sahip olduğu için topolojik olarak sıralanamaz. Örneğin, şu grafiğe bakın:

Bu grafik, A, B ve C'nin bir döngü oluşturması nedeniyle yönlendirilmiş döngüsüz bir grafik (DAG) değildir. Dikkat ederseniz, sıfır giriş derecesine sahip hiçbir düğüm yoktur. Kahn algoritmasına göre, yukarıdaki grafiği analiz edersek:

• Sıfır dereceli (gelen kenarları olmayan) bir düğüm bulun.
• O düğümü grafikten kaldırın ve kuyruğa ekleyin. Ancak yukarıdaki grafikte sıfır giriş derecesine sahip hiçbir düğüm yoktur. Her düğümün 0'dan büyük bir giriş derecesi değeri vardır.
• Sıfır giriş derecesine sahip herhangi bir düğüm bulamadığı için boş bir kuyruk 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 Eğer bu değer 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 şunlardır:

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ıralamanın 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ığı birlikte 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 düzenlemenin her adımı için ayrı ayrı zaman karmaşıklıkları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) alanı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ı "order" olup, düğümleri topolojik sıraya göre saklıyordu. Bu da şunu gerektiriyordu: Ç(V) alanlarda.

Bunlar bireysel alan karmaşıklıklarıydı. Dolayısıyla, çalışma zamanında bu alanları en üst düzeye çıkarmamız gerekiyor. Alan karmaşıklığı O(V)'dir; burada V, Grafikteki köşe sayısını ifade eder.

Topolojik Sıralamanın Uygulanması

Topolojik sıralamanın çok geniş bir kullanım alanı vardır. İşte bunlardan bazıları:

• Bir şey olduğunda kullanılır Operating sistemi kaynak tahsisini gerçekleştirmesi gerekmektedir.
• Grafikte bir döngü bulma. Topolojik sıralama ile grafiğin yönlendirilmiş döngüsüz grafik (DAG) olup olmadığını doğrulayabiliriz.
• Otomatik tamamlama uygulamalarında cümle sıralaması.
• Tespit etmek için kullanılır. kilitlenmeler.
• Farklı planlama türleri veya ders planlamaları 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.

SSS