Node’lardan ve bu node’lar arasındaki ilişkiyi gösteren kenarlardan oluşan doğrusal olmayan veri yapısana graph (çizge) denilmektedir.
Graph veri yapısıyla ilgili bilmemiz gereken kavramlar:
- Vertex (Node): Verilerin tutulduğu graph’ın her bir elemanıdır. Ağaçlarda bu yapı node ismini alırken graph’larda ise genellikle vertex ismi tercih edilmektedir.
- Edge (Kenar): Vertex’lerin birbirleriyle ilişkisini gösteren, vertex’lerin arasında bulunan yapılardır.
- Adjacent (Komşu): Bir vertex’in bağlı olduğu vertex veya vertex’lerdir.
- Derece (Degree): Bir vertex’in bağlı olduğu vertex sayısıdır.
Graph’ları yönlü ve yönsüz graph olmak üzere iki gruba ayırabiliriz.
Directed Graph (Yönlü Graph)
Kenarlarının bir vertex’den diğerine yönlendirildiği graph’lardır.
Undirected Graph (Yönsüz Graph)
Kenarlarının yönlendirilmediği graph’lardır. İki vertex arasındaki bağlantı çift yönlüdür.
Adjacency (Komşuluk)
Yönsüz graph’larda, bir kenarla doğrudan bağlantılı olan iki vertex birbirinin komşusudur. Yönlü graphlar’da ise bir vertex’in ok ile işaret ettiği graph, kendisinin komşusu iken; işaret edilen vertex’in komşusu, işaret eden vertex değildir.
Komşusu olan vertex’e 1, olmayan vertex’e 0 yazarak bir graph’ın komşularını komşuluk matrisi ile gösterebiliriz.
Aşağıda sırasıyla yönlü ve yönsüz birer graph için komşuluk matrisi oluşturulmuştur.
