Grafik Veri Yapısı

İçindekiler

Grafik Terminolojisi
Grafik Gösterimi
Grafik İşlemleri

Bu eğitimde, Grafik Veri Yapısının ne olduğunu öğreneceksiniz. Ayrıca, bir grafiğin temsillerini bulacaksınız.

Grafik veri yapısı, veriye sahip ve diğer düğümlere bağlı düğümlerin bir koleksiyonudur.

Bunu bir örnekle anlamaya çalışalım. Facebook'ta her şey bir düğümdür. Buna Kullanıcı, Fotoğraf, Albüm, Etkinlik, Grup, Sayfa, Yorum, Hikaye, Video, Bağlantı, Not dahildir… veriye sahip her şey bir düğümdür.

Her ilişki, bir düğümden diğerine bir uçtur. İster bir fotoğraf yayınlayın, ister bir sayfa gibi bir gruba katılın, vb. Bu ilişki için yeni bir kenar yaratılır.

Grafik veri yapısı örneği

Facebook'un tamamı bu düğümlerin ve kenarların bir koleksiyonudur. Bunun nedeni, facebook'un verilerini depolamak için bir grafik veri yapısı kullanmasıdır.

Daha doğrusu bir grafik, aşağıdakilerden oluşan bir veri yapısıdır (V, E)

V köşelerinden oluşan bir koleksiyon
Sıralı köşe çiftleri (u, v) olarak gösterilen, E kenarlarının bir koleksiyonu

Tepe noktaları ve kenarlar

Grafikte,

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Grafik Terminolojisi

Bitişiklik : Bir tepe noktasının, onları birbirine bağlayan bir kenar varsa, başka bir tepe noktasına bitişik olduğu söylenir. Tepe noktaları 2 ve 3, aralarında kenar olmadığından bitişik değildir.
Yol : A tepe noktasından B tepe noktasına gitmenize izin veren bir dizi kenar, yol olarak adlandırılır. 0-1, 1-2 ve 0-2, köşe 0'dan köşe 2'ye giden yollardır.
Yönlendirilmiş Grafik : Bir kenarın (u, v) mutlaka bir kenar (v, u) olduğu anlamına gelmediği bir grafik. Böyle bir grafikteki kenarlar, kenarın yönünü göstermek için oklarla temsil edilir.

Grafik Gösterimi

Grafikler genellikle iki şekilde temsil edilir:

1. Bitişiklik Matrisi

Bir bitişik matrisi, 2B V x V köşelerinden oluşan bir dizidir. Her satır ve sütun bir tepe noktasını temsil eder.

Herhangi bir elemanın a(i)(j)değeri 1 ise, bu, tepe noktası i ile tepe j'yi birleştiren bir kenar olduğunu gösterir.

Yukarıda oluşturduğumuz grafiğin bitişik matrisi

Grafik bitişik matrisi

Yönsüz bir grafik olduğu için (0,2) kenarı için (2,0) kenarını da işaretlememiz gerekir; bitişik matrisin köşegen etrafında simetrik hale getirilmesi.

Kenar araması (köşe A ve köşe B arasında bir kenar olup olmadığını kontrol etmek) bitişik matris gösteriminde son derece hızlıdır, ancak tüm köşeler (V x V) arasındaki olası her bağlantı için alan ayırmalıyız, bu nedenle daha fazla alan gerektirir.

2. Komşuluk Listesi

Bitişiklik listesi, bağlantılı listeler dizisi olarak bir grafiği temsil eder.

Dizinin indeksi bir tepe noktasını temsil eder ve bağlantılı listesindeki her öğe, tepe ile bir kenar oluşturan diğer tepe noktalarını temsil eder.

İlk örnekte yaptığımız grafiğin bitişiklik listesi aşağıdaki gibidir:

Bitişiklik listesi gösterimi

Bir bitişiklik listesi depolama açısından etkilidir çünkü sadece kenarların değerlerini saklamamız gerekir. Milyonlarca köşesi olan bir grafik için bu, çok fazla tasarruf edilmiş alan anlamına gelebilir.