Grafik Veri Yapısı ve Algorithms (Misal)
Sarah Chen
⚡ Akıllı Özet
Grafik veri yapısı, her kenarın bir çift düğümü birbirine bağladığı, doğrusal olmayan bir düğüm ve kenar koleksiyonudur. Grafikler, haritalar, sosyal bağlantılar ve web sayfaları gibi gerçek dünya ağlarını modeller ve birçok güçlü algoritmayı destekler.
Veri Yapısında Grafik Nedir?
Grafik, köşelerden ve kenarlardan oluşan doğrusal olmayan bir veri yapısıdır; burada köşeler bilgi veya veri içerir ve kenarlar bir çift köşe arasında bağlantı görevi görür.
Bu grafik, hedef konuma en iyi rotayı bulmak, telekomünikasyon ve sosyal ağlar için rota belirlemek gibi gerçek dünya problemlerini çö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
İşte basit bir grafik veri yapısı örneği:
Bu, basit bir yönsüz grafiktir (grafik türlerinden biri). Burada köşeler kümesi şöyledir: {A, B, C, D, E, F}. İki köşe bir kenar oluşturur. Örneğin, A ve B bir kenarla birbirine bağlıdır. Ancak, A ve F hiçbir kenarla birbirine bağlı değildir.
Veri Yapısında Grafik Terminolojileri
Aşağıda, grafik veri yapısında kullanılan bazı önemli terimler yer almaktadır:
| Dönem | Açıklama |
|---|---|
| Tepe | Her veri öğesine köşe veya düğüm denir. Yukarıdaki resimde A, B, C, D ve E köşelerdir. |
| Kenar (Yay) | İki düğüm veya köşe arasındaki bağlantılara kenar (yay) denir. İki ucu vardır ve (başlangıçKöşesi, bitişKöşesi) şeklinde gösterilir. |
| Yönlendirilmemiş Kenar | Çift yönlü bir kenardır. |
| Yönlendirilmiş Kenar | Tek yönlü bir kenardır. |
| Ağırlıklı Kenar | Üzerinde değer yazılı bir kenar. |
| derece | Bir 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 | Köşeler arasında bir kenar bağlantısı varsa, 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
Bir Grafiği Veri Yapısında Nasıl Gösterebiliriz?
Bir grafik genellikle iki gösterim biçiminden biri kullanılarak bellekte saklanır. Bu seçim, grafiğin ne kadar bellek kullandığını ve yaygın işlemlerin ne kadar hızlı çalıştığını etkiler.
- Komşuluk Matrisi: İki boyutlu V × V dizisi; burada [i][j] hücresi, i ve j düğümleri arasında bir kenar varsa 1 (veya kenar ağırlığı), yoksa 0 değerini alır. O(1) kenar aramasına izin verir ancak O(V²) alan kullanır, bu da onu yoğun grafikler için en uygun hale getirir.
- Komşuluk Listesi: Her bir köşenin komşu köşelerinin listesini sakladığı bir liste dizisi. O(V + E) alan kullanır ve seyrek grafikler için verimlidir; bu nedenle gerçek dünyadaki çoğu grafikte kullanılır.
Bunlar hakkında daha fazla bilgiyi şurada bulabilirsiniz: Bir grafın komşuluk listesi ve matris gösterimi öğretici.
Grafik Veri Yapısının Uygulamaları
Bir grafın birçok kullanım alanı vardır. Graf kullanan birçok algoritma mevcuttur. İşte grafın 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 Grafikler kullanıyor. Algoritması, her kullanıcıyı bir grafiğin düğümü olarak kabul ediyor.
- Kaynak tahsisi için, yönlendirilmiş döngüsel olmayan bir grafik (DAG) kullanılır. Bu grafik, kaynakların bağımlılıklarını kontrol eder.
- MKS Google Arama motorları, web sitelerinin sıralamasını oluşturmak için grafikler kullanır.
- Bir haritaping Cihaz, grafik veri yapısını kullanır.
- A yönlendirici ve protokolü, hedefe giden yolu öğrenmek için Graf'ı kullanır.
