Grafik Veri Yapısı ve Algorithms (Misal)
Sarah Chen
Veri Yapısında Grafik Nedir?
Grafik, köşelerden ve kenarlardan oluşan, köşelerin bilgi veya veriyi içerdiği ve kenarların köşe çifti arasında bir bağlantı görevi gördüğü doğrusal olmayan bir veri yapısıdır.
Hedef konuma giden en iyi rotayı ve telekomünikasyon ve sosyal ağlar için rotayı bulma gibi gerçek sözlü problemleri çözmek için kullanılır. Kullanıcılar Grafikte bir düğüm olarak kabul edilir ve teller kullanıcıları birbirine bağlayan kenarlardır.
Kenarlar E olarak ve köşeler V olarak temsil edilirse, G grafiği köşeler ve kenarlar kümesi olarak yazılabilir, örneğin: G (V, E)
Veri Yapısındaki Grafik Örneği
Grafik veri yapısının basit bir örneğini burada bulabilirsiniz:
Bu basit, yönlendirilmemiş bir grafiktir (bir tür Grafik). Burada köşe kümesi şöyledir: {A, B, C,D,E,F}. İki köşe bir kenar oluşturur. Örneğin A ve B bir kenarla bağlantılıdır. Ancak A ve F herhangi bir kenarla bağlantılı değildir.
Veri Yapısında Grafik Terminolojileri
Grafik veri yapısında kullanılan bazı önemli terimler şunlardır:
| Dönem | Açıklama |
|---|---|
| Tepe | Tüm veri öğelerine köşe veya düğüm adı verilir. Yukarıdaki görüntüde A, B, C, D ve E köşelerdir. |
| Kenar (Yay) | İki düğüm veya köşe arasındaki bağlantılara kenar (Yay) adı verilir. İki ucu vardır ve (startingVertex, endVertex) olarak temsil edilir. |
| Yönlendirilmemiş Kenar | Çift yönlü bir kenardır. |
| Yönlendirilmiş Kenar | Tek yönlü bir kenardır. |
| Ağırlıklı Kenar | Değeri olan bir avantaj. |
| derece | Grafikte bir köşeye bağlı kenarların sayısına derece denir. |
| Lisans | Bir tepe noktasına bağlanan gelen kenarların toplam sayısı. |
| Yüksek Derece | Bir tepe noktasına bağlı giden kenarların toplam sayısı. |
| Kendi kendine döngü | Bir kenar, iki uç noktası çakışıyorsa kendi kendine döngü olarak adlandırılır. |
| komşuluk | Bir kenar bağlıysa köşelerin bitişik olduğu söylenir. |
Veri Yapısındaki Grafik Türleri
İşte en yaygın olanların listesi veri yapısındaki grafik türleri:
- Yönlendirilmiş grafik
- Yönsüz Grafik
- Ağırlıklı Grafik
- Çift Yönlü Grafik
- Sonsuz Grafik
- Boş Grafik
- Önemsiz Grafik
- Çoklu Grafik
- Grafiği Tamamla
- Bağlı Grafik
- Döngüsel Grafik
- Yönlendirilmiş Asiklik Grafik (DAG)
- Döngü Grafiği
- İki Parçalı Grafik
- Euler Grafiği
- Hamilton Grafiği
Grafik Veri Yapısının Uygulamaları
Bir grafiğin birçok kullanım durumu vardır. Grafikleri çok kullanan birçok algoritma var. İşte Grafiğin bazı uygulamaları:
- Google Haritalar, iki yolun kesişim noktasını bulmak ve iki konum arasındaki mesafeyi hesaplamak için grafikler kullanır.
Örneğin, DijkstraKaynak ve hedef konum arasındaki en kısa mesafeyi bulmak için. - Facebook, kullanıcıların ortak arkadaşlarını bulmak için Grafikleri kullanıyor. Algoritması her kullanıcıyı bir grafiğin düğümü olarak görür.
- Kaynak tahsisi için DAG (Doğrudan Asiklik Grafik) kullanılır. Kaynakların bağımlılığını kontrol eder.
- Google Arama Motoru, web sitelerinin sıralamasını oluşturmak için grafikler kullanır.
- Bir haritalama cihazı grafik veri yapısını kullanır.
- yönlendirici ve t'nin protokolü, hedef yolun yolunu öğrenmek için Grafiği kullanır.
