Komşuluk Listesi ve Grafiğin Matris Gösterimi
Sarah Chen
Her ne kadar farklı görünseler de hepsi grafik türleri benzer şekilde temsil edilebilir. Genellikle iki tür Grafik Gösterimi vardır:
- Bitişiklik Matrisi
- Komşuluk Listesi
Komşuluk Listesi
Bitişiklik Listesi Bağlantılı Listelerden oluşur. Her köşe bir dizi dizini olarak kabul edilir ve her öğe bağlantılı bir listeyi temsil eder. Bu bağlantılı listeler, indeks köşe noktasıyla kenarları olan köşe noktalarını içerir.
Aşağıda bir bitişiklik listesi örneği verilmiştir:
Diyelim ki bir grafik V sayıda köşe ve E sayıda kenar içeriyor.
Genel olarak, uzay karmaşıklığı şu şekilde olacaktır: O(V + E).
En kötü durumda uzay karmaşıklığı şu şekilde olacaktır: O(V2) Verilen Grafik tam Grafik ise
Bitişiklik Matrisi
Bitişiklik Matrisi 2 boyutlu bir diziden oluşur. V sayıda köşeye sahip olan grafikte matrisin boyutu şöyle olacaktır: VxV.
Söylemek, matrix[i][j] = 5. Bu, i ve j düğümleri arasında ağırlığın 5 olduğu bir kenar olduğu anlamına gelir.
Aşağıdaki Grafiğe ve onun Komşuluk matrisine bakalım:
Biz yarattık 2 boyutlu dizi bu adımları kullanarak:
) 1 Adım A köşesinin B ile direkt kenarı vardır ve ağırlığı 5'tir. Yani A satırındaki ve B sütunundaki hücre 5 ile doldurulacaktır. A satırındaki hücrelerin geri kalanı sıfırla doldurulacaktır.
) 2 Adım B köşelerinin C ile direkt kenarı vardır ve ağırlıkları 4'tür. Yani B satırı ve C sütunundaki hücre 4 ile doldurulacaktır. B'nin herhangi bir yere giden kenarı olmadığı için B satırındaki kalan hücreler sıfırla doldurulacaktır. diğer düğümler.
) 3 Adım C köşe noktalarının başka herhangi bir köşe ile doğrudan kenarları yoktur. Yani C satırı sıfırlarla doldurulacak.
) 4 Adım Vertice D'nin A ve C ile yönlendirilmiş bir kenarı vardır.
- Burada D satırı ve A sütunundaki hücre 7 değerini alacaktır. D satırı ve C sütunundaki hücreler ise 2 değerini alacaktır.
- D satırındaki hücrelerin geri kalanı sıfırlarla doldurulacaktır.
) 5 Adım E köşe noktalarının B ve D ile yönlendirilmiş bir kenarı vardır. E satırı ve B sütunundaki hücre 6 değerine sahip olacaktır. E satırı ve D sütunundaki hücreler 3 değerine sahip olacaktır. D satırındaki hücrelerin geri kalanı sıfırlarla dolu.
Dikkat edilmesi gereken bazı noktalar şunlardır:
- Bitişiklik matrisinin birincil köşegeni 0 olduğunda Grafiğin kendi kendine döngüsü yoktur.
- (a,b) ve (b,a) indeksleri aynı değere sahip değilse, Grafik yönlendirilmiş bir grafiktir. Aksi takdirde, Grafik yönlendirilmiş bir grafiktir.
- Hücrelerin değeri 1'den büyükse Grafik ağırlıklı bir grafik olacaktır.
Bitişiklik matrisinde kareli boşluklar gerektirdiğinden bazı sorunlar var. Burada bağlı olmayan kenarları saklıyoruz. Bu kenarlar hafızada yer ayırır.
Örneğin 100 düğümlü bir grafiğimiz varsa, onu depolamak için 10 bin hücreye ihtiyaç vardır. RAM. Grafikte daha az kenar olması nedeniyle, bu kadar büyük bir belleğin tahsis edilmesi bir israf olabilir. Bu nedenle, Adjacency matrisini kullanarak alan karmaşıklığı şu şekilde olacaktır: O(N2), burada N, Grafikteki düğüm sayısı anlamına gelir.
