Graph Nedir?

Bir graf (graph), bir dizi nesneyi ve aralarındaki bağlantıları modelleyen bir veri yapısıdır. Nesnelere köşeler (vertices veya düğümler), bağlantılara ise kenarlar (edges) denir.

Graflar her yerdedir. Sosyal ağlar birer graftır (insanlar köşeler, arkadaşlıklar kenarlardır). Yol haritaları birer graftır (kavşaklar köşeler, sokaklar kenarlardır). İnternet, bağımlılık ağaçları ve oyun haritalarının hepsi birer graftır.

Bu kursta yönsüz (undirected) bir grafa odaklanacağız: Eğer bir kenar u ve v'yi birbirine bağlıyorsa, o zaman v de u'ya bağlıdır. Herhangi bir yön yoktur. İşleri basit tutmak için köşe anahtarları olarak tam sayıları (integers) kullanacağız.

Dahili olarak grafı bir komşuluk listesi (adjacency list) olarak saklayacağız: Her köşeden, o köşenin komşularının listesine giden bir eşleme (map). Bu, çoğu graf algoritmasının ihtiyaç duyduğu şey olan bir köşenin komşularına bakma işlemini tek bir eşleme erişimi haline getirir.

Graph sınıfımız üzerinde oluşturacağımız işlemler şunlardır:

1. addVertex: Henüz kenarı olmayan yeni bir köşe ekler.
2. addEdge: İki köşeyi birbirine bağlar.
3. hasEdge: İki köşenin birbirine bağlı olup olmadığını kontrol eder.
4. getNeighbors: Bir köşenin komşularının listesini alır.
5. removeEdge: İki köşe arasındaki bağlantıyı keser.
6. size: Grafta kaç tane köşe olduğunu sayar.

Hadi bir Graph sınıfı oluşturalım!