İyi metin çevirisi Grafik veri yapısına giriş
Açık kaynak Çin OSC başlık numarasını takip edin ve en son teknik bilgileri alın
Çeviriye katıldı (4 kişi): xiaoaiwhc1, Tocy, lnovonl, longsi
Bu yazıda, grafikler gibi doğrusal olmayan veri yapılarını keşfedeceğiz. Temel kavramlarını ve tipik uygulamalarını tanıtacağız.
Grafik (ve ağaç) veri yapılarını kullanan bir program kullanıyor olabilirsiniz. Örneğin, iş yeriniz ile eviniz arasındaki en kısa yolu bilmek istiyorsanız, cevabı almak için grafik algoritmasını kullanabilirsiniz! Bunu ve diğer ilginç zorlukları keşfedeceğiz.
Önceki makalede diziler, bağlantılı listeler, koleksiyonlar, yığınlar vb. Gibi doğrusal veri yapılarını inceledik. Bu makale öğrendiklerimize dayanmaktadır.
Bu makale, bu eğitim dizisinin bir parçasıdır:
Yeni başlayanlar için veri yapısı ve algoritma yolu
İşte bu yazıda ele alacağımız işlemlerin bir özeti:
Temel grafik bilgisi
Grafik, düğümlerin sıfır veya daha fazla bitişik öğeye sahip olabileceği bir veri yapısıdır. İki düğüm arasındaki bağlantıya kenar denir. Düğümler ayrıca köşeler olarak da adlandırılabilir.
Derece, tepe ile ilişkili kenarların sayısıdır. Örneğin, mor köşenin derecesi 3 ve mavi köşenin derecesi 1'dir.
Kenarlar çift yönlü ise, yönsüz bir grafiğimiz var. Ancak kenarların yönleri varsa, yönlendirilmiş bir grafiğimiz veya basit bir grafiğimiz var demektir. Bunu tek yönlü (yönlendirilmiş) veya iki yönlü (yönsüz) bir cadde olarak düşünebilirsiniz.
Bir tepe noktası, kendi kendine döngü adı verilen mavi bir tepe gibi kendi etrafında bir kenara sahip olabilir.
Grafiğin döngüleri olabilir, bu, bir düğümü geçmek istiyorsanız, aynı düğümü birden çok kez ziyaret edebileceğiniz anlamına gelir. Döngüsüz bir grafiğe çevrimsiz grafik denir.
Ek olarak, döngüsel olmayan yönsüz grafiklere ağaç denir. Ağacı bir sonraki makalede derinlemesine açıklayacağız.
Grafikte tüm köşelerin birbirine bağlı olması gerekmez. İzole edilmiş düğümler veya hatta ayrı alt grafikler olabilir. Tüm düğümlerin en az bir kenarı varsa, bağlı bir grafiğimiz var. Tüm düğümler diğer tüm düğümlere bağlandığında, tam bir grafiğimiz var.
Tam bir grafik için, her düğümün # düğüm-1 kenarı olmalıdır. Önceki örnekte 7 köşemiz var, bu nedenle her düğümün 6 kenarı var.
