Topological Sort algoritması , Topological Sort nedir ? Topological Sort örnek? Topological Sort konu anlatımı ? Topological Sort Topolojik sıralama Topolojik sıralama nedir ? Topolojik sıralama konu anlatımı ?

Indegree'si en küçük olan node önce yazılır. Indegree, node'a doğru kaç tane ok girdiğidir.Yandaki node'un in-degree'si 3'tür.









İşte elinizdeki diagramdaki node'ları in-degree'lerine göre küçükten büyüğe doğru sıralarsınız. Unique bir sıralama olacak diye bir şey yoktur. Topological sort ile birbirinden farklı sıralamalar yapabilirsiniz.

Soldaki grafikte, tüm node'ların in-degree değerleri üstlerinde yazılıdır. Buna göre topological sıralama yapılmak istenirse, en düşük in-degree'ye sahip olan 'a' node'unun ilk sırada yazarız.

   a - ?

Bundan sonra 'a' node'unu ve bu node'a giren çıkan tüm okları sileriz. Böylece kalan node'ların in-degree değerleri değişebilir. Bundan sonraki adımda gene en küçük in-degree değerine sahip node'u yazarak devam ederiz.

   'a' node'unu ve buna giren çıkan tüm okları sildikten sonra 'b', 'c' ve 'e' node'larının in-degree'leri değişir. Sonuçta yandaki gibi bir grafik elde edilir.

Şimdi önümüzde iki seçenek var. 'b' node'unu ya da 'c' node'unu seçebiliriz.

1.Seçenek:   a - b - ?  (Bu yoldan devam ettiğimizi varsayalım , dolayısıyla b node'unu ve bu node'a giren çıkan okları silerek devam edeceğiz.)

2.Seçenek:   a - c - ? (Bu yol da takip edilebilirdi.)

In-degree'leri sürekli güncellediğimize dikkat edin. Şimdi önümüzde üç farklı seçenek var. 'd' , 'c' veya 'e' node'larından birisi seçilebilir.

1.Seçenek: a - b - d - ? (Bu yoldan devam ettiğimizi varsayalım..)
2.Seçenek: a - b - e - ? (Bu yol da takip edilebilirdi.)
3.Seçenek: a - b - c - ? (Bu yol da takip edilebilirdi.)

   Şimdi de önümüzde 2 seçenek var: 'e' veya 'c' node'u.
   'e' node'u ile devam ettiğimizi varsayalım.(Uzatmamak için bundan sonraki adımlarda diğer seçenekleri yazmayacağım)

   a - b - d - e - ?

 

'g' node'u ile gittiğimizi varsayalım.

 a - b - d - e - g - ?

Bu sefer önümüzde tek seçenek var: 'c' node'u .




a - b - d - e - g - c - ?

Yine tek seçenek var : 'f' node'u.

a - b - d - e - g - c - f - ?

Yine tek seçenek var : 'h' node'u.

a - b - d - e - g - c - f - h - ?

Tek seçenek var: 'i' node'u.

a - b - d - e - g - c - f - h - i








Elimizde node kalmadı ve elde ettiğimiz topological sıralama  şu :     a - b - d - e - g - c - f - h - i 
Bizim elde ettiğimiz bu sıralama bir çok muhtemel topological sıralamadan sadece bir tanesidir. Yukarıdaki takip ettiğimiz yol ile bir çok farklı topological sıralama elde edebilirsiniz.

Notes:
- Topological sort sonucunda, Directed-Acyclic Graph(DGA)'daki node'lar öyle bir sıralanır ki , bir a node'undan bir y node'una doğru bir edge varsa yani (a,b) edge'i varsa , a node'u sıralamada b 'den önce gelir.
- Eğer graph'da cycle varsa , topological sorting yapamazsınız.

Bu yazımda faydalandığım kaynak :
http://www.brpreiss.com/books/opus4/html/page557.html