Topolojik Sıralama

Graflar O(V + E) O(V)

Bir YYG'nin düğümlerini her kenar ileri bakacak şekilde doğrusal sıralar — Kahn algoritması giriş derecesi 0 olan düğümleri ayıklar.

1/23

İç dereceler sayılıyor (her düğümün altındaki rozet).

DeğişmezŞimdiye kadar yayınlanan her düğümün tüm ön koşulları ondan önce yayınlanmıştır.

mevcutsınırziyaret edildiağaç kenarı

topological-sort.c

#define V 6
 
void topoSort(int graph[V][V]) {
    int indeg[V] = {0};
    for (int u = 0; u < V; u++)
        for (int v = 0; v < V; v++)
            if (graph[u][v]) indeg[v]++;
 
    int queue[V], front = 0, rear = 0;
    for (int v = 0; v < V; v++)
        if (indeg[v] == 0) queue[rear++] = v;
 
    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u);
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && --indeg[v] == 0)
                queue[rear++] = v;
        }
    }
 
    if (rear < V)
        printf("\ncycle: %d node(s) never reached in-degree 0", V - rear);
}

Topolojik Sıralama nasıl çalışır?

Giriş derecesi 0 olan bir düğümü kopar, çıkan kenarlarını sil ve tekrarla (Kahn algoritması). Kuyruk tüm düğümler çıkmadan boşalırsa grafta döngü vardır.

Ne zaman kullanılır?

Bağımlılık altında iş sıralama: derleme sistemleri, ders ön koşulları, hesap tablosu değerlendirme.