Herkese Merhaba.
Bu notta, bilgisayar bilimlerinde grafikleri depolamak için kullanılan ana veri yapılarını listelemeye karar verdim ve ayrıca benim için bir şekilde "kristalleşen" bu tür birkaç yapıdan daha bahsedeceğim.
Öyleyse başlayalım. Ama en başından beri değil - sanırım hepimiz bir grafiğin ne olduğunu ve ne olduğunu zaten biliyoruz (yönlendirilmiş, yönlendirilmemiş, ağırlıklı, ağırlıksız, çoklu kenarlar ve döngüler olsun veya olmasın).
O zaman hadi gidelim. "Grafik depolama"ya yönelik veri yapıları için hangi seçeneklere sahibiz?
1. Matris veri yapıları
1.1 Komşuluk matrisi. Bitişiklik matrisi, satır ve sütun başlıklarının grafiğin köşe sayılarına karşılık geldiği ve her bir elemanının değerinin a(i,j) köşeler arasındaki kenarların varlığına veya yokluğuna göre belirlendiği bir matristir. i ve j (yönlendirilmemiş bir grafik için böyle bir matrisin simetrik olacağı açıktır veya tüm değerleri yalnızca ana köşegenin üzerinde sakladığımız konusunda anlaşabiliriz). Ağırlıksız grafikler için a(i,j), i'den j'ye kadar olan kenar sayısına göre (böyle bir kenar yoksa a(i,j)= 0) ve ağırlıklı grafikler için ayrıca ağırlığa göre ayarlanabilir. (toplam ağırlık) bahsedilen kenarların.
1.2 İnsidans matrisi. Bu durumda grafiğimiz, kural olarak satır numaralarının köşe numaralarına ve sütun numaralarının önceden numaralandırılmış kenarlara karşılık geldiği bir tabloda da saklanır. Bir tepe noktası ve bir kenar birbirine denk gelirse, karşılık gelen hücreye sıfırdan farklı bir değer yazılır (yönsüz grafikler için, köşe ve kenar çakışırsa 1 yazılır, yönlendirilmiş grafikler için - kenar ise “1” yazılır) Tepe noktasından "çıkışlar" ve eğer "dahil ediyorsa" "-1" (hatırlaması yeterince kolaydır, çünkü "eksi" işareti aynı zamanda "-1" sayısına "dahil" gibi görünmektedir). Ağırlıklı grafikler için yine 1 ve -1 yerine kenarın toplam ağırlığını belirtebilirsiniz.
2. Numaralandırma veri yapıları
2.1 Yakınlık listesi. Burada her şey basit görünüyor. Grafiğin her köşesi genel olarak herhangi bir numaralandırma yapısıyla (liste, vektör, dizi, ...) ilişkilendirilebilir; bu yapı, verilen köşeye bitişik tüm köşelerin sayılarını saklar. Yönlendirilmiş grafikler için, böyle bir listeye yalnızca bir özellik tepe noktasından "yönlendirilmiş" bir kenarın bulunduğu köşeleri ekleyeceğiz. Ağırlıklı grafikler için uygulama daha karmaşık olacaktır.
2.2 Kaburga listesi. Oldukça popüler bir veri yapısı. Kaptan Açıklık'ın bize söylediği gibi kenarlar listesi aslında grafiğin kenarlarının bir listesidir ve bunların her biri başlangıç köşesi ve bitiş köşesi tarafından belirtilir (yönlendirilmemiş grafikler için sıra burada önemli değildir, ancak birleştirme için şunları yapabilirsiniz: çeşitli kuralları (örneğin, artan sırayla köşeleri belirtmek) ve ağırlığı (yalnızca ağırlıklı grafikler için) kullanın.
Yukarıda listelenen matris listelerine daha ayrıntılı (ve resimlerle birlikte) bakabilirsiniz, örneğin, .
2.3 Bitişiklik dizisi. En yaygın yapı değil. Özünde, bitişik listelerin tek bir numaralandırma yapısında (dizi, vektör) "paketlenmesi" biçimidir. Böyle bir dizinin ilk n (grafiğin köşe sayısına göre) öğeleri, aynı dizinin başlangıç \uXNUMXb\uXNUMXbindekslerini içerir; bu, verilen diziye bitişik tüm köşelerin bir satıra yazıldığı yerden başlar.
Burada (kendim için) en anlaşılır açıklamayı buldum:
3. Bitişiklik Vektörü ve İlişkisel Bitişiklik Dizisi
Bu satırların yazarının profesyonel bir programcı olmadığı, ancak periyodik olarak grafiklerle ilgilenen kişinin çoğunlukla kenar listeleriyle ilgilendiği ortaya çıktı. Aslında grafiğin birden fazla döngüye ve kenara sahip olması uygundur. Ve böylece, klasik kenar listelerinin geliştirilmesinde, bunların "gelişimine/dalına/modifikasyonuna/mutasyonuna", yani bitişiklik vektörüne ve ilişkisel bitişiklik dizisine dikkat etmeyi öneriyorum.
3.1 Komşuluk vektörü
Durum (a1): ağırlıklandırılmamış grafik
Ağırlıksız bir grafik için bitişiklik vektörünü, her bir sayı çiftinin bulunduğu çift sayıdaki tamsayıların (a[2i], a[2i+1],..., i'nin c 0 olarak numaralandırıldığı) sıralı bir kümesi olarak adlandıracağız. a[2i]'dir, a[2i+1 ] sırasıyla a[2i] ve a[2i+1] köşeleri arasındaki bir grafik kenarını belirtir.
Bu kayıt formatı grafiğin yönlendirilip yönlendirilmediğine dair bilgi içermez (her iki seçenek de mümkündür). Digraf formatını kullanırken, kenarın a[2i]'den a[2i+1]'e yönlendirildiği kabul edilir. Burada ve aşağıda: Yönsüz grafikler için gerekirse kayıt köşelerinin sırasına ilişkin gereksinimler uygulanabilir (örneğin, kendisine atanan sayının daha düşük değerine sahip köşenin önce gelmesi).
C++'da std::vector kullanarak bir bitişiklik vektörünün belirtilmesi tavsiye edilir, dolayısıyla bu veri yapısının adı da buradan gelir.
Durum (a2): ağırlıklandırılmamış grafik, kenar ağırlıkları tam sayıdır
(a1) durumuna benzer şekilde, tamsayı kenar ağırlıklarına sahip ağırlıklı bir grafik için bitişiklik vektörünü (a[3i], a[3i+1], a[3i+2]) sıralı bir sayı kümesi (dinamik dizi) olarak adlandırırız. ..., burada i, c 0 olarak numaralandırılmıştır), burada a[3i], a[3i+1], a[3i+2] sayılarının her "üçlü"sü, grafiğin a[3i] olarak numaralandırılmış köşeleri arasındaki bir kenarını belirtir. ve a[3i+1] olup, a [3i+2] değeri bu kenarın ağırlığıdır. Böyle bir grafik de yönlendirilebilir veya yönlendirilmeyebilir.
Durum (b): ağırlıklandırılmamış grafik, tam sayı olmayan kenar ağırlıkları
Heterojen elemanları tek bir dizide (vektör) depolamak imkansız olduğundan, örneğin aşağıdaki uygulama mümkündür. Grafik bir çift vektörde saklanır; burada birinci vektör, ağırlıkları belirtmeden grafiğin bitişiklik vektörüdür ve ikinci vektör karşılık gelen ağırlıkları içerir (C++ için olası uygulama: std::pair) ). Dolayısıyla, birinci vektörün 2i, 2i+1 indeksleri altındaki bir çift köşe tarafından tanımlanan bir kenar için ağırlık, ikinci vektörün i indeksi altındaki elemana eşit olacaktır.
Peki bu neden gerekli?
Bu satırların yazarı, bir dizi sorunu çözmek için bunu oldukça faydalı buldu. Resmi açıdan bakıldığında aşağıdaki avantajlar olacaktır:
- Bitişiklik vektörü, diğer herhangi bir "numaralandırmalı" yapı gibi, oldukça kompakttır, bitişiklik matrisinden (seyrek grafikler için) daha az bellek kaplar ve uygulanması nispeten kolaydır.
- Grafiğin köşeleri prensip olarak negatif sayılarla da işaretlenebilir. Peki ya böyle bir “sapkınlığa” ihtiyaç varsa?
- Grafikler, farklı ağırlıklara (pozitif, negatif, hatta sıfır) sahip birden çok kenar ve birden çok döngü içerebilir. Burada herhangi bir kısıtlama yoktur.
- Kenarlara farklı özellikler de atayabilirsiniz; ancak bunun hakkında daha fazla bilgi için bölüm 4'e bakın.
Ancak bu “listenin” uca hızlı erişim anlamına gelmediğini de kabul etmek gerekir. Ve burada aşağıda tartışılan İlişkisel Bitişiklik Dizisi kurtarmaya geliyor.
3.2 İlişkisel bitişiklik dizisi
Dolayısıyla, belirli bir kenara erişim, onun ağırlığı ve diğer özellikleri bizim için kritikse ve bellek gereksinimleri bitişiklik matrisini kullanmamıza izin vermiyorsa, bu sorunu çözmek için bitişiklik vektörünü nasıl değiştirebileceğimizi düşünelim. Yani anahtar, grafiğin sıralı bir tamsayı çifti olarak belirtilebilen bir kenarıdır. Bu neye benziyor? İlişkisel bir dizideki bir anahtar değil mi? Eğer öyleyse, neden bunu uygulamıyoruz? Her anahtarın (sıralı bir tam sayı çifti) bir değerle (kenarın ağırlığını belirten bir tam sayı veya gerçek sayı) ilişkilendirileceği ilişkisel bir dizimiz olsun. C++'da bu yapının std::map konteynerine (std::map) dayalı olarak uygulanması tavsiye edilir. , int> veya std::map , double>) veya birden fazla kenar bekleniyorsa std::multimap. Grafikleri depolamak için “matris” yapılardan daha az bellek kaplayan, birden fazla döngü ve kenar içeren grafikler tanımlayabilen ve hatta köşe sayılarının negatif olmaması konusunda katı gereksinimleri olmayan bir yapıya sahibiz (bilmiyorum) buna kimin ihtiyacı var ama yine de).
4. Veri yapıları dolu ama bir şeyler eksik
Ve bu doğru: Bir takım problemleri çözerken, grafiğin kenarlarına bazı özellikler atamamız ve buna göre bunları saklamamız gerekebilir. Bu özellikleri açık bir şekilde tam sayılara indirgemek mümkünse, bitişiklik vektörünün ve ilişkisel bitişiklik dizisinin genişletilmiş versiyonlarını kullanarak bu tür "ek özelliklere sahip grafikleri" depolamak mümkündür.
Öyleyse, her kenarı için, örneğin tamsayılarla belirtilen 2 ek özelliği saklamanın gerekli olduğu, ağırlıklandırılmamış bir grafiğimiz olsun. Bu durumda, bitişiklik vektörünü "çiftlerden" değil, tam sayıların "dörtlülerinden" oluşan sıralı bir küme olarak tanımlamak mümkündür (a[2i], a[2i+1], a[2i+2], a) [2i+3]…) , burada a[2i+2] ve a[2i+3] karşılık gelen kenarın özelliklerini belirleyecektir. Kenarların tamsayı ağırlıklarına sahip bir grafik için sıralama genellikle benzerdir (tek fark, niteliklerin kenarın ağırlığını takip etmesi ve a[2i+3] ve a[2i+4] elemanları tarafından belirtilmesidir. ve kenarın kendisi 4 değil 5 sıralı sayı olarak belirtilecektir). Tamsayı olmayan kenar ağırlıklarına sahip bir grafik için özellikler, ağırlıklandırılmamış bileşenine yazılabilir.
Tamsayı kenar ağırlıklarına sahip grafikler için ilişkisel bir bitişiklik dizisi kullanıldığında, değer olarak tek bir sayı değil, bir kenarın ağırlığına ek olarak gerekli diğer tüm değerleri belirten bir sayı dizisini (vektör) belirtmek mümkündür. özellikler. Aynı zamanda, tamsayı olmayan ağırlıklar durumunda, kayan noktalı bir sayı içeren bir işaret belirtme ihtiyacı da bir rahatsızlık olacaktır (evet, bu bir rahatsızlıktır, ancak bu tür işaretler çok fazla değilse ve eğer onları fazla "aldatıcı" hale getirmezseniz hiçbir şey olmayabilir). Bu, C++'ta genişletilmiş ilişkisel bitişiklik dizilerinin şu şekilde tanımlanabileceği anlamına gelir: std::map , std::vector> veya std::map , std::vector, burada "anahtar-değer-vektörü" ndeki ilk değer kenarın ağırlığı olacak ve ardından özelliklerinin sayısal tanımları yer alacaktır.
Referanslar:
Genel olarak grafikler ve algoritmalar hakkında:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmalar: yapı ve analiz, 2. baskı: Çev. İngilizceden – M.: Williams Yayınevi, 2011.
2.Harari Frank. Grafik teorisi. M.: Mir, 1973.
Yazarın aynı vektör ve ilişkisel bitişiklik dizisi hakkındaki raporu:
3. Çernouhov S.A. Grafikleri temsil etme ve saklama yolları olarak bitişiklik vektörü ve ilişkisel bitişiklik dizisi / SA Chernouhov. Bir grafiği temsil edecek veri yapıları olarak bitişiklik vektörü ve bitişiklik haritası // Uluslararası Bilimsel ve Pratik Konferansın makalelerinin toplanması “Yenilikçi gelişmelerin sonuçlarını uygulama sorunları ve bunları çözme yolları” (Saratov, 14.09.2019 Eylül 2019). – Sterlitamak: AMI, 65, s. 69-XNUMX
Konuyla ilgili faydalı çevrimiçi kaynaklar:
4.
5.
Kaynak: habr.com