Algoritmalar Ve Programlama Dersi 8. Ünite Özet

Giriş

Çizge (graph), düğümlerle bu düğümleri birbirine bağlayan kenarlardan oluşan ve ağ görünümünde olan bir tür veri yapısıdır. Temel olarak birbirleriyle ilişkili verileri temsil etmek için kullanılırlar. Çizgelerin ulaşım, bilgisayar ağları, elektrik devreleri, sosyal ağlar gibi günlük hayattaki birçok alanda uygulamaları mevcuttur.

Herhangi bir çizgenin içerdiği düğümler, özel arama algoritmalarıyla bir noktadan başlanarak belirli sırada ziyaret edilebilmekte ve listelenebilmektedir. Çizgeler üzerinde bu işlemin yapılabilmesi için temel olarak enine arama (breadth-first search) ve önce derinliğine arama (depth-first search) algoritmaları mevcuttur. Bunun yanısıra, çizgelerin içerdiği düğüm noktaları arasındaki en kısa mesafelerin hesaplanması da söz konusu olabilir.

Çizgelerle İlgili Temel Kavramlar Çizgeler, matematiksel olarak aşağıdaki formüldeki gibi temsil edilirler. Bu formülde, Ç ifadesi çizgeyi, D ve K ifadeleri ise sırasıyla düğümleri ve kenar bağlantılarını temsil etmektedir. Ç = (D, K)

Çizgeler, düğümler arasındaki kenar bağlantılarının tipine göre yönlü çizge (directed graph) ve yönsüz çizge (undirected graph) olmak üzere ikiye ayrılırlar. Yönlü çizge, kenar bağlantılarının yönleri temsil eden oklarla gösterildiği çizgedir. Çizge içerisindeki birbirine bağlı iki düğüm noktası arasında, sadece ilgili okun işaret ettiği yönde ilerlenebilmesi mümkündür. Yönsüz çizge, kenar bağlantılarının yönleri temsil eden oklar ile gösterilmediği çift yönlü olan çizgedir. Çizge içerisindeki birbirine bağlı iki düğüm noktası arasında her iki yönde de ilerlenebilmesi mümkündür. Bir anlamda, düğümler arasındaki bağlantıların simetrik olduğu söylenebilir.

Yönlü bir çizge aşağıdaki şekilde ifade edilebilir: D={1, 2, 3, 4} K={(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 2), (3, 4)}

D kümesinin içerisinde 4 farklı düğüm noktası bulunmaktadır. K ise şekildeki 6 adet kenar bağlantılarını temsil etmektedir. Örneğin, K içerisindeki (1,2) ifadesi, 1 düğümü ile 2 düğümü arasında çift yönlü bir kenar bağlantısı olduğunu göstermektedir.

Çizgelerde komşuluk (adjacency) ve çakışım (incidence) olmak üzere iki farklı ilişki türü vardır. Komşuluk, iki düğüm arasında bir bağlantı olmasıdır. Çakışım ise düğüm ile kenar bağlantısı arasındaki ilişkiyi belirtir.

Çizgelere özgü yol, bağlantılılık gibi bazı kavramlar bulunmaktadır. Yol (path), çizgenin içerisinde bir düğümden başka bir düğüme ulaşmak için geçilmesi gereken düğümlerdir. Bir yolda tekrar edilen düğümler yoksa bu yola, basit yol (simple path) denilir. Çizgeler hakkındaki bir diğer önemli husus ise düğümlerin komşuluk ilişkilerinin temsil edilme şeklidir. Bu amaçla kullanılabilecek en çok bilinen yöntemlerden birisi komşuluk matrisi (adjacency matrix) yöntemidir.

Komşuluk matrisi oluştururken düğüm sayısı kadar satırı ve sütunu olan bir tablo kullanılır. Bu tabloda, aralarında komşuluk olan düğümler için 1 değeri kullanılırken, komşuluk olmayan düğümler için 0 değeri kullanılmaktadır. Ağırlıklandırılmış çizge (weighted graph), düğümler arasındaki kenar bağlantıları üzerinde sıfırdan farklı sayısal değerlerin yer aldığı çizge türüdür. Bu türde çizgelerin komuşuluk matrisinde 1 yerine farklı sayılar olması da söz konusu olabilir.

Enine Arama Algoritması

Enine arama, çizgenin bir düğümünden başlanarak, söz konusu düğümün komşu düğümlerinin ve onların da komşularının sırayla ziyaret edildiği arama algoritmasıdır. Bu algoritmanın çalışması sırasında, öncelikle başlangıç düğümünün tüm komşuları ziyaret edilir. Daha sonra, başlangıç düğümünün komşuları ile komşu olan düğümlerden devam edilir. Algoritmanın uygulanması esnasında kuyruk (queue) veri yapısından faydalanılır.

