Komşuluk listesi - Adjacency list
İçinde grafik teorisi ve bilgisayar Bilimi, bir bitişiklik listesi sonlu bir değeri temsil etmek için kullanılan sırasız listelerin bir koleksiyonudur grafik. Her liste, bir grubun komşu kümesini açıklar. tepe grafikte. Bu, yaygın olarak kullanılan birkaç temsilinden biridir. grafikler bilgisayar programlarında kullanım için.
Uygulama ayrıntıları
| Yukarıda gösterilen grafik, bu bitişik liste temsiline sahiptir: | ||
| a | bitişiğinde | M.Ö |
| b | bitişiğinde | AC |
| c | bitişiğinde | a, b |
Bir grafiğin bitişik listesi temsili, grafikteki her bir tepe noktasını komşu tepe noktaları veya kenarlarının koleksiyonuyla ilişkilendirir. Köşeler ve koleksiyonlar arasındaki ilişkiyi nasıl uyguladıklarına, koleksiyonları nasıl uyguladıklarına, hem köşeleri hem de kenarları veya yalnızca köşeleri birinci sınıf nesneler olarak dahil edip etmediklerine ve hangi Köşeleri ve kenarları temsil etmek için çeşitli nesneler kullanılır.
- Tarafından önerilen bir uygulama Guido van Rossum kullanır karma tablo bir grafikteki her tepe noktasını bir dizi bitişik köşelerin. Bu gösterimde, bir köşe, herhangi bir hashable nesne ile temsil edilebilir. Nesne olarak kenarların açık bir temsili yoktur.[1]
- Cormen vd. köşelerin dizin numaralarıyla temsil edildiği bir uygulama önerir.[2] Temsillerinde, her köşe için dizi hücresinin bir tek bağlantılı liste bu tepe noktasının komşu köşelerinin. Bu gösterimde, tekil bağlantılı listenin düğümleri, kenar nesneleri olarak yorumlanabilir; ancak, her bir kenar hakkındaki tüm bilgileri saklamazlar (kenarın iki uç noktasından yalnızca birini saklarlar) ve yönlendirilmemiş grafiklerde her kenar için iki farklı bağlantılı liste düğümü olacaktır (her biri için listelerde bir tane) kenarın uç noktaları).
- nesne odaklı Goodrich ve Tamassia tarafından önerilen insidans listesi yapısı, özel köşe nesneleri ve kenar nesneleri sınıflarına sahiptir. Her köşe nesnesinin, komşu kenar nesnelerini listeleyen bir koleksiyon nesnesine işaret eden bir örnek değişkeni vardır. Sırayla, her bir kenar nesnesi, uç noktalarındaki iki tepe nesnesine işaret eder.[3] Bitişiklik listesinin bu sürümü, bitişik köşelerin doğrudan listelendiği sürümden daha fazla bellek kullanır, ancak açık kenar nesnelerinin varlığı, kenarlar hakkında ek bilgilerin depolanmasında ekstra esneklik sağlar.
Operasyonlar
Bitişiklik listesi veri yapısı tarafından gerçekleştirilen ana işlem, belirli bir tepe noktasının komşularının bir listesini rapor etmektir. Yukarıda ayrıntıları verilen uygulamalardan herhangi biri kullanılarak bu, her komşu için sabit zamanda gerçekleştirilebilir. Başka bir deyişle, bir tepe noktasındaki tüm komşuları bildirmek için toplam süre v orantılıdır derece nın-nin v.
Belirtilen iki köşe arasında bir kenarın var olup olmadığını test etmek için bitişiklik listelerini kullanmak da mümkündür, ancak bu kadar verimli değildir. Her bir tepe noktasının komşularının sıralanmamış olduğu bir bitişiklik listesinde, bir kenarın varlığı için test, verilen iki köşenin minimum derecesiyle orantılı olarak, bir sıralı arama bu tepe noktasının komşuları aracılığıyla. Komşular sıralı bir dizi olarak temsil ediliyorsa, Ikili arama bunun yerine, derecenin logaritması ile orantılı zaman alarak kullanılabilir.
Takas
Bitişik listenin ana alternatifi, bitişik matris, bir matris satırları ve sütunları tepe noktaları tarafından indekslenen ve hücreleri, hücrenin satırına ve sütununa karşılık gelen köşeler arasında bir kenar olup olmadığını gösteren bir Boolean değeri içerenler. Bir seyrek grafik (çoğu köşe çiftinin kenarlarla bağlantılı olmadığı) bir bitişik listesi, bitişik bir matristen (iki boyutlu bir dizi olarak depolanır) önemli ölçüde daha fazla alan verimlidir: bitişik listesinin alan kullanımı, sayısıyla orantılıdır. grafikteki kenarlar ve köşeler, bu şekilde depolanan bir bitişik matris için boşluk, köşe sayısının karesiyle orantılıdır. Bununla birlikte, bitişik matrisleri, bir dizi yerine köşe çiftleri tarafından indekslenmiş bir karma tablo kullanarak, bir bitişik listesinin doğrusal uzay kullanımıyla eşleşerek, daha verimli bir şekilde saklamak mümkündür.
Bitişiklik listeleri ile bitişik matrisler arasındaki diğer önemli fark, gerçekleştirdikleri işlemlerin verimliliğidir. Bitişik bir listede, her bir tepe noktasının komşuları, tepe noktasının derecesiyle orantılı olarak zaman içinde verimli bir şekilde listelenebilir. Bir bitişik matrisinde, bu işlem, dereceden önemli ölçüde daha yüksek olabilecek grafikteki tepe noktalarının sayısı ile orantılı olarak zaman alır. Öte yandan, bitişik matris, iki köşenin sabit zamanda birbirine bitişik olup olmadığını test etmeye izin verir; bitişiklik listesi bu işlemi desteklemek için daha yavaştır.
Veri yapıları
Bir veri yapısı olarak kullanmak için, bitişik listesinin ana alternatifi bitişik matrisidir. Bitişik matrisindeki her giriş yalnızca bir bit gerektirdiğinden, çok kompakt bir şekilde temsil edilebilir, yalnızca |V|2/8 bitişik alanın baytları, nerede |V| grafiğin köşe noktası sayısıdır. Boşa harcanan alandan kaçınmanın yanı sıra, bu kompaktlık referans yerelliğini teşvik eder.
Bununla birlikte, seyrek bir grafik için, bitişik listeleri mevcut olmayan kenarları temsil etmek için herhangi bir alan israf etmedikleri için daha az alan gerektirir. 32 bitlik bir bilgisayarda saf bir dizi uygulaması kullanarak, yönsüz bir grafik için bitişiklik listesi, 2·(32/8)|E| = 8|E| bayt boşluk, nerede |E| grafiğin kenar sayısıdır.
Yönlendirilmemiş basit bir grafiğin en fazla (|V|2-|V|)/2 ≈ V 2 kenarlar, döngülere izin verir, izin verebiliriz d = |E|/|V|2 grafiğin yoğunluğunu gösterir. Sonra, 8|E| > |V|2/8 ne zaman |E|/|V|2 > 1/64, yani bitişik liste gösterimi, bitişik matris gösteriminden daha fazla yer kapladığında d > 1/64. Bu nedenle bir grafik, bir bitişik liste temsilini doğrulayacak kadar seyrek olmalıdır.
Uzay değiş tokuşunun yanı sıra, farklı veri yapıları da farklı işlemleri kolaylaştırır. Bir bitişiklik listesindeki belirli bir tepe noktasına bitişik tüm köşeleri bulmak, listeyi okumak kadar basittir. Bir bitişik matris ile, bunun yerine tüm bir satır taranmalıdır; Ö(|V|) zaman. Belirtilen iki köşe arasında bir kenar olup olmadığı, bitişiklik listesiyle iki köşenin minimum derecesiyle orantılı zaman gerektirirken, bir bitişik matris ile aynı anda belirlenebilir.
Referanslar
- ^ Guido van Rossum (1998). "Python Kalıpları - Grafikleri Uygulama".
- ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001). Algoritmalara Giriş, İkinci baskı. MIT Press ve McGraw-Hill. Bölüm 22.1, sayfa 527–529: Grafiklerin gösterimleri. ISBN 0-262-03293-7.
- ^ Michael T. Goodrich ve Roberto Tamassia (2002). Algoritma Tasarımı: Temeller, Analizler ve İnternet Örnekleri. John Wiley & Sons. ISBN 0-471-38365-1.