Komşuluk Listesi ve Grafiğin Matris Gösterimi
Sarah Chen
⚡ Akıllı Özet
Grafın komşuluk listesi ve matris gösterimi, düğümleri ve kenarları bellekte saklayarak algoritmaların ağlarda gezinmesine olanak tanır. Komşuluk listesi, her düğüm için bağlantılı listeler kullanırken, komşuluk matrisi kare şeklinde iki boyutlu bir ızgara kullanır.
Her ne kadar farklı görünseler de hepsi grafik türleri Benzer şekilde temsil edilebilir. Genel olarak iki tür grafik gösterimi vardır:
- Bitişiklik Matrisi
- Komşuluk Listesi
Komşuluk Listesi
Komşuluk listesi, bağlantılı listelerden oluşur. Her köşe bir dizi indeksi olarak kabul edilir ve her eleman bir bağlantılı listeyi temsil eder. Bu bağlantılı listeler, indeks köşesiyle ortak bir kenarı paylaşan köşeleri içerir.
İşte komşuluk listesine bir örnek:
Bir grafın V sayıda köşesi ve E sayıda kenarı olsun. Komşuluk listesinin alan karmaşıklığı nedir? O(V + E)Bu, her olası köşe çifti yerine gerçek kenarların sayısıyla orantılı olarak artar.
En kötü durumdaki alan karmaşıklığı şu hale gelir: O(V²) Verilen grafik tam bir grafik ise, her köşe diğer her köşeye bağlanır.
Bitişiklik Matrisi
Komşuluk matrisi 2 boyutlu bir diziden oluşur. V köşeli bir grafik için matrisin boyutu şu şekilde olacaktır: V × V.
Söylemek matrix[i][j] = 5Bu, i düğümü ile j düğümü arasında ağırlığı 5 olan bir kenar olduğu anlamına gelir.
Şimdi aşağıdaki grafiğe ve komşuluk matrisine bakalım:
Biz inşa ettik 2 boyutlu dizi bu adımları kullanarak:
) 1 Adım A düğümünün B düğümüyle doğrudan bir kenarı vardır ve ağırlığı 5'tir. Bu nedenle, A satırındaki ve B sütunundaki hücreler 5 ile doldurulacaktır. A satırındaki diğer hücreler ise sıfır ile doldurulacaktır.
) 2 Adım B düğümünün C ile doğrudan bir kenarı vardır ve ağırlığı 4'tür. Bu nedenle, B satırındaki ve C sütunundaki hücre 4 ile doldurulacaktır. B'nin başka bir düğüme giden bir kenarı olmadığı için, B satırındaki kalan hücreler sıfır ile doldurulacaktır.
) 3 Adım C düğümünün diğer düğümlerle doğrudan bağlantısı yoktur. Bu nedenle, C satırı sıfırlarla doldurulacaktır.
) 4 Adım D düğümü, A ve C ile yönlendirilmiş bir kenara sahiptir.
- D satırındaki A sütunundaki hücrenin değeri 7 olacaktır. D satırındaki C sütunundaki hücrenin değeri 2 olacaktır.
- D satırındaki hücrelerin geri kalanı sıfırlarla doldurulacaktır.
) 5 Adım E düğümü, B ve D düğümleriyle yönlü bir kenara sahiptir. E satırındaki B sütunundaki hücrenin değeri 6 olacaktır. E satırındaki D sütunundaki hücrenin değeri 3 olacaktır. E satırındaki diğer hücreler sıfırlarla doldurulacaktır.
Dikkat edilmesi gereken bazı noktalar şunlardır:
- Komşuluk matrisinin ana köşegen elemanı 0 olduğunda grafikte kendi kendine döngü bulunmaz.
- Eğer (a, b) ve (b, a) noktalarındaki hücreler aynı değere sahip değilse, grafik yönlü bir grafiktir. Aksi takdirde, grafik yönsüzdür.
- Grafikteki herhangi bir hücrenin değeri 1'den büyükse, grafik ağırlıklı bir grafiktir.
Komşuluk matrisinin temel sorunu, karesel alan gerektirmesidir. Var olmayan kenarlar bile bellekte hücre tahsis eder.
Örneğin, 100 düğümlü bir grafımız varsa, bunu depolamak için 10,000 hücreye ihtiyaç duyulur. RAMGrafikte daha az kenar olduğunda, bu kadar büyük miktarda bellek ayırmak israf olabilir. Dolayısıyla, komşuluk matrisini kullanan alan karmaşıklığı şu şekildedir: O(N²)Burada N, grafikteki düğüm sayısını ifade eder.
Komşuluk Listesi ve Komşuluk Matrisi Arasındaki Fark
Bir gösterim seçmeden önce, her iki modeli de gerçek grafik iş yüklerinde baskın olan işlemler açısından yan yana karşılaştırmak faydalı olacaktır:
| Çalışma | Bitişiklik Matrisi | Komşuluk Listesi |
|---|---|---|
| Alan karmaşıklığı | O(V²) | O(V + E) |
| Bir köşe noktası ekleyin | O(V²) | O (1) |
| Kenar ekleyin | O (1) | O (1) |
| Bir kenarı çıkarın | O (1) | Ç(E) |
| (i, j) kenarının var olup olmadığını kontrol edin. | O (1) | O(i'nin derecesi) |
| i'nin komşuları üzerinde yineleme yapın. | Ç(V) | O(i'nin derecesi) |
| İçin en iyisi | Yoğun grafikler, sık kenar sorguları | Seyrek grafikler, yoğun gezinme gerektiren görevler |
Özetle, komşuluk matrisi sabit zamanlı kenar aramalarında, komşuluk listesi ise bellek ve komşu yinelemelerinde avantajlıdır; bu nedenle BFS, DFS ve Dijkstra gibi algoritmalar genellikle komşuluk listeleriyle birlikte kullanılır.
Grafik Gösteriminin Avantajları ve Dezavantajları
Her bir gösterim biçiminin kendine özgü dezavantajları vardır. Her iki modelin de güçlü ve zayıf yönlerini bilmek, çözmekte olduğunuz problem için doğru olanı seçmenize yardımcı olur.
Komşuluk Matrisinin Avantajları:
- Herhangi iki köşe arasındaki kenar varlığı sorguları sabit zamanlı O(1).
- Sabit indeksleme, Floyd-Warshall ve geçişli kapanma gibi matris tabanlı algoritmaların uygulanmasını kolaylaştırır.
- Ağırlıklı kenarlar, tek bir matris hücresine doğal olarak sığar.
Komşuluk Matrisinin Dezavantajları:
- Grafik seyrek olduğunda O(V²) bellek israfı yapar.
- Yeni bir köşe eklemek, tüm matrisin boyutunun yeniden ayarlanmasını gerektirir.
- Tek bir köşenin komşuları üzerinde yineleme yapmak, köşenin yalnızca birkaç kenarı olsa bile O(V) zaman alır.
Komşuluk Listesinin Avantajları:
- Seyrek grafiklerdeki gerçek kenar sayısına yakın olan yalnızca O(V + E) bellek kullanır.
- Yeni bir köşe veya kenar eklemek O(1) zaman karmaşıklığına sahiptir.
- BFS ve DFS gibi geçiş algoritmaları, komşuları O(derece) sürede yineleyerek toplamda O(V + E) çalışma süresi sağlar.
Komşuluk Listesinin Dezavantajları:
- Belirli bir kenarın var olup olmadığını kontrol etmek, O(1) yerine O(derece) zaman alır.
- Bağlantılı listeler belleğe dağılmış olduğundan önbellek yerelliği daha zayıftır.
- Ağırlıklı kenarlar, bir yardımcı alan veya bir çift listesi gerektirir; bu da veri yapısını biraz karmaşıklaştırır.
Komşuluk Listesi mi Yoksa Komşuluk Matrisi mi Ne Zaman Kullanılmalı?
Grafik gösterim seçimi, grafiğin yoğunluğuna ve en sık çalıştırdığınız işlemlere bağlıdır. Doğru yapıyı seçmek için bu kısa kılavuzu kullanın:
- Komşuluk matrisini tercih edin. Grafik yoğun olduğunda (E, V²'ye yakın olduğunda), kenarlar nadiren değiştiğinde ve algoritmanız "i ve j arasında bir kenar var mı?" sorusunu birçok kez sorduğunda.
- Komşu listeyi tercih edin Grafik seyrek olduğunda (E, V²'den çok daha küçük olduğunda), köşe veya kenar kümesi işlem sırasında büyüdüğünde ve grafiği BFS, DFS veya Dijkstra'nın en kısa yol algoritması.
- Karma bir modeli tercih edin (Komşuluk listesi artı kenarların karma kümesi), hem hızlı komşu yinelemesine hem de O(1) kenar sorgularına ihtiyaç duyduğunuzda, ek bellek maliyeti karşılığında kullanılır.
NetworkX ve igraph gibi modern grafik kütüphaneleri, gerçek dünyadaki grafiklerin çoğunun (sosyal ağlar, yol haritaları, web sayfaları, paket bağımlılıkları) seyrek ve yoğun gezinme gerektirdiği için varsayılan olarak komşuluk listelerini kullanır.
