Yerleştirilen
Yerleştirilmeyi bekleyen
İncelenen kenar

  • Şu anki
  • Serbest ya da ziyareti süren
  • Yerleştirilen
  • Döngü

Topolojik sıralama hakkında daha fazla

Topolojik sıralama

Ayakkabıdan önce çorap, duvardan önce temel, bir dersten önce ona ön koşul olan ders. Topolojik sıralama, tek yönlü kenarları olan bir grafın düğümlerini her kenarın ileriyi gösterdiği bir sıraya dizer. Kahn algoritmasını ya da DFS yöntemini seçin ve sıranın büyümesini görmek için adım adım ilerleyin; sonra neden hiçbir sıranın mümkün olmadığını görmek için bir döngü ekleyin. Sıranın büyümesini izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Her kenar, okun gösterdiği gibi tek yönlüdür: onu "bu, şundan önce gelir" diye düşünün. Yöntemi seçin: Kahn algoritması önce gelen kenarı olmayan düğümleri yerleştirir ve her düğümdeki sayı, o düğümün hâlâ kaç gelen kenarı olduğunu gösterir; DFS yöntemi, bir düğümden sonra gelen her şey yerleştirilince o düğümü başa koyar. Grafın altındaki satır şimdiye kadarki sıradır. Her yöntemin döngüyü nasıl bulduğunu görmek için Döngü ekle'yi işaretleyin. Yeni graf başka bir graf oluşturur; kaç düğüm ve kenar olacağını seçin. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.

Nasıl çalışır

  1. Kahn algoritmasını ya da DFS yöntemini seçin.
  2. Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
  3. Grafın altında sıranın büyümesini izleyin. Her yöntemin döngüyü nasıl bulduğunu görmek için Döngü ekle'yi işaretleyin.

Kahn algoritması

Her düğüm için ona kaç kenarın gittiğini sayın. Hiç gelen kenarı olmayan bir düğüm hiçbir şeye bağlı değildir, yani önce gelebilir. Böyle bir düğümü yerleştirin ve çıkan kenarlarını kaldırın: bu kenarların gösterdiği düğümlerin artık bir gelen kenarı eksiktir ve bazıları sıfıra inip serbest kalabilir. Serbest düğüm kalmayana kadar yerleştirmeye devam edin. Bazı düğümler hiç serbest kalmadıysa bir döngü içinde birbirlerini bekliyorlardır ve topolojik sıra yoktur.

DFS yöntemi

Ziyaret edilmemiş her düğümden bir derinlik öncelikli arama başlatın. Bir düğüm, ondan ulaşılabilen her şey tamamlandığında tamamlanır; yani ondan sonra gelmesi gereken her şey zaten yerleştirilmiştir. Tamamlanan her düğümü sıranın başına koyun; sıra doğru çıkar. Arama, hâlâ içinde olduğu bir düğüme giden bir kenarı izlerse o kenar bir döngü kapatır ve yine hiçbir sıra yoktur.

Sık sorulan sorular

Topolojik sıralama nedir?

Yönlü bir grafın düğümlerinin, her kenarın önceki bir düğümden sonraki bir düğüme gittiği bir sıralaması. Kenarlar "önce gelmeli" anlamına geliyorsa, bu tüm görevlerin yapılabileceği bir sıradır.

Topolojik sıra ne zaman vardır?

Tam olarak grafta yönlü döngü olmadığında: graf yönlü döngüsüz bir graftır, yani DAG'dir. Döngü olsaydı, döngüdeki her düğümün kendisinden önce gelmesi gerekirdi.

Topolojik sıra tek midir?

Genellikle değildir. İki düğüm bir kenar zinciriyle bağlı değilse hangisi önce gelirse gelsin olur, bu yüzden bir grafın birçok geçerli sırası olabilir. Kahn algoritması ve DFS yöntemi çoğu zaman farklı sıralar verir.

Topolojik sıralama ne kadar hızlıdır?

İki yöntem de her düğüme ve her kenara sabit sayıda bakar, yani iş düğüm sayısı ile kenar sayısının toplamıyla artar.

Grafım bir yere gönderiliyor mu?

Hayır. Graf tarayıcınızda oluşturulur ve sıralanır, son ayarlarınız da bu tarayıcının yerel depolamasında kalır.

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

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

Editöre Git