Topolojik sıralama

Yazılım kurduğunuzda, bir program derlediğinizde ya da bir proje planladığınızda, bir şeyin önce neyin yapılacağına karar vermesi gerekir. B görevi A görevine ihtiyaç duyuyorsa A daha önce gelmelidir. Topolojik sıralama, böyle kurallardan oluşan bir ağı tek bir düz çizgiye dönüştürür.

Tek yönlü oklarla bağlı düğümlerden oluşan bir graf; yerleştirilen düğümler yeşil, şimdiye kadarki sıra da altta bir satır olarak çizilmiş
Tek yönlü oklarla bağlı düğümlerden oluşan bir graf; yerleştirilen düğümler yeşil, şimdiye kadarki sıra da altta bir satır olarak çizilmiş

Temel fikir

Her görevi bir düğüm, her "B'den önce A" kuralını da A'dan B'ye bir ok olarak çizin. Topolojik sıra, her okun sağı gösterdiği, tüm düğümlerden oluşan bir satırdır. Bir şeyleri sıraya koyduğu için sıralama denir, ama sayıları sıralamanın aksine yalnızca oklara uyması gerekir: hiçbir ok zincirinin bağlamadığı düğümler herhangi bir sırayla gelebilir.

Ne zaman imkânsızdır

Oklar bir döngü oluşturuyorsa, örneğin A B'den, B C'den ve C A'dan önceyse, A'nın kendisinden önce gelmesi gerekirdi. Yani topolojik sıra tam olarak grafta yönlü döngü olmadığında vardır. Böyle bir grafa yönlü döngüsüz graf ya da DAG denir. Aşağıdaki iki yöntem de varsa bir döngüyü bulur, bu yüzden kullanışlı bir döngü testi de sayılırlar.

Bir örnek

A → C, B → C, B → D, C → E ve D → E oklarını alın. Kahn algoritması gelen okları sayar: A ve B'nin hiç yok, bu yüzden önce A, sonra B gelir. B'nin oklarını kaldırmak C ve D'yi serbest bırakır; onlar gelir, sonra da E: sıra A, B, C, D, E. DFS yöntemi A'yı, sonra C'yi, sonra E'yi ziyaret eder; önce E tamamlanır, sonra C, sonra A ve her biri başa geçer. Sonra B ve D'yi ziyaret eder; bunlar onların önünde tamamlanır: sıra B, D, A, C, E. İki sıra da doğrudur.

Kahn mı, DFS mi?

Arthur Kahn'ın 1962'de yayımladığı Kahn algoritması ileriye doğru çalışır: hangi görevlerin şu anda başlayabileceğini her zaman bilir, bu da planlamaya uygundur ve serbest görevler arasından alfabetik sıra gibi herhangi bir kurala göre seçim yapabilir. Robert Tarjan'ın 1976'da yaygınlaştırdığı DFS yöntemi uçlardan geriye doğru çalışır ve yalnızca derinlik öncelikli aramaya ihtiyaç duyar. İkisinin de süresi düğüm sayısı ile kenar sayısının toplamıyla artar.

Robert Tarjan, 1972–73’te John Hopcroft ile birlikte derinlik öncelikli aramanın birçok çizge problemini doğrusal zamanda çözdüğünü gösterdi; 1986 Turing Ödülü’nü kısmen bu çalışma için aldılar.
Robert Tarjan, 1972–73’te John Hopcroft ile birlikte derinlik öncelikli aramanın birçok çizge problemini doğrusal zamanda çözdüğünü gösterdi; 1986 Turing Ödülü’nü kısmen bu çalışma için aldılar.

Kullanım alanları

make gibi derleme araçları dosyaları, bağlı oldukları dosyalardan sonra derler. Paket yöneticileri kütüphaneleri bağımlılık sırasıyla kurar. Elektronik tablolar bir hücreyi, formülünün kullandığı hücrelerden sonra yeniden hesaplar. Üniversiteler derslerin ön koşullarının karşılanabildiğini denetler, derleyiciler komutları sıralar, veri hatları da her adımı girdileri hazır olunca çalıştırır. Unix'teki tsort komutu kendi başına topolojik sıralama yapar.

Keşfedin

Uygulamayı açın ve Adım'a basın. Oklar hangi düğümün hangisinden önce gelmesi gerektiğini söyler. Kahn algoritmasında her düğümdeki sayı kalan gelen okları sayar ve serbest düğümler mavidir. DFS yönteminde mavi düğümlerin ziyareti sürmektedir, yeşil olanlar ise yerleştirilmiştir. Sıra, grafın altındaki satırda büyür. Döngü ekle'yi işaretleyin ve iki yöntemin de hiçbir sıranın olmadığını keşfetmesini izleyin.

Sık sorulan sorular

Burada topolojik ne anlama geliyor?

Ad, şeylerin tam biçiminden çok nasıl bağlandığını inceleyen topolojiden gelir. Sıra yalnızca hangi düğümlerin oklarla bağlı olduğuna bağlıdır, nereye çizildiklerine değil.

Sıra olmadığında döngüyü nasıl bulurum?

DFS yöntemi onu doğrudan gösterir: ziyareti hâlâ süren bir düğüme giden kenar, ziyareti süren düğümlerin yoluyla birlikte döngüyü oluşturur. Kahn algoritması yalnızca hangi düğümlerin takıldığını söyler; bunlar arasında yapılan bir arama döngüyü bulur.

Geçerli sıralar arasından belirli birini seçebilir miyim?

Evet. Kahn algoritmasında birkaç düğüm serbestse tercih ettiğinizi seçin, örneğin en küçük harfi ya da en acil görevi. Öncelik kuyruğu kullanmak alfabetik olarak ilk gelen sırayı verir.

Topolojik sıralama en kısa yollarda nasıl kullanılır?

Yönlü döngüsüz bir grafta, uzaklıkları her düğümün kenarları boyunca topolojik sırayla güncellemek, bir başlangıçtan tüm en kısa yolları tek geçişte bulur; negatif kenarlar olsa bile ve Dijkstra ya da Bellman–Ford'dan daha hızlı.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Topolojik sıralamayı deneyin