Topological Sort(Sıralama)

Topological sort bir sıralama algoritmasıdır ve graflar üzerinde gerçeklenir. Topological sort'u uygulamak için gerekli olan en önemli koşul ele alınan grafın "directed acyclic graph" olmasıdır. Yani sıralama yapılacak olan grafın herhangi bir düğümünden başlanıldığında diğer düğümleri ziyaret ettikten sonra  bir döngü üzerinde tekrar kendisine gelememe durumudur. Eğer başlanılan düğüme bir döngü üzerinden tekrar geliniyorsa "directed cyclic graph" olur. Bu şartın sağlanması durumunda topological sort şu şekilde uygulanır:
İlk başta kök,root veya herhangi bir düğümün çoçuğu olmayan düğüm, alınır. (Bunun birden fazla olması problem değildir istenilen düğümden başlanılabilir.) Alınan düğümün değeri yazılır ve o düğümün kendisi ve bağlantıları silinir. Daha sonra yine aynı şekilde varolan düğümler içerisinden yeni bir kök seçilir ,değeri yazılır ve tekrar kendisi ve bağlantıları silinir. Bu işlem bütün düğümler bitene kadar tekrarlanır.

Bu işlemleri sonucunda elde edilen sıralama farklılık gösterebilir. Yukarıda da bahsettiğimiz üzere bunun sebebi birden fazla kök düğümü olabileceğinden o anda seçilen kök düğümüne göre değişiklik göstermesidir.

Bir örnek üzerinde bunun nasıl gerçekleştiğini inceleyelim:

Şekil-1

Şekil-1 den başlangıç düğümü olarak "a"' yı seçeriz ve "a" ve "a" nın bağlantılarını sileriz. 

Sıralama : a

Şekil-2

Şekil-2 de kök olarak hem "b" yi hem de "c" yi seçebiliriz. Biz "b" yi alalım. "b" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b

Şekil-3

Şekil-3 de kök olarak hem "c" yi hem de "d" yi seçebiliriz. Biz "c" yi alalım. "c" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c

Şekil-4

Şekil-4 de kök olarak hem "d" yi hem  "f" yi hem de "e" yi seçebiliriz. Biz "d" yi alalım. "d" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c,d

Şekil-5

Şekil-5 de kök olarak hem "e" yi hem de "f" yi seçebiliriz. Biz "e" yi alalım. "e" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c,d,e

Şekil-6

Şekil-6 de kök olarak hem "f" yi hem de "g" yi seçebiliriz. Biz "f" yi alalım. "f" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c,d,e,f

Şekil-7

Şekil-7 de kök olarak hem "g" yi hem de "h" yi seçebiliriz. Biz "g" yi alalım. "g" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c,d,e,f,g

Şekil-8

Şekil-8 de kök olarak "h"yi seçeriz. "h" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c,d,e,f,g,h

Şekil-9

Son olarak şekil-9 da "i" yi sıralamaya ekleriz ve sileriz.

Sıralama : a,b,c,d,e,f,g,h,i şeklinde gerçekleşir.

Tabiki bunun dışında gerçekleşecek sıralamalarda mevcut.

Alternatif sıralamalar :


1 ) a, b, c, d, e, f, g, h, i

2 ) a, c, b, f, e, d, h, g, i

3 ) a, b, d, c, e, g, f, h, i

4 ) a, c, f, b, e, h, d, g, i

 Bu yazı yazılırken faculty.kfupm.edu.sa/ics/jauhar/ics202/Unit24_TopologicalSort.ppt powerpoint sunumundan yararlanılmıştır .