Grafikler, düğümler (vertices) ve kenarlar (edges) arasındaki ilişkileri modellemek için kullanılan veri yapılarıdır.
Graf Terminolojisi
- Düğüm (Vertex): Grafın temel elemanları
- Kenar (Edge): İki düğüm arasındaki bağlantı
- Yönlü Graf: Kenarların yönü olan graflar
- Yönsüz Graf: Kenarların yönü olmayan graflar
- Ağırlıklı Graf: Kenarların ağırlığı olan graflar
Komşuluk Matrisi
Grafı VxV boyutunda bir matris ile temsil eder. matris[i][j] = 1 ise i ve j arasında kenar vardır.
Avantajları:
- Kenar kontrolü O(1)
- Kenar ekleme/silme O(1)
Dezavantajları:
- O(V²) bellek kullanımı
- Seyrek graflar için verimsiz
Komşuluk Listesi
Her düğüm için komşularının listesini tutar.
Avantajları:
- O(V+E) bellek kullanımı
- Seyrek graflar için verimli
Dezavantajları:
- Kenar kontrolü O(derece(V))