Ağlarla ilgili Tanımlar
Ağ Yapılarının Tarifi
Bir önceki bölümde tanıttığımız veri ağaçları aslında ağ yapılarının özel bir türünü oluştururlar.
Aşağıdaki şekil sayılarla numaralandırılmış, bazıları birbirlerine bağlı noktalardan oluşan bir ağ yapısını gösteriyor. Aşağıda da belirteceğimiz gibi, her ağ yapısı bu şekilde kendilerine ait özellikleri veya doğrultuları olmayan bağlantılardan oluşmaz. Bu şekil bir yönsüz ağı gösteriyor.
| Şekil 6‑1 Bir yönsüz ağ yapısı. |
Ağ yapılarını “veri ağları” diye adlandırmıyoruz. Bir veri ağı birbirleriyle şu veya bu şekilde ilişikili bir veri grubu demek olurdu, ama bu günlük hayatta da çok değişik örneklerini gördüğümüz ağ yapıların ancak bir alt türü olurdu. Bir ülkenin büyük şehirleri arasındaki otoyol bağlantıları, elektrik üretim santrallerini ana dağıtım noktalarıyla bağlayan elektrik iletim hatları, telefon veya diğer veri iletim hatlarının oluşturduğu iletişim ağları, vb. ağ yapılarının en iyi bilinen fiziksel örnekleridir. Belli bir dile ait sözcükler ve dilbilimsel kuralların oluşturduğu ilişkiler ağı bile –fiziksel olmasa da- bir ağ yapısı sayılabilir.
Ağ Yapılarının Türleri
Kapalı halkalar oluşturmayan, açık uçlu bağlantılardan oluşan ağ yapılarına “veri ağaçları” dediğimizi az önce belirttik. Yani veri ağaçları ağ yapılarının bir türüdür. Aşağıdaki şekil açık uçlu yönsüz bir ağ yapısının (a) bir veri ağacı (b) ile eşdeğer olduğunu gösteriyor.
Şekil 6‑2 Halka içermeyen bir ağ yapısı ile bir veri ağacının eşdeğerliği
Diğer ağ yapıları da bağlantıların tiplerine göre türlere ayrılırlar.
Bağlantılarıyla ilgili bilgi içermeyen ağ yapılarına “ağırlıksız ağlar” (unweighted graphs) denir. Bir havayolu şirketinin hangi havaalanları arasında uçuşlar yaptığını gösteren bir uçuş rotaları şeması ağırlıksız ağlara iyi bir örnektir. Veri ağaçları da ağırlıksız ağların bir alt türü sayılabilirler. Şekil 6‑1’de bağlantılara özellik atanmamıştır; o yüzden ağırlıksız bir ağı göstermektedir.
Bağlantılarına bir veya daha fazla özellik atanmış ağ yapıları ise “ağırlıklı ağlar” (weighted graphs) diye bilinirler. Yol uzunlukları, yolların trafik yoğunlukları veya kapasiteleri gibi ekstra bilgiler içeren karayolları haritaları ağırlıklı ağ örnekleridirler.
| Şekil 6‑3 Bir ağırlıklı ağ ile temsil edilen basitleştirilmiş bir yol haritası |
Yönsüz (undirected) bir ağda, Şekil 6‑1’de olduğu gibi bağlantıların yönü belirtilmemiştir; birbirlerine bağlı iki noktanın herhangi birinden diğerine geçişin olduğu varsayılır.
Buna karşın, yönlü (directed) bir ağda ise bağlantıların yönleri vardır ve yalnızca gösterilen yönlerde geçişe izin verirler. Yalnızca tek yönlü caddelerden oluşan bir şehir planı veya uçuş yönüne göre farklı rotalar tanımlayan uçuş rotaları haritaları yönlü ağ örnekleri arasında sayılabilirler.
| Şekil 6‑4 Bir yönlü ağ yapısı |
Bilgisayarlarda Ağ Yapıları
Bir ağ yapısını bir bilgisayar programında nasıl temsil edeceğimiz ağın yukarıda belirtilen türlerden hangisine ait olduğuna, veya programın ağ üzerinde ne tür işlemler yapacağına göre değişebilir, ama genelde kabul gören iki temsil şekli vardır:
Komşu Listeleri (adjacency lists)
Az sayıda bağlantıları olan bir ağ yapısında her bir nokta (vertex) için diğer hangi noktaların bu noktaya bağlı olduğunu gösteren bir liste tutulması yeterli olur.
Şekil 6‑5 (a) Yönsüz (Şekil 6‑1) ve (b) yönlü (Şekil 6‑4) ağları temsil eden komşuluk listeleri
Bir veri ağacındaki bir ana elemanın altındaki çocuk elemanlar listesi de aslında bir komşu listesidir. Bir komşu listesinde bağlantılı noktaları temsil eden değişkenlerin adresleri, veya o değişkenlere erişim sağlayacak veya hiç değilse onların hangileri olduğu belirtecek sıra numarası vb. türünden bilgiler olması gerekir. Ağırlıklı ağları temsil eden komşu listelerinde bağlantıların ağırlıkları olarak işlem görecek özellikleri de bulunmalıdırlar. Örneğin, bilgisayarda bir karayolları haritasını temsil eden ağ yapısında, her bir şehirin adı yanındaki komşu listesi o şehirden erişilebilecek şehirlerin adlarından başka yol uzunluklarını, trafik kapasitelerini, vb. gösteren veriler de içermelidir. Komşu listeleriyle temsil edilen bir ağ yapısı yönsüz ise birbirlerine bağlı herhangi iki nokta birbirlerinin komşu listelerinde gözükürler. Dolayısıyla yönsüz bir ağ yapısını temsil eden komşuluk listelerindeki toplam eleman sayısı bağlantı sayısının iki katıdır. Yönlü bir ağda ise herhangi bir bağlantı yalnız belli bir yönde geçişe izin verdiği için birbirlerine bağlı herhangi iki noktadan biri başlangıç noktası, diğeri varış noktası olacaktır. Dönüş yönünde bir bağlantı daha yoksa, başlangıç noktası varış noktasının komşu listesinde gözükmeyecektir (Bkz. Şekil 6‑5). Bu da demek oluyor ki, yönlü bir ağ yapısını temsil eden komşuluk listelerindeki toplam eleman sayısı bağlantı sayısına eşittir.
Bağlantı Matrisleri (adjacency matrices)
Çok sayıda bağlantıları olan bir ağ yapısını temsil etmek için komşu listeleri kullanmak iyi bir fikir olmayabilir. Komşu listeleri kullanıldığında herhangi iki şehir arasında bir bağlantı olup olmadığını araştıracak bir program o noktalardan birini temsil eden elemana bakıp onun komşuluk listesini tarayarak diğer noktanın o listede olup olmadığını anlamak zorundadır. Halbuki her nokta için bütün noktalarla olan/olmayan bağlantıları gösteren bir dizi bulundursaydık, bu tür bir arama yapmak çok daha kolay olurdu. Her bir elemana ait eşit uzunluktaki diziler bir matris oluştururdu ki buna biz bir “bağlantı matrisi” diyeceğiz.
Şekil 6‑6 (a) Yönsüz (Şekil 6‑1) ve (b) yönlü (Şekil 6‑4) ağları temsil eden bağlantı matrisleri
Yukarıdaki şekil daha önce sunulan yönsüz ve yönlü ağları temsil eden bağlantı matrislerini gösteriyor. Bu bağlantı matrislerinin elemanları sıra numaraları satır ve sütunlarda verilen noktalar arasında bağlantı olup olmadığını gösterecek şekilde ya 0 (bağlantı yok) ya da 1 (bağlantı var) değerleri almıştır. Dolayısıyla ağırlıksız bir ağı temsil eden bir bağlantı matrisinin her bir elemanının tek bir bitten ibaret olması yeterlidir. Böylelikle, büyük ağ yapılarını temsil eden matrisler komşuluk listelerine göre çok daha az yer kaplayabilir.Şekil 6‑3’deki gibi ağırlıklı bir ağı temsil eden bir bağlantı matrisinde matris elemanları bağlantıların ağırlıklarını gösteren değerler alacaktır ki o zaman her eleman tek bir bit değil, ağırlık değerini ifade edecek kadar bit gerektirir.
Ağ Yapıları ile İlgili Problemler ve Grafik Algoritmalar
Bir ağ yapısının gerçek hayatta neyi temsil ettiğine bağlı olarak üzerinde çok çeşitli işlemler farklı yollardan yapılabilir. Burada, “grafik algoritmalar” adı altında ağ yapılarıyla ilgili en sık karşılaşılan problemleri ve onların yaygın çözüm yollarını sunan algoritmaları inceleyeceğiz.
Kapsama Ağacı Oluşturulması
Şekil 6‑1’deki gibi halkalar içeren bir yönsüz ağ bir ağaç yapısına eşdeğer sayılamaz. Bu ağın herhangi iki noktası arasında birden fazla bağlantı yolu vardır.
Bu tür bir ağ yapısında bulunan bağlantıları dolaşarak belli bir noktadan diğer noktaların hepsine kapalı halkalar oluşturmaksızın ulaşacak bağlantı yollarını belirleme işlemine “kapsama ağacı” (spanning tree) oluşturmak denir. Bir ağ yapısı üzerinde bir kapsama ağacı iki yolla oluşturulabilir: Genişlik öncelikli arama (breadth-first search) ve derinlik öncelikli arama (depth-first search). Bu iki arama şeklini veri ağaçlarını incelerken tanıtmıştık. Ağ yapıları üzerinde de tıpkı ağaçlar üzerinde çalıştıkları gibi çalışırlar.
Genişlik Öncelikli Arama
Genişlik öncelikli arama kapsama ağacının ilk adımda başlangıç noktasına (yani kök elemanına) doğrudan bağlı bütün noktalara erişir, sonraki adımlarda ise sonra halka oluşturmayacak şekilde diğer noktalara erişecek bağlantıları belirler. Her adımda son erişilmiş noktalardan birine doğrudan bağlı olup daha önceden erişilmemiş noktalara giden bağlantılar belirlenir. Aşağıdaki şekil, genişlik öncelikli arama yoluyla Şekil 6‑3’deki ağ yapısının bağlantılarının ağırlıksız olduğu durumda B noktasını başlangıç alan bir kapsama ağacı oluşturuyor.
Şekil 6‑7 Yönsüz ve ağırlıksız bir ağ üzerinde genişlik öncelikli arama yoluyla
bir kapsama ağacı oluşturulması
Görüldüğü gibi (a) ilk adımda B noktasında doğrudan bağlı noktalara, (b) ikinci adımda ilk adımda erişilmiş olan A’ya bağlı noktaralara, (c) üçüncü adımda yine ilk adımda erişilmiş olan F noktasına bağlı noktalara, ve son olarak da (d) dördüncü adımda yine ilk adımda erişilmiş olan C noktasına bağlı noktalara erişen yollar seçilmiştir. Şekilde gösterilmemiş olan beşinci adımda ise dördüncü adımda erişilmiş olan noktaları daha önce erişilmemiş bir noktaya bağlayan bir bağlantı aranacak ve J-L bağlantısının eklenmesiyle eksiksiz bir kapsama ağacı oluşturulacaktır. Bu eksiksiz kapsama ağacında her noktadan diğer her noktaya erişmek mümkün olacaktır.
Derinlik Öncelikli Arama
Derinlik öncelikli arama yaparken başlangıç noktasından bir başka noktaya erişecek bir bağlantı seçer, eriştiğimiz noktadan başka bir noktaya, o noktadan başka birine, … giden bağlantıları takip ederek daha önce erişilmemiş noktalar buldukça devam ederiz. Bu şekilde bulduğumuz her bağlantıyı ağaca ekler, eklenecek bağlantı kalmayınca geri dönüp daha önce eklenmemiş bir bağlantı bulur ve yine halka oluşturmayacak şekilde gidebildiğimiz kadar gideriz. Aşağıdaki şekil, Şekil 6‑7’deki yönsüz ve ağırlıksız ağ üzerinde derinlik öncelikli arama yoluyla kapsama ağacı oluşturan adımları gösteriyor. Oklar bağlantı yönlerini değil, kapsama ağacına yeni bağlantılar eklerken izlenen yolları (ve eklenecek bağlantı kalmayınca yapılan geri dönüşleri) göstermektedir.
Şekil 6‑8 Yönsüz ve ağırlıksız bir ağ üzerinde derinlik öncelikli arama yoluyla
bir kapsama ağacı oluşturulması
En Kısa Kapsama Ağacı
Dikkat edilirse, Şekil 6‑7’deki genişlik öncelikli arama algoritması ile Şekil 6‑8’deki derinlik öncelikli arama algoritması aynı ağ yapısı üzerinde uygulandıkları halde ikisinde oluşturulan kapsama ağaçları aynı değildir. Genişlik öncelikli arama ile elde edilen kapsama ağacında herhangi iki nokta arasındaki yol (içerdiği bağlantı sayısı açısından) en kısa yol olduğu halde, derinlik öncelikli aramada bu koşul sağlanmıyor. Şekil 6‑8’deki ağ yapısında B ve C noktaları birbirlerine doğrudan bağlı oldukları halde, kapsama ağacının bu iki nokta arasında bulduğu yol tam beş bağlantıdan oluşuyor. Cormen, Leiserson ve Rivest’in (7) ispat da sunarak belirttiği gibi, genişlik öncelikli arama işlemi gerçekten de herhangi iki noktayı en kısa yoldan birbirlerine bağlayan yollar bulacak, yani “en kısa” kapsama ağacını oluşturacaktır. Buna karşın derinlik öncelikli arama bu koşulu sağlayacak bir kapsama ağacı oluşturmayabilir.
Şunu da belirtmeden geçmeyelim: Biz derinlik öncelikli aramayı doğrudan şekil üzerinde, her adımda rasgele yeni bir bağlantı seçerek yaptık. Şekil üzerinde başka türlü seçimler yapsaydık, veya şekil üzerinde değil de komşuluk listelerinde gözüken noktalardan önce ilkine, sonra ikincisine, vb. giden bağlantıları seçerek çalışmış olsaydık, ortaya daha farklı kapsama ağaçları çıkabilirdi.
Kapsama Ağacı Oluşturma Algoritmalarının Uygulanması ve Analizi
İster genişlik öncelikli aramayı kullanalım, ister derinlik öncelikli aramayı uygulayalım, bir kapsama ağacı oluştururken ağ yapısındaki bütün noktalara erişir ve aralardaki bütün bağlantıları ağaca eklenebilecek bağlantılar olarak dikkate alırız. Dolayısıyla bir kapsama ağacı oluşturma algoritmasının adım sayısı nokta sayısı (Nn) ve bağlantı sayısının (Nb) toplamıdır (Nn + Nb).
Bu algoritmalara dayalı programlar noktaların ve bağlantıların, komşuluk listelerinin, vb. nasıl temsil edildiklerine göre birbirlerinden çok farklı olabilirler. Şimdiye kadarki kod örneklerinde kullandığımız yapay dil de bir grafik algoritmaya uyarlanamayacak kadar sınırlıdır; uyarlansa bile algoritmalardan her ikisini de çok farklı şekillerde yazabilirdik. O yüzden basit yazılı ifadelerden ibaret kod örnekleri vermekle yetineceğiz. Örneğin genişlik öncelikli arama aşağıdaki gibi tarif edilebilir:
Başlangıç noktasından başlayarak
kapsama ağacına eklenmiş her nokta için
(baştan sona doğru) tekrarla:
{
Noktanın komşularının her biri için tekrarla:
{
Eğer komşu nokta daha önceden ağaca eklenmemiş ise:
{
Bu nokta ve komşu nokta arasındaki bağlantıyı
ve komşu noktayı kapsama ağacına ekle.
}
}
}
Genişlik öncelikli aramada kapsama ağacına eklenen noktalar eklenme sırasına göre dikkate alınmalıdırlar. Bu yukarıdaki açıklamalarımızdan da anlaşılmış olmalıdır: Başlangıç noktası önce en yakın komşularına bağlanır, onlar da daha önceden ağaca eklenmemiş en yakın komşularına bağlanarak kapsama ağacı büyütülür. Demek oluyor ki bu tür bir algoritmada kapsama ağacına eklenen noktalar bir liste ve kuyruk oluşturmalı, baştan sona doğru işleme konmalıdırlar.
Derinlik öncelikli arama yoluyla kapsama ağacı oluşturulması ise aşağıdaki gibi tarif edilebilir:
Başlangıç noktasından başlayarak
kapsama ağacına eklenmiş her nokta için
(sondan başa doğru) tekrarla:
{
Noktanın komşularının her biri için tekrarla:
{
Eğer komşu nokta daha önceden ağaca eklenmemiş ise:
{
Bu nokta ve komşu nokta arasındaki bağlantıyı
kapsama ağacına ekle. Komşu noktalar döngüsünden çık.
}
}
}
Okuyucularımız derinlik öncelikli aramada daha önceden kapsama ağacına eklenmemiş noktalar buldukça ağacı büyüttüğümüzü, başka yeni bulamadığımızda bir önce eklenmiş noktaya geri dönüp daha önceden erişilmemiş başka noktalar aradığımızı hatırlarlarsa neden ilk döngünün sondan başa doğru gitmesi gerektiğini anlayacaklardır. Bu tür bir algoritmanın uygulamasında kapsama ağacına eklenen noktalar bir yığın oluşturmalıdır ki başarısız lık durumunda son eklenen noktadan bir önce eklenen noktaya, yine başarısız durumunda iki adım önce eklenmiş noktaya, … dönülsün.
En Az Ağırlıklı Kapsama Ağacı Oluşturulması
Ağırlıklı bir ağ üzerinde oluşturulacak bir kapsama ağacının bağlantı sayısı bakımından en kısa yollardan oluşmasından çok, toplam ağırlıkları minimum olan bağlantılardan oluşması daha önemli olabilir. Bu koşulu sağlayan bir kapsama ağacına “en az ağırlıklı kapsama ağacı” (least-weighted spanning tree), veya basitçe “minimum kapsama ağacı” (minimum spanning tree) denir. Bir minimum kapsama ağacı ayrık bağlantılarla bağlayarak veya birbirlerini izleyen bağlantıları seçerek iki değişik şekilde oluşturulabilir. Bu iki değişil yönteme dayalı algoritmalar ilk kullananların adlarıyla anılmaktadır:
Kruskal’ın Algoritması
Bu algoritma, ağ yapısındaki en düşük ağırlıklı bağlantıları ekleyerek işe başlar; ilk adımlarda seçilen bağlantılar ayrık olabilirler (bkz. Şekil 6‑9; bu şekilde kapsama ağacına eklenmemiş bağlantyılar kesikli çizgilerle, eklenmiş olanlar kalın kesiksiz çizgilerle temsil ediliyorlar). Bağlantılar seçilirken halka oluşturacak olanlar ağırlıkları henüz seçilmemiş bağlantılardan daha düşük ağırlıklara sahip olsalar bile dikkate alınmazlar. Şekil 6‑9’daki A-J bağlantısı işte bu nedenle kapsama ağacında yer bulamamıştır. Bu şekildeki minimum kapsama ağacının oluşturulmasındaki her adım tek tek gösterilmemiştir, ama bağlantıların hangi sırayla eklendiğini anlamak kolaydır. Sonuçta elde edilen kapsama ağacındaki bağlantıların toplam ağırlığı 5 + 7 + 9 + 11 + 13 + 15 + 17 + 17 + 18 + 21 + 33 = 166’dır. Dikkat çekici bir nokta minimum kapsama ağacının Şekil 6‑7’de genişlik öncelikli aramayla elde dilen kapsama ağacıyla aynı olmamasıdır.
Bu algoritmanın yazılı ifadelere dayalı bir kod örneği aşağıdaki gibi olacaktır:
Ağ bağlantılarını küçükten büyüğe ağırlık sırasıyla listeye sok.
Bağlantılar listesi elemanları için sırayla tekrarla:
{
Bağlantı kapsama ağacında halka oluşturmayacak ise:
{
Bağlantıyı kapsama ağacına ekle
}
}
Tabi tüm ağ bağlantılarının incelenmesine gerek yoktur. Kapsama ağacı ağın tüm noktalarına eriştiği an ağırlığa göre sıralanmış bağlantılar listesini tarayan döngüden çıkılabilir.
Şekil 6‑9 Kruskal’ın algoritmasıyla bir minimum kapsama ağacı oluşturulması
Prim’in Algoritması
Prim algoritması ağ yapısındaki belli bir noktadan başlar ve her defasında daha önceden bulunmamış en düşük ağırlıklı bağlantıyı ekleyerek devam eder. Kruskal’ın algoritmasında olduğu gibi daha önceden erişilmiş noktalara giden bağlantılar gözardı edilerek halkalar oluşması engellenir, ama ondan farklı olarak ayrık bağlantılar kabul edilmez. Prim’in algoritması her adımda daha önceden erişilmiş noktalardan çıkan bağlantıları ekleyerek ilerler.
Şekil 6‑10, daha önce Kruskal’ın algoritmasını uyguladığımız ağırlıklı ağ üzerinde Prim’in algoritmasının uygulanışını gösteriyor. Bu şekilde de her adım gösterilmemiştir, hangi bağlantıların hangi sırayla eklendiklerini anlamak zor değildir. Temel prensip seçilen başlangıç noktasını (kapsama ağacının kök elemanını) bir başka noktaya bağlayan en düşük ağırlıklı bağlantıyı seçerek başlamak, ve her adımda o zamana kadar erişilmiş noktalardan birini henüz erişilmemiş bir noktaya bağlayan en düşük ağırlıklı bağlantıyı seçmektir. Bu algoritmayla elde edilen minimum kapsama ağacının Kruskal algoritmasından elde edilenle aynı olması ilginçtir. Okuyucularımız belki kendi tasarladıkları ağlar üzerinde iki algoritmayı deneyip biraz mantık yürüterek bu iki algoritmanın her ağ üzerinde aynı kapsama ağacıyla sonuçlanıp sonuçlanmayacağını anlamaya çalışmalıdırlar.
Bu algoritmanın yazılı ifadelere dayalı bir kod örneği aşağıdaki gibi olacaktır:
Başlangıç noktasını kapsama ağacına ekle
Tekrarla:
{
Kapsama ağacındaki noktaların bağlantıları arasındaki
en düşük ağırlıklı bağlantıyı bul
Eğer bu bağlantı ağacın erişmediği bir noktaya bağlı ise
{
Bu bağlantıyı ve eriştiği noktayı kapsama ağacına ekle.
}
Bu bağlantıyı bir daha dikkkate alma.
}
Bu algoritmaya dayalı bir programın sonsuz döngüye girmemesi için dikkate alınmış bağlantıların bir daha dikkate alınmamaları önemlidir. Bunu başarmanın bir yolu kapsama ağacına ne zaman yeni bir nokta eklense o noktanın komşularına olan bağlantılarını ileride dikkate alınmak üzere bir listeye sokmaktır. Bu listeden her adımda seçilen en düşük ağırlıklı bağlantı listeden çıkartılır ve böylece bir daha dikkate alınmaz. Dikkate alınan bir bağlantı ağaca eklenmiş olsa da olmasa da her adımda dikkate alınacak bağlantılar listesinin en başına dönülüp yeniden en düşük ağırlıklı bir bağlantı aranmalıdır. Okuyucularımız ellerinden geldiği kadar bu algoritmanın bir analizini yapıp ağaca yeni eklenen her nokta için dikkate alınacak bağlantılar listesine eklenen komşu bağlantılarını sıralayarak sokmanın bir fayda sağlayıp sağlamayacağını araştırmalıdırlar.
Tabi bir de şu var ki yukarıdaki kod örneğimizdeki döngü sınır veya bitiş koşulu verilmediği için aslında bir sonsuz döngüdür. Ağdaki tüm noktalar kapsama ağacına eklendiği an döngüden çıkılması için gerekli önlemler alınmalıdır.
Şekil 6‑10 Prim’in algoritmasıyla bir minimum kapsama ağacı oluşturulması
Minimum Kapsama Ağacı Algoritmalarının Programlara Uyarlanması
Çizili bir ağ üzerinde elle uygulandığı zaman Kruskal veya Prim algoritmalarının anlaşılmayacak bir yanı yoktur. Uygulayıcı insan görsel yetenekleri yardımıyla kapsama ağacına eklemek için incelediği bir bağlantının halka oluşturup oluşturmayacağını kolaylıkla anlar. Ama görsel yetenekleri olmayan bir bilgisayar için bir bağlantının halka oluşturup oluşturmadığını kontrol etmek özel işlemler gerektirebilir. Bu açıdan bakıldığında, Prim’in algoritmasını bir bilgisayar programına uyarlamak daha kolaydır. Prim’in belli bir bağlangıç noktasından gidip hep daha önceden erişilmiş noktalardan çıkan bağlantıları dikkate alarak ilerlediği için, Kod Örneği 9‑7’de gösterildiği gibi dikkate alınan bir bağlantının halka oluşturup oluşturmadığını anlamak için birbirine bağladığı noktalara daha önce erişlmiş mi diye bakmak yeterlidir. Bağlantının iki uç noktası da kapsama ağacında mevcut ise onlar birbiriyle zaten dolaylı olarak bağlantılıdır; onları doğrudan bağlamak kesinlikle bir halka oluşturur. Bu basit koşulu uygulamak son derece mantıklı bir çözüm gibi gözüktüğü için Kod Örneği 9‑8’de Kruskal algoritmasını uyarlarken de aynı yolu seçtik. Ama dikkatli düşünecek olan okuyucularımız Kruskal’ın algoritması söz konusu olduğunda bunun doğru bir yol olmadığını anlayacaklardır.
En Kısa Yollar (Shortest Paths) Problemi
Şekil 6‑10’da Prim’in algoritmasıyla elde edilmiş olan minimum kapsama ağacı B noktasından başlanarak elde edilmiştir ama bu noktayı diğer her noktayı en kısa yoldan bağlamamıştır. Örneğin, B’den G’ye C’den geçerek giden yolun toplam ağırlığı 29 olduğu halde, minimum kapsama ağacı bizi B’den G’ye götürürken F, E, D ve C noktalarından geçiriyor ki bu yolun toplam maliyeti 54’dür! Peki biz B noktasını diğer her noktaya en kısa yoldan bağlayacak bir ağ oluşturmak isteseydik nasıl bir yol izlerdik?
Djikstra’nın algoritması bu problemi çözmemizi sağlar. Bu algoritma izlenecek yolları oluşturacak bağlantıları seçmeden önce başlangıç noktasından diğer şehirlere erişebilecek yolların toplam ağırlıklarına bakar, ve ne zaman ki bir noktayı başlangıç noktasına bağlayacak en kısa yolu bulur, o zaman o yolu ulaşım ağına ekler. Şekil 6‑10’daki ağ üzerinde B noktasını diğer noktalara en kısa yoldan bağlayan ulaşım ağı aşağıdaki şekilde gösterilmiştir.
Şekil 6‑11 B noktasını başlangıç alarak Djikstra’nın algoritmasıyla
elde edilmiş en kısa ulaşım ağı
Djikstra algoritması aslında genişlik öncelikli aramaya dayalıdır. B noktası önce en yakın komşularına bağlanır. Bu bağlantıların ağırlıkları eğer bağlantı uzunluklarına karşılık geliyorsa bu ilk aşamada B noktasının komşuları olan C, F ve A’nın B’ye olan uzaklıkları bulunmuş olur. Bu uzaklıklar her noktanın yanında parantezler içinde belirtilmiştir. Daha sonra B’nin komşularının komşularına giden bağlantılar incelenir. Eklenen her bağlantıdan sonra son erişilen noktalara giden bağlantı uzunlukları toplanarak bu noktaların başlangıç noktasına olan uzaklıkları belirlenir. Bu algoritmanın sıradan bir genişlik öncelikli aramadan farklı yanı bağlantılar eklenirken izlenen kuralın farklılığıdır. Genişlik öncelikli arama yoluyla bir kapsama ağacı oluşturulurken yeni eklenecek olan bir bağlantı halka oluşturacaksa hiç eklenmez. Djikstra algoritmasında ise daha önceden ağaca eklenmiş bnoktalara erişiyor oldukları için halka oluşturacak bağlantılar bile dikkate alınır. Dikkate alınan bir bağlantı başlangıç noktasını önceden erişilmiş bir noktaya daha kısa bir yoldan bağlıyorsa o zaman ağaca o eklenir ve daha önceden o noktaya erişmiş olan bağlantı ağaçtan çıkartılır.
Şekil 6‑11’deki kapsama ağacının oluşturulması adım adım gösterilseydi bile önceden eklenmiş bağlantıların çıkartıldığı bir durum görülmeyecekti; bağlantı uzunluklarının seçilen değerleri nedeniyle sıradan genişlik öncelikli arama algoritması zaten en kısa bağlantıları sağlayan bir ağaçla sonuçlanmıştır. Ama bağlantı uzunluklarının farklı seçildiği aşağıdaki ağda Djikstra algoritması adım adım uygulanırken önceden eklenmiş bazı bağlantılar belli noktaları başlangıç noktasına daha uzun yollardan bağladıkları için kapsama ağacından çıkartılmıştır. Çıkartılan bağlantılar kalın, ama kesikli çizgilerle gösterilmişlerdir.