Örnek olarak aşağıdaki yönsüz çizgeyi ele alalım (bkz. Şekil 8.4): D={S, A, B, C, D} K={(S, A), (S, B), (S, C), (A, D), (B, D), (C, D)}

Algoritma ilk çalıştığında, aramaya çizgenin S isimli düğümünden başlanmıştır. Sonraki adımda S düğümünün komşuları sırayla ziyaret edilir. İkinci adımda A düğümü ziyaret edilir ve bu ziyaretin bilgisine de kuyruk veri yapısı içerisinde yer verilir. Üçüncü ve dördüncü adımlarda S düğümünün diğer iki komşusu olan B ve C düğümleri ziyaret edilir. Artık S düğümünün komşuları içinde ziyaret edilmemiş başka bir düğüm bulunmamaktadır. Bu sebeple kuyruk veri yapısı içerisinden bir eleman çıkartılır. Bu eleman, kuyruğun en başındaki A düğümüdür. Daha sonra A düğümünün komşusu olan D düğümü ziyaret edilir. Algoritmaya B ve C düğümlerinin komşularının ziyaret edilmesiyle devam edilecektir. Ancak, D düğümü zaten ziyaret edilmiş durumda olduğundan bu aşamada bir işlem yapmaya gerek yoktur. Son olarak, D'nin de ziyaret edilmemiş komşusu olmadığı için algoritma sonlanır. Algoritma sona erdiğinde, kuyruk veri yapısının içinde hiçbir düğüm bulunmayacaktır. 5 düğümün tamamı erişilebilir durumda olduğundan hepsinin ziyaret edilmesi mümkün olmuştur. Enine arama algoritması, bu örnekte sırasıyla S, A, B, C, D düğümlerini ziyaret etmektedir.

Çizge üzerinde enine aramaya yönelik kod örneği için kitabınızdaki Örnek 8.1’i inceleyiniz.

Önce Derinliğine Arama Algoritması

Önce derinliğine arama, çizgenin bir düğümünden başlanarak bu düğümün komşusu üzerinden gidilebilecek en uzak düğüme kadar olan noktaların ziyaret edildiği ve daha sonra geri dönülerek aynı işlemlerin ziyaret edilmemiş düğümler için sürdürüldüğü bir arama algoritmasıdır. Algoritmanın uygulanması esnasında yığın (stack) veri yapısından faydalanılır.

Örnek olarak aşağıdaki yönsüz çizgeyi ele alalım (bkz. Şekil 8.6): D={S, A, B, C, D} K={(S, A), (S, B), (S, C), (A, D), (B, D), (C, D)}

Algoritma ilk çalıştığında aramaya çizgenin S isimli düğümünden başlanmıştır ve S düğümü yığının içerisine eklenmiştir. Daha sonra, komşular arasında alfabetik olarak en önde gelen A düğümü ile devam edilmiştir. Bu düğüm de yine yığına eklendikten sonra A’nın komşusu olan D düğümüyle devam edilmiştir. Bu aşamada, D düğümü de yığına eklenmiştir. D düğümünün komşuları B ve C düğümleridir. Alfabetik sıra göz önüne alındığında B düğümü ile ziyarete devam edilmiştir ve B düğümü de yığına eklenmiştir. Bu aşamadan sonra, B düğümünün ziyaret edilmemiş komşusu bulunmadığı için bu düğüm yığından çıkarılmış ve bir önceki düğüme geri dönülmüştür. Bir önceki düğüm olan D düğümünün ziyaret edilmemiş komşusu durumundaki C düğümü ziyaret edilmiş ve yığına eklenmiştir. Bu işlemlerin sonunda tüm düğümler ziyaret edilmiş durumdadır. Sonrasında, yığındaki elemanlar tek tek çıkarılmakta ve çıkarılanın ilgili düğümün ziyaret edilmemiş komşusu olup olmadığına bakılmaktadır. Düğümlerin tamamı ziyaret edilmiş durumda olduğundan, yığındaki tüm elemanlar sırayla çıkarılmıştır. Son olarak, yığında eleman kalmadığı ve aramanın sona erdiği görülmektedir. Önce derinliğine arama algoritması, bu örnekte sırasıyla S, A, D, B, C düğümlerini ziyaret etmektedir.

Çizge üzerinde önce derinliğine aramaya yönelik kod örneği için kitabınızdaki Örnek 8.2’i inceleyiniz.

Djikstra En Kısa Yol Algoritması

Dijkstra algoritması, ağırlıklandırılmış çizgelerde bir başlangıç düğümü ile diğer düğümler arasındaki en kısa mesafeyi tespit etmek için kullanılır. Bu algoritmanın amacını açıklamak için örnek olarak Türkiye haritasındaki şehirlerin bir çizge üzerinde düğümler olarak gösterildiğini varsayalım. Düğümler arasındaki ağırlıklandırılmış kenar bağlantıları ise her iki şehir çifi arasındaki uzaklığı temsil edecektir. Bu bilgilerin yardımıyla Dijkstra algoritması kullanılarak, belirtilen bir şehir ile diğer bütün şehirler arasındaki en kısa yollar bulunabilir. Sonuçta, çıktı olarak farklı şehirler arasındaki en kısa mesafeler ve izlenmesi gereken yollar elde edilecektir. Bu algoritmanın başlangıcında, başlangıç düğümü ile diğer düğümler arasındaki uzaklıkların tamamının sonsuz olduğu varsayılır. Algoritma, düğümler arasındaki en kısa yolları aradığı için düğümler arasında daha kısa yollar bulundukça, sonsuz değeri ilgili yolun uzunluğu ile değiştirilir.

Örnek olarak aşağıdaki yönsüz ağırlıklandırılmış çizgeyi ele alalım (bkz. Şekil 8.8). Kenar bağlantıları (düğüm1, düğüm2, ağırlık) şeklinde ifade edilmiştir. D={0, 1, 2, 3, 4} K={(0, 1, 4), (0, 3, 8), (1, 2, 3), (2, 3, 4), (3, 4, 7)}

Dijkstra algoritması, her bir adımında ziyaret edilenler listesine yeni bir düğüm eklemekte ve düğümler arası mesafeleri günceller. Mesafe değeri kesinleşen ve üzerinde artık işlem yapılmayacak düğümleri gösteren hücreler, tablo içerisinde mavi olarak görüntülenir. Parantez içerisinde belirtilen değerler, o mesafenin elde edilmesi için ziyaret edilmesi gerekli olan düğümü gösterir. İlk olarak 0 düğümü ziyaret edilir. 0 düğümü ile diğer düğümlerin arasındaki mesafeler incelenir ve ilk satırın değerleri oluşturulur. 0 düğümü doğrudan sadece 1 ve 3 düğümleri ile komşu olduğu için bu tablo hücrelerine 4 ve 8 değerleri verilir. 2 ve 4 düğümleri ile komşu olmadığı için onlar ile arasındaki mesafe sonsuzdur. İkinci işlem adımına başlarken, ilk satırdaki mavi olmayan değerler içerisinden en küçük olan tespit edilir. 4, 8 ve sonsuz değerleri içerisinde en küçüğü 4 olduğu için bir sonraki adımda 1 düğümünün ziyaret edilmesi söz konusudur. Çünkü 4 değeri 1 düğümüne ait sütunda yer almaktadır. 1 düğümünü ziyaret ederken ilgili satırdaki değerlerin hangilerinin güncelleneceği tespit edilmelidir. 1 düğümü, 2 ve 0 düğümleri ile komşu durumdadır. Bu sebeple, 0 ile 2 düğümleri arasındaki mesafenin 4 ve 3’ün toplamı olan 7 değeri olduğu tespit edilir ve tabloya yazılır. Daha sonra, ikinci satırdaki mavi olmayan değerler içerisinden en küçük olan tespit edilir. 7, 8 ve sonsuz değerleri arasından en küçüğü 7 olduğu için bir sonraki adımda 2 düğümünün ziyaret edilmesi söz konusudur. 2 düğümü, 1 ve 3 düğümü ile komşudur. 0, 1 ve 2 düğümlerini kullanarak 3’e ulaşmak mümkündür. Ancak ilgili mesafe, 4, 3 ve 4 sayılarının toplamı olan 11 sayısına eşittir. Bu değer 8’den büyük olduğu için 3 düğümüne ulaşmak için gerekli en küçük mesafede bir değişiklik yapılmayacaktır. Böyle bir durumda, mesafe değeri olarak daha küçük bir sayı elde edilebilseydi tablonun güncellenmesi gerekirdi. Daha sonra, mevcut satırda mavi olmayan 8 ve sonsuz arasından en küçük olan değerin tespit edilmesi gereklidir. 8 değeri küçük olduğu için bir sonraki adımda 3 düğümü ziyaret edilir. 3 düğümü ile 4 düğümü arasında komşuluk bulunduğu için tabloya 15 sayısı yazılır. Bunun sebebi, 3 düğümüne ulaşmak için en kısa mesafenin 8 olduğunun bilinmesi ve bu sayının son iki düğüm arasındaki mesafe olan 7 sayısı ile toplanmış olmasıdır. Yani 0 ve 3 düğümleri ziyaret edilerek 4 düğümüne ulaşılmıştır. Algoritmanın çalışması tamamlanmıştır ve son satırdaki değerler 0 düğümünden her bir sütunda bulunan ilgili düğümlere ulaşmak için en kısa yollardır. Örneğin, 0 ile 2 düğümü arasındaki en kısa mesafe 7’dir. Bunun için öncesinde 1 düğümünün ziyaret edilmesi gereklidir

Çizge üzerinde Djikstra algoritmasıyla en kısa yolu bulmaya yönelik kod örneği için kitabınızdaki Örnek 8.3’i inceleyiniz.