AlgoPit

Topolojik Sıralama (Topological Sort) Algoritması

Topolojik sıralama, yönlü asiklik graflarda (DAG) düğümleri bağımlılıklarına göre sıralayan bir algoritmadır. Her düğüm, kendisine bağımlı olan düğümlerden önce gelecek şekilde bir doğrusal sıralama oluşturur. Bu algoritma, görev planlaması, derleme sırası, kurs ön koşulları gibi bağımlılık yönetimi gerektiren birçok alanda kullanılır.

Avantajlar

  • Doğrusal zaman karmaşıklığı (O(V + E) - Düğüm ve kenar sayısıyla orantılı)
  • Bağımlılık ilişkilerini doğru şekilde yönetir
  • Çevrimleri (döngüleri) tespit edebilir
  • Derleme sırası, görev planlaması gibi birçok gerçek dünya problemine uygulanabilir
  • DFS algoritmasının doğal bir uzantısıdır

Dezavantajlar

  • Yalnızca yönlü asiklik graflar (DAG) için kullanılabilir
  • Çevrimli graflar için kullanılamaz
  • Birden fazla geçerli topolojik sıralama olabilir (tek bir doğru çözüm yoktur)
  • Yüksek öncelikli görevleri belirleme konusunda yetersiz kalabilir

İnteraktif Demo

Topolojik sıralama algoritmasını test edin. Grafı aşağıdaki formatta girin (her satır bir düğümü ve komşularını temsil eder):

Format: Düğüm:Komşu1,Komşu2,Komşu3

Örnek gösterim:

  • A:B,C - A düğümünden B ve C düğümlerine kenarlar var
  • B:D - B düğümünden D düğümüne kenar var
  • C: - C düğümünden çıkan kenar yok

Graf Yapısı

A
→ C, D
B
→ D
C
→ E
D
→ E
E
→ (yok)

Topolojik Sıralama Sonucu

B
→
A
→
D
→
C
→
E

Bu sıralama, her düğümün kendi tüm bağımlılıklarından sonra geldiği bir düzeni gösterir. Bir DAG için birden fazla geçerli topolojik sıralama olabilir.

Kod Örnekleri

Topolojik sıralama algoritmasının farklı programlama dillerindeki implementasyonları.

Topolojik Sıralama - TypeScript
1function topologicalSort(graph: Record): { result: string[], hasCycle: boolean } {
2  // Düğümlerin ziyaret durumunu izlemek için
3  const visited: Record = {};
4  const tempVisited: Record = {}; // Geçici ziyaret (çevrim tespiti için)
5  const result: string[] = [];
6  let hasCycle = false;
7  
8  // DFS yardımcı fonksiyonu
9  function dfs(node: string) {
10    // Çevrim kontrolü - eğer düğüm geçici olarak ziyaret edildiyse, çevrim var demektir
11    if (tempVisited[node]) {
12      hasCycle = true;
13      return;
14    }
15    
16    // Eğer düğüm zaten ziyaret edildiyse, tekrar ziyaret etmeye gerek yok
17    if (visited[node]) {
18      return;
19    }
20    
21    // Düğümü geçici olarak ziyaret edildi olarak işaretle
22    tempVisited[node] = true;
23    
24    // Komşu düğümleri kontrol et
25    const neighbors = graph[node] || [];
26    for (const neighbor of neighbors) {
27      dfs(neighbor);
28    }
29    
30    // Düğüm işlendi, artık kalıcı olarak ziyaret edildi
31    visited[node] = true;
32    // Geçici ziyaret işaretini kaldır
33    tempVisited[node] = false;
34    
35    // Sonuç listesine ekle (başa ekleyerek sıralama tersine çevrilir)
36    result.unshift(node);
37  }
38  
39  // Tüm düğümler için DFS
40  for (const node of Object.keys(graph)) {
41    if (!visited[node]) {
42      dfs(node);
43    }
44  }
45  
46  return { result, hasCycle };
47}

Algoritma Nasıl Çalışır?

Topolojik sıralama, yönlü asiklik graflarda (DAG) düğümleri sıralama yöntemidir. Eğer grafdaki iki düğüm arasında u'dan v'ye bir kenar varsa, u düğümü topolojik sıralamada v'den önce gelmelidir. Algoritmanın temeli, her düğümün kendisine bağımlı olan tüm düğümlerden önce işlenmesini sağlamaktır.

Algoritmanın Adımları

Topolojik sıralama için yaygın olarak iki yaklaşım kullanılır:

1. DFS (Derinlik Öncelikli Arama) Tabanlı Yaklaşım

  1. Her düğüm için, henüz ziyaret edilmediyse DFS başlat
  2. Mevcut düğümün tüm komşularını ziyaret et
  3. Tüm komşuları ziyaret edildikten sonra, düğümü sonuç listesinin başına ekle
  4. DFS tamamlandığında, sonuç listesi doğru topolojik sıralamayı içerir

2. Kahn Algoritması (Girdi Derecesi Tabanlı)

  1. Her düğümün girdi derecesini (gelen kenar sayısı) hesapla
  2. Girdi derecesi 0 olan düğümleri bir kuyruğa ekle
  3. Kuyruktan bir düğüm çıkar, sonuç listesine ekle
  4. Çıkarılan düğümün tüm komşularının girdi derecesini 1 azalt
  5. Girdi derecesi 0'a düşen düğümleri kuyruğa ekle
  6. Kuyruk boşalana kadar devam et

Çevrim Tespiti

Topolojik sıralama yalnızca çevrimsiz graflar (DAG) için mümkündür. Algoritma çevrim tespiti de yapabilir:

  • DFS yaklaşımında, geçici ziyaret işaretleri kullanarak çevrimleri tespit edebiliriz. Eğer bir düğüm halen geçici ziyaret edildi olarak işaretliyken tekrar ziyaret edilirse, bu bir çevrim olduğunu gösterir.
  • Kahn algoritmasında, eğer sonuç listesinin uzunluğu graf düğüm sayısından azsa, graf bir çevrim içeriyor demektir.

Örnek Uygulama: Ders Ön Koşulları

Topolojik sıralama algoritmasının klasik uygulamalarından biri, üniversite derslerinin ön koşul ilişkilerini düzenlemektir. Örneğin:

  • Matematiksel Analiz → Diferansiyel Denklemler
  • Lineer Cebir → Sayısal Analiz
  • Algoritma Teorisi → Veri Yapıları → İşletim Sistemleri

Topolojik sıralama algoritması, bu dersleri ön koşulları dikkate alarak sıralayarak bir öğrencinin hangi dersleri hangi sırayla alması gerektiğini belirlemede yardımcı olur.