Kruskal Algoritması Labirent Oluşturucu
Yayınlandı: 16 Şubat 2025 18:00:51 UTC
Kruskal algoritmasını kullanarak mükemmel bir labirent oluşturmak için labirent oluşturucu. Bu algoritma, orta uzunlukta koridorlar ve birçok çıkmazın yanı sıra oldukça düz bir çözüme sahip labirentler oluşturma eğilimindedir.Kruskal's Algorithm Maze Generator
Kruskal'ın algoritması, labirent üretimi için uyarlanabilen bir minimum yayılan ağaç algoritmasıdır. Özellikle mükemmel labirentler oluşturmak için etkilidir. Kruskal'ın algoritmasına bir alternatif, aynı zamanda bir minimum yayılan ağaç algoritması olan Prim'in algoritmasıdır, ancak aynı labirentleri ürettikleri ve Kruskal'ın algoritması daha hızlı çalıştığı için Prim'in algoritmasını uygulama zahmetine girmedim.
Mükemmel bir labirent, labirentteki herhangi bir noktadan diğer herhangi bir noktaya tam olarak tek bir yolun olduğu bir labirenttir. Bu, daireler çizerek ilerleyemeyeceğiniz, ancak sık sık çıkmaz sokaklarla karşılaşacağınız ve sizi geri dönmeye zorlayacağınız anlamına gelir.
Burada oluşturulan labirent haritaları, herhangi bir başlangıç ve bitiş konumu olmayan varsayılan bir sürüm içerir, böylece bunlara kendiniz karar verebilirsiniz: labirentin herhangi bir noktasından başka bir noktaya bir çözüm olacaktır. İlham almak isterseniz, önerilen bir başlangıç ve bitiş konumunu etkinleştirebilir ve hatta ikisi arasındaki çözümü görebilirsiniz.
Kruskal Algoritması Hakkında
Kruskal'ın algoritması, Amerikalı bir matematikçi, istatistikçi ve bilgisayar bilimcisi olan Joseph Bernard Kruskal, Jr. tarafından yaratıldı. Algoritmayı ilk olarak 1956'da "Bir Grafiğin En Kısa Kapsayan Alt Ağacı ve Gezgin Satıcı Problemi" adlı makalesinde tanımladı.
Algoritma, döngülerden kaçınarak tüm köşelerin mümkün olan en düşük toplam kenar ağırlığıyla bağlanmasını sağlayarak bir grafiğin minimum yayılan ağacını (MST) bulmak için tasarlanmıştır.
Kruskal Algoritması Labirent Oluşturma İçin Nasıl Çalışır?
Adım 1: Başlatma
- Labirentteki her hücreyi ayrı bir küme (benzersiz bir bileşen) olarak ele alın.
- Komşu hücreler arasındaki tüm duvarları potansiyel kenarlar olarak listeleyin.
Adım 2: Duvarları Sıralayın
- Duvarları karıştırın veya rastgele sıralayın. Bunu gerçek bir Kruskal algoritması olarak uygularsanız, duvarları rastgele bir sıraya göre sıralayın (çünkü labirent oluşturma ağırlık gerektirmez).
Adım 3: Duvarları İşle
- Karıştırılmış duvarların arasından geç.
- Duvarla bölünen iki hücre farklı kümelere aitse (yani labirentte henüz bağlanmamışlarsa), duvarı kaldır ve kümeleri birleştir.
- Eğer aynı sette iseler, döngüleri önlemek için duvarı atlayın.
Adım 4: Tamamlanana Kadar Devam Edin
- Tüm hücreler birbirine bağlanıp tek bir kapsayan ağaç oluşana kadar bu işlemi tekrarlayın.
- Sonunda her hücre, döngüler veya izole bölümler olmadan diğer hücrelere bağlanır.
Kruskal'ın algoritması kümeleri birleştirmeye dayandığından, labirent oluşturma sırasında bağlı hücreleri izlemek için etkili bir yol sağlayan Union-Find algoritması kullanılarak optimize edilebilir. Union-Find algoritmasının PHP uygulamasını burada görebilirsiniz: PHP'de Ayrık Küme (Birleşim Bulma Algoritması)