Python’da Derinlik-Öncelikli Arama: Grafikler ve Ağaçlarda Dolaşma

Geniş bir mağara sistemini keşfettiğinizi hayal edin. Bir tünel seçip sonuna kadar, gittikçe derine inerek ilerliyorsunuz; bir çıkmaza ulaştığınızda ise geri dönüp son kavşağa gelerek yeni bir tünel deniyorsunuz. Bu tür derinlemesine keşif, yalnızca gerektiğinde adımlarınızı geriye sarmak, grafikler ve ağaçlar gibi veri yapıları içinde gezinmek için temel bir algoritma olan derinlik-öncelikli aramaya (DFS) oldukça benzer.

Veri yapıları, algoritmalar ve problem çözme ile ilgileniyorsanız, DataCamp size yardımcı olur: Farklı veri yapıları ve onları keşfetmek için en iyi algoritmalar hakkında daha fazla bilgi edinmek için Data Structures and Algorithms in Python kursuna ve Data Structures: A Comprehensive Guide With Python Examples eğitimine göz atın.

Derinlik-Öncelikli Arama nedir?

Derinlik-öncelikli arama (DFS), bir grafik veya ağaç gibi bir veri yapısı içinde dolaşmak veya arama yapmak için kullanılan bir algoritmadır. DFS’in temel fikri, geri dönüp alternatif dalları keşfetmeden önce bir grafik ya da ağacın bir dalında olabildiğince derine inmektir. Bu yaklaşım, bir sonraki derinlik seviyesine geçmeden önce mevcut seviyedeki tüm düğümleri keşfeden genişlik-öncelikli aramaya (BFS) zıttır. Genişlik-öncelikli arama hakkında BURADAN okuyabilirsiniz.

Derinlik-öncelikli aramayı bir labirenti keşfetmek gibi düşünün: Bir yol seçer ve bir çıkmaza ulaşana kadar onu takip edersiniz. O yolun sonuna vardığınızda, son karar noktasına geri dönerek farklı bir rota denersiniz. Bu derin keşif, özellikle çok sayıda olası yol içeren yapılarda, yapının tamamını keşfetmek istendiğinde DFS’i mükemmel bir tercih kılar.

DFS, özellikle tüm olası çözümleri keşfetmeniz gerektiğinde faydalıdır.

Birkaç örnek şunlardır:

• Her dalın bir dizi seçimi temsil ettiği ve tüm olası sonuçların değerlendirilmesinin amaçlandığı yapay zekâdaki karar ağaçlarında gezinmek.
• Bir oyun tahtasında gezinmek veya bir haritada güzergâh bulmak gibi, kapsamlı aramalar gerektiren yol bulma problemleri.

DFS her düğümün bir kez ziyaret edilmesini ve algoritmanın tüm grafik veya ağacı kapsamasını sağlar.

Python’da Derinlik-Öncelikli Aramanın Temel Özellikleri

Derinlik-öncelikli arama, düğümleri sistematik biçimde keşfeden ve yalnızca gerektiğinde geri izleyen bir yaklaşıma sahiptir. Hadi bazı temel özelliklerine göz atalım.

Özyinelemeli yapısı

DFS özünde özyinelemeli (recursive) çalışır; yani yapının daha derinlerine indikçe kendini tekrar tekrar çağırarak problemi çözer. DFS bir dala daldığında, diğer dalları keşfetmek üzere geri dönmeden önce olabildiğince derine iner. Bir yola derine inme ve daha fazla seçenek kalmadığında geri izleme süreci, ideal olarak özyineleme ile yönetilir. Özyinelemeli fonksiyonların ne olduğu ve ne zaman faydalı olduklarına derinlemesine bakmak için Understanding Recursive Functions in Python içeriğine göz atın.

Geri izleme

Geri izleme, DFS için esastır. Algoritma ziyaret edilmemiş komşusu olmayan bir düğüme ulaştığında, önceki düğüme adımlarını geri sarar ve orada ziyaret edilmemiş başka komşular olup olmadığını kontrol eder. Varsa onları keşfeder; yoksa geri izlemeye devam eder. Bu, derine dalma ve geri sarma döngüsü, tüm olası yollar kapsanıncaya kadar ya da bir çıkış koşulu karşılanıncaya kadar sürer.

Döngülerle başa çıkma

Grafikler, kendi üzerine dönen yollar olan döngüler içerebilir. Uygun önlemler olmadan, DFS bu döngülerde düğümleri sonsuz kez yeniden ziyaret edebilir. Her düğümü ilk karşılaşıldığında “ziyaret edildi” olarak işaretleyerek, DFS gereksiz yere adımlarını yeniden izlemekten kaçınır. Böylece, döngülü grafiklerde bile DFS verimli kalır ve sonsuz döngülerden kaçınır.

Kapsamlı keşif

DFS’in ayırt edici özelliklerinden biri, bir yapıyı tamamen keşfedebilmesidir. Algoritma, her düğüm ziyaret edilene kadar devam eder. Bu, bulmacaları çözmek, karar ağaçlarını keşfetmek veya labirentlerde gezinmek gibi, hiçbir olası çözümün gözden kaçmadığından emin olmanız gereken durumlarda özellikle kullanışlıdır.

Python’da Derinlik-Öncelikli Arama Uygulaması

Python’da derinlik-öncelikli aramayı uygulamanın iki ana yolu vardır: özyinelemeli ve yinelemeli. Her yaklaşımın avantajları ve ödünleri bulunur; seçim genellikle grafiğin boyutuna ve çözdüğünüz probleme bağlıdır.

Her iki yöntemi de göstermek için basit bir karar ağacı oluşturalım ve DFS ile onu dolaşalım. Örneğimiz için Python kullanacağız. Python bilginizi tazelemek isterseniz Python Programming beceri yoluna göz atabilirsiniz.

Örnek olarak ikili bir karar ağacı alalım. Her düğümün iki alt dala sahip olduğu basit bir ağaç yapısı şöyle:

Bu karar ağacını Python’da açıkça bir sözlük olarak tanımlayalım.

# Define the decision tree as a dictionary
tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H', 'I'],
    'E': ['J', 'K'],
    'F': ['L', 'M'],
    'G': ['N', 'O'],
    'H': [], 'I': [], 'J': [], 'K': [],
    'L': [], 'M': [], 'N': [], 'O': []
}Altyapı:

Özyinelemeli DFS

DFS sıklıkla özyinelemeli olarak uygulanır. Her düğümde, DFS alt düğümler üzerinde kendini çağırır; ziyaret edilecek düğüm kalmayınca geri izler. İşte ağacı dolaşmak için özyinelemeli bir DFS fonksiyonu.

# Recursive DFS function
def dfs_recursive(tree, node, visited=None):
    if visited is None:
        visited = set()  # Initialize the visited set
    visited.add(node)    # Mark the node as visited
    print(node)          # Print the current node (for illustration)
    for child in tree[node]:  # Recursively visit children
        if child not in visited:
            dfs_recursive(tree, child, visited)

# Run DFS starting from node 'A'
dfs_recursive(tree, 'A')Altyapı:

Bu özyinelemeli sürümde kök düğüm A’dan başlar, alternatifleri keşfetmek için geri dönmeden önce her dal boyunca derine ineriz. Bu kodu çalıştırırsak, ağacı keşfederken izlenen yolu çıktılar:

A
B
D
H
I
E
J
K
C
F
L
M
G
N
OAltyapı:

Yinelemeli DFS

Çok büyük karar ağaçlarında, Python’un özyineleme derinliği sınırı sorun yaratabilir. Bu durumlarda, ziyaret edilmesi gereken düğümleri yönetmek için bir yığın kullanarak DFS’i yinelemeli olarak uygulayabiliriz. Aynı karar ağacı için yinelemeli DFS’i şöyle uygulayabiliriz:

# Iterative DFS function
def dfs_iterative(tree, start):
    visited = set()  # Track visited nodes
    stack = [start]  # Stack for DFS

    while stack:  # Continue until stack is empty
        node = stack.pop()  # Pop a node from the stack
        if node not in visited:
            visited.add(node)  # Mark node as visited
            print(node)        # Print the current node (for illustration)
            stack.extend(reversed(tree[node]))  # Add child nodes to stack

# Run DFS starting from node 'A'
dfs_iterative(tree, 'A')Altyapı:

Bu yinelemeli yaklaşım, yığını elle yöneterek özyineleme derinliği sınırlarını aşar; bu da büyük ağaçlar veya derin yapılar için faydalıdır. Bu kodu çalıştırmak, yukarıdakiyle aynı çıktıyı verir.

Ne Zaman Özyinelemeli, Ne Zaman Yinelemeli DFS Kullanmalı?

Derinlik-öncelikli aramada hem özyinelemeli hem de yinelemeli yaklaşımlar değerlidir; ancak aralarındaki seçim, grafiğin yapısına ve özel gereksinimlerinize bağlıdır. Her yaklaşımın güçlü ve sınırlı yönlerine yakından bakalım.

Özyinelemeli DFS

Genellikle özyinelemeli DFS’in sadeliğini ve zarafetini tercih ederim. Bu yaklaşım sezgiseldir ve temizdir.

Artıları:

• Sadelik: Kod kısadır ve problemi iyi yansıtır.
• Okunabilirlik: Özellikle küçük ve orta boyutlu problemler için anlaşılması daha kolaydır.

Eksileri:

• Özyineleme Derinliği Sınırı: Büyük grafiklerde Python’un özyineleme derinliği sınırına takılabilirsiniz.

Özyineleme, ağaç veya grafiğin nispeten küçük olduğu ve Python’un özyineleme derinliği sınırları içinde rahatça kaldığı problemler için idealdir.

Yinelemeli DFS

Yazması biraz daha karmaşık olsa da, yinelemeli DFS daha esnektir ve özyineleme sınırlarını dert etmeden daha büyük problemleri kaldırabilir. Python’un çağrı yığınına güvenmek yerine, yinelemeli DFS keşfedilecek düğümleri açıkça bir yığınla yönetir.

Artıları:

• Özyineleme Sınırı Yok: Yığın elle yönetildiğinden Python’un özyineleme derinliği sınırı aşılmaz.

Eksileri:

• Daha Fazla Kod: Yinelemeli DFS daha fazla kurulum gerektirir ve daha az sezgisel olabilir.
• Okunabilirlik: Kod genellikle biraz daha uzundur ve takip etmesi zor olabilir.

Yinelemeli yaklaşım, özyineleme derinliğinin sorun olabileceği büyük veya karmaşık problemler için en iyisidir. Ayrıca dolaşım üzerinde daha fazla denetime ihtiyaç duyduğunuzda da kullanışlıdır.

Zaman ve Bellek Karmaşıklığı

DFS verimli bir algoritmadır; ancak performansı, keşfettiği grafiğin boyutu ve yapısından etkilenir. DFS’in çalışmasının ne kadar sürdüğü ve ne kadar bellek kullandığı, ziyaret ettiği düğüm sayısına ve aralarındaki bağlantılara bağlıdır.

Karmaşıklığı konuşmak için Big O gösterimini kullanırız. Big O gösterimine hızlı bir bakış için Big O Notation and Time Complexity Guide: Intuition and Math içeriğine göz atın.

Zaman karmaşıklığı

DFS’in zaman karmaşıklığı O(V + E) olarak tanımlanır; burada V düğüm sayısı, E ise bağlantı ("kenar") sayısıdır. DFS her düğümü ve her bağlantıyı bir kez ziyaret eder. Dolayısıyla, DFS’in toplam çalışma süresi düğüm ve bağlantı sayısına bağlıdır.

Alan (bellek) karmaşıklığı

DFS’te kullanılan bellek, algoritmanın herhangi bir anda takip ettiği düğüm sayısına bağlıdır. Hem özyinelemeli hem yinelemeli DFS, keşfedilen düğümleri izlemek için bir yığın kullanır. En kötü senaryoda, kullanılan bellek grafikteki tüm düğümleri tutabilir ve bu da O(V) alan karmaşıklığına yol açar.

Algoritma karmaşıklığını ölçmenin diğer yollarını Analyzing Complexity of Code through Python eğitiminde keşfedin.

Derinlik-Öncelikli Aramanın Gerçek Hayat Uygulamaları

DFS; bilgisayar bilimi, yapay zekâ ve oyun geliştirme dâhil birçok alanda kullanışlıdır. Aşağıdaki tabloda DFS’in yaygın uygulamalarına göz atın.

Derinlik-Öncelikli Arama ve Diğer Arama Algoritmaları

DFS’i genişlik-öncelikli arama, Dijkstra Algoritması ve A* gibi diğer bilinen algoritmalarla karşılaştıralım.

Derinlik-öncelikli arama ve genişlik-öncelikli arama

Genişlik-öncelikli arama (BFS), bir grafiği seviye seviye keşfeder; bir sonraki seviyeye geçmeden önce mevcut derinlikteki tüm düğümleri ziyaret eder. BFS, amaç ağırlıksız bir grafikte en kısa yolu bulmak olduğunda özellikle kullanışlıdır. Ancak geniş grafiklerde her seviyedeki tüm düğümleri takip etmek zorunda olduğundan, çok bellek kullanabilir. BFS, sosyal ağ analizi veya basit yönlendirme problemleri için harika bir seçimdir.

Öte yandan derinlik-öncelikli arama, bir grafikteki döngüleri bulmak veya bulmaca çözmek gibi tüm olası yolları ya da çözümleri keşfetmek istendiğinde kullanışlıdır. BFS’in aksine, DFS en kısa yolu garanti etmez. Ancak yalnızca mevcut yolu takip ettiği için bellek açısından daha verimlidir.

Genişlik-öncelikli arama hakkında daha fazla bilgiyi Breadth-First Search: A Beginner’s Guide with Python Examples içeriğinde bulabilirsiniz.

DFS ve Dijkstra algoritması

Dijkstra algoritması, her düğümler arası bağlantının bir maliyete sahip olduğu ağırlıklı kenarlı grafiklerde en kısa yolu bulmak için tasarlanmıştır. Dijkstra, her zaman en düşük maliyetli yolu önce keşfederek, başlangıç düğümünden herhangi bir düğüme giden en iyi yolu bulmayı garanti eder. Ancak bazı basit grafik keşiflerinde DFS’ten daha yavaş olabilir. Dijkstra, yol maliyetlerinin önemli olduğu yol ağları veya daha karmaşık yönlendirme problemleri için idealdir.

Derinlik-öncelikli arama kenar ağırlıklarını dikkate almaz; bu nedenle en iyi yolu garanti etmez. Ancak ağırlıksız grafiklerde veya kenar ağırlıklarının önemsiz olduğu durumlarda Dijkstra’dan daha hızlıdır.

Dijkstra Algoritması hakkında daha fazla bilgiyi Implementing the Dijkstra Algorithm in Python: A Step-by-Step Tutorial içeriğinde bulabilirsiniz.

DFS ve A*

A* ("A-star" olarak okunur), aramasını yönlendirmek için bir sezgisel (heuristic) kullanan ve böylece Dijkstra’yı geliştiren bir algoritmadır. Bu, birçok durumda onu daha hızlı ve verimli kılar. A*, en düşük maliyetli yolları keşfetmek (Dijkstra gibi) ile hedefe doğrudan yönelmek arasında denge kurar; hedefe düz çizgi mesafesi gibi bir sezgiselden yararlanır. Bu da A*’yı GPS navigasyonu veya video oyunlarında yol bulma gibi görevlerde son derece verimli yapar.

Derinlik-öncelikli arama herhangi bir sezgisel kullanmaz; yani A*’nın hedefe verimli şekilde ulaşmak için kullandığı “yön”e sahip değildir. DFS, tüm grafik veya karar ağacının kapsamlı biçimde taranması gereken problemler için daha uygundur; A* ise, bir sezgiselin yardımıyla en kısa yolun verimli şekilde bulunması gerektiğinde daha iyidir.

Yaygın Hatalar ve Bunlardan Kaçınma Yolları

Derinlik-öncelikli arama kullanırken, özellikle büyük grafiklerde birkaç yaygın sorun ortaya çıkabilir.

Ziyaret edilen düğümlerin izlenmemesi

Zaten ziyaret edilmiş düğümlerin izinin unutulması bir sorundur. Bu, özellikle döngüler içeren grafiklerde sonsuz döngülere yol açabilir. DFS, keşfedilip keşfedilmediğini kontrol etmeden düğümleri yeniden ziyaret ettiğinde, sonsuz bir döngüye takılabilir. Bundan kaçınmak için, ziyaret edilen düğümlerin bir listesini (tercihen bir küme) tutun. Yeni bir düğümü ziyaret etmeden önce ziyaret kümesinde olup olmadığını kontrol edin. Varsa güvenle atlayabilir ve takılmaktan kaçınabilirsiniz.

Özyinelemeli DFS’te yığın taşması

Python’da özyineleme derinliği varsayılan olarak yaklaşık 1.000 seviyeyle sınırlıdır; bu da büyük grafiklerde derinlemesine özyinelemeli çağrıların RecursionError’a neden olabileceği anlamına gelir. Bunu önlemek için büyük grafiklerde yinelemeli bir DFS uygulaması kullanabiliriz. Yığını bir liste olarak tutarak özyineleme sınırlarından kaçınır ve çok daha büyük grafiklerle güvenle başa çıkabiliriz.

Bir çözümü en kısa yol sanmak

DFS’in iki düğüm arasındaki en kısa yolu garanti etmediğini unutmamak da önemlidir. DFS, diğer yolları keşfetmek için geri dönmeden önce bir yolu derinlemesine takip ettiğinden, bir çözüm bulabilir; ancak bu, en doğrudan olan olmayabilir.

Sonuç

Derinlik-öncelikli arama, grafikler ve ağaçları keşfetmek ve dolaşmak için güçlü bir algoritmadır. Yolların derinliklerine inebilme ve tüm olasılıkları keşfedebilme yeteneğiyle, labirent çözme, bulmaca çözme ve karar ağacı keşfi gibi çeşitli problemler için son derece uygundur.

Arama algoritmalarıyla ilgileniyorsanız, bu serideki diğer yazılarıma göz atın: Binary Search in Python: A Complete Guide for Efficient Searching ve Breadth-First Search: A Beginner’s Guide with Python Examples. Ayrıca AVL Tree: Complete Guide With Python Implementation ve Introduction to Network Analysis in Python içeriklerine de ilgi duyabilirsiniz.