Grafik geçişi - Graph traversal
|
Grafik ve ağaç arama algoritmaları |
|---|
| Listeler |
| İlgili konular |
Olarak bilgisayar biliminin , grafik geçişi (aynı zamanda grafik arama ) bir, her köşe ziyaret (kontrol ve / veya güncellenmesi) sürecine işaret eder grafik . Bu tür geçişler, köşelerin ziyaret edildiği sıraya göre sınıflandırılır. Ağaç geçişi , grafik geçişinin özel bir durumudur.
artıklık
Ağaç geçişinden farklı olarak, grafik geçişi, bazı köşelerin bir kereden fazla ziyaret edilmesini gerektirebilir, çünkü bir tepe noktasına geçişten önce zaten keşfedilmiş olduğu bilinmeyebilir. Grafikler daha yoğun hale geldikçe, bu fazlalık daha yaygın hale gelir ve hesaplama süresinin artmasına neden olur; grafikler daha seyrek hale geldikçe, bunun tersi geçerlidir.
Bu nedenle, genellikle hangi köşelerin algoritma tarafından keşfedildiğini hatırlamak gerekir, böylece köşeler mümkün olduğunca seyrek tekrar ziyaret edilir (veya en kötü durumda, geçişin süresiz olarak devam etmesini önlemek için). Bu, geçiş sırasında grafiğin her bir köşesini bir "renk" veya "ziyaret" durumuyla ilişkilendirerek gerçekleştirilebilir, bu daha sonra algoritma her bir köşeyi ziyaret ettikçe kontrol edilir ve güncellenir. Köşe zaten ziyaret edilmişse, yok sayılır ve yol daha fazla izlenmez; aksi takdirde, algoritma tepe noktasını kontrol eder/günceller ve mevcut yolunda devam eder.
Birkaç özel grafik durumu, yapılarındaki diğer köşelerin ziyaretini ima eder ve bu nedenle, geçiş sırasında ziyaretin açıkça kaydedilmesini gerektirmez. Bunun önemli bir örneği bir ağaçtır: bir geçiş sırasında mevcut tepe noktasının (ve algoritmaya bağlı olarak diğerlerinin) tüm "ata" köşelerinin zaten ziyaret edilmiş olduğu varsayılabilir. Hem derinliği ilk ve genişliği birinci grafik arama yapısal belirlenen "kök" tepe olmaması ve tarama en ziyaret durumunu kaydetmek için, bir veri yapısı ilavesiyle öncelikli olarak ayırt ağaç tabanlı algoritmalar uyarlamalar vardır.
Grafik geçiş algoritmaları
Not. — Bir grafikteki her tepe noktası, ağaç tabanlı bir algoritma (DFS veya BFS gibi) tarafından geçilecekse, algoritma , grafiğin her bağlı bileşeni için en az bir kez çağrılmalıdır . Bu, grafiğin tüm köşeleri boyunca yineleme yaparak, algoritmayı incelendiğinde hala ziyaret edilmeyen her köşede gerçekleştirerek kolayca gerçekleştirilir.
Derinlik öncelikli arama
Derinlik öncelikli arama (DFS), sonlu bir grafiğin üzerinden geçmek için kullanılan bir algoritmadır. DFS, kardeş köşeleri ziyaret etmeden önce alt köşeleri ziyaret eder; yani, genişliğini keşfetmeden önce herhangi bir belirli yolun derinliğini kateder. Algoritmayı uygularken genellikle bir yığın (genellikle programın özyineleme yoluyla çağrı yığını ) kullanılır.
Algoritma, seçilen bir "kök" tepe noktası ile başlar; daha sonra, mevcut konumundan geçiş yapmak için keşfedilmemiş bir tepe noktası bulana kadar mevcut tepe noktasından bitişik, ziyaret edilmemiş bir tepe noktasına yinelemeli olarak geçiş yapar. Algoritma daha sonra daha önce ziyaret edilen köşeler boyunca geri döner ve daha haritalanmamış bölgeye bağlı bir köşe bulana kadar. Daha sonra, daha önce olduğu gibi yeni yolda ilerleyecek, çıkmaz noktalarla karşılaştığında geri dönecek ve yalnızca algoritma ilk adımdan itibaren orijinal "kök" tepe noktasını geçmiş olduğunda sona erecektir.
DFS, topolojik sıralamalar ve düzlemsellik testi de dahil olmak üzere, grafikle ilgili birçok algoritmanın temelidir .
sözde kod
- Giriş : bir grafik G ve bir köşe V bölgesinin G .
- Çıktı : v'nin bağlı bileşenindeki kenarların keşif kenarları ve arka kenarlar olarak etiketlenmesi .
procedure DFS(G, v) is
label v as explored
for all edges e in G.incidentEdges(v) do
if edge e is unexplored then
w ← G.adjacentVertex(v, e)
if vertex w is unexplored then
label e as a discovered edge
recursively call DFS(G, w)
else
label e as a back edge
Genişlik öncelikli arama
Genişlik öncelikli arama (BFS), sonlu bir grafiğin üzerinden geçmek için başka bir tekniktir. BFS, alt köşeleri ziyaret etmeden önce kardeş köşeleri ziyaret eder ve arama sürecinde bir kuyruk kullanılır. Bu algoritma genellikle bir tepe noktasından diğerine en kısa yolu bulmak için kullanılır.
sözde kod
- Giriş : bir grafik G ve bir köşe V bölgesinin G .
- Çıktı : Bazı koşulları sağlayan v'ye en yakın tepe noktası veya böyle bir tepe noktası yoksa null.
procedure BFS(G, v) is
create a queue Q
enqueue v onto Q
mark v
while Q is not empty do
w ← Q.dequeue()
if w is what we are looking for then
return w
for all edges e in G.adjacentEdges(w) do
x ← G.adjacentVertex(w, e)
if x is not marked then
mark x
enqueue x onto Q
return null
Uygulamalar
Genişlik öncelikli arama, grafik teorisindeki birçok sorunu çözmek için kullanılabilir, örneğin:
- tek bir bağlantılı bileşen içindeki tüm köşeleri bulma ;
- Cheney'nin algoritması ;
- iki köşe arasındaki en kısa yolu bulma ;
- iki taraflılık için bir grafiğin test edilmesi ;
- Cuthill–McKee algoritması ağ numaralandırması;
- Bir akış ağındaki maksimum akışı hesaplamak için Ford-Fulkerson algoritması ;
- bir ikili ağacın seri hale getirilmesi/seri hale getirilmesi ve sıralı sırada seri hale getirilmesi (ağacın verimli bir şekilde yeniden oluşturulmasına izin verir);
- labirent oluşturma algoritmaları ;
- iki boyutlu bir görüntünün veya n-boyutlu dizinin bitişik bölgelerini işaretlemek için taşkın doldurma algoritması;
- ağların ve ilişkilerin analizi.
Grafik keşfi
Grafik keşfi sorunu, grafik geçişinin bir çeşidi olarak görülebilir. Bu bir olan çevrimiçi sorun grafiği hakkında bilgiler yalnızca algoritmanın çalışma zamanı sırasında ortaya anlamına. Ortak bir model aşağıdaki gibidir: Negatif olmayan kenar ağırlıkları ile bağlantılı bir grafik G = ( V , E ) verildiğinde . Algoritma bir tepe noktasında başlar ve tüm olay giden kenarları ve bu kenarların sonundaki tepe noktalarını bilir - ama daha fazlasını değil. Yeni bir köşe ziyaret edildiğinde, yine tüm olay giden kenarlar ve sondaki köşeler bilinir. Amaç, tüm n köşelerini ziyaret etmek ve başlangıç köşesine geri dönmektir, ancak turun ağırlıklarının toplamı mümkün olduğunca küçük olmalıdır. Problem aynı zamanda satıcının grafiği hareket halindeyken keşfetmesi gereken gezgin satıcı probleminin özel bir versiyonu olarak da anlaşılabilir .
Genel grafikler için, hem yönlendirilmemiş hem de yönlendirilmiş grafikler için en iyi bilinen algoritmalar basit bir açgözlü algoritmadır :
- Yönlendirilmemiş durumda, açgözlü tur, optimal bir turdan en fazla O (ln n ) - kat daha uzundur. Herhangi bir deterministik çevrimiçi algoritma için bilinen en iyi alt sınır 10/3'tür.
- Birim ağırlıklı yönsüz grafikler , zaten Tadpole grafiklerinde sıkı bir sınır olan 2 − ε'lik rekabetçi bir oran ile keşfedilebilir .
- Yönlendirilmiş durumda, açgözlü tur, optimal bir turdan en fazla ( n - 1 ) kat daha uzundur. Bu, n − 1'in alt sınırıyla eşleşir . Ω ( n )' nin benzer bir rekabetçi alt sınırı, geometrik bir yerleştirmede her bir düğümün koordinatlarını bilen rastgele algoritmalar için de geçerlidir. Tüm düğümleri ziyaret etmek yerine yalnızca tek bir "hazine" düğümünün bulunması gerekiyorsa, rekabetçi sınırlar, hem deterministik hem de rastgele algoritmalar için birim ağırlığa yönelik grafiklerde Θ ( n 2 ) olur.
Evrensel geçiş dizileri
Bir üniversal geçişi sekansı herhangi bir grafiktir geçişi içeren bir talimatlar dizisidir Normal grafikte köşe bir dizi numarası ile herhangi bir başlangıç tepe için. Aleliunas ve diğerleri tarafından bir olasılıksal kanıt kullanılmıştır. n köşeli herhangi bir düzenli grafik için O ( n 5 ) ile orantılı komut sayısı ile evrensel bir geçiş dizisinin olduğunu göstermek için . Sırada belirtilen adımlar, mutlak değil, geçerli düğüme göredir. Düğüm ise, örneğin, v j ve v j sahip d komşu, o zaman geçişi sekansı ziyaret yanında düğümü belirleyecektir v j + 1 olarak, I inci komşu V j , burada 1 ≤ i ≤ d .