BİL207U-VERİ YAPILARI
Ünite 8: Graf Veri Modeli ve Algoritmalar
Giriş
Matematiksel anlamda Graf, düğümler ve bu düğümler arasındaki ilişkileri gösteren kenarlardan oluşan kümeye verilen isimdir. Mantıksal ilişki ise düğüm ile düğüm veya kenar ile düğüm arasında kurulmaktadır. Bağlantılı listeler (linked list) ve ağaç yapıları (tree) graf yapısı ile oluşturulmuş özel örneklerdir.
Graflar, gerçek hayatta karşılaşılan yapıları temsil etmesi amacıyla bilgisayar ortamında kullanılan şekillerdir. Bir karar ağacının şekillendirilmesi, bir bilgisayar ağının görselleştirilmesi gibi işlemlerde graflar kullanılmaktadır.
Tıptan mühendisliğe, fizik ve kimya gibi temel bilimlerde pek çok problemin modellendirilmesi ve çözümünde graflardan yararlanılmaktadır. Grafta varlıklar düğümler ile ifade edilmektedir. Varlıklar arasındaki ilişkiler ise graftaki kenarlar ile gösterilmektedir. Graf kenarlarının yönlü olanları yönlü graflar, yönsüz olanları ise yönsüz graflar olarak isimlendirilir. Bunun yanında kenarların değer almalarına göre de ağırlıklı/değerli graflar ve ağırlıksız/ değersiz graflar olarak isimlendirilmektedirler.
Graf Veri Modeli
Yönsüz ve Yönlü Graflar (Undirected & Directed Graphs)
Düğümler arasındaki kenarlara yönlendirme atanan graflara Yönlü Graf, yönlendirme olmayan durumdaki graflara ise Yönsüz Graf adı verilmektedir. Graflardaki düğümler arası ilişkilerde, kullanılacak uygulamada kenar bağlantılarının nereden başlayıp nerede bittiği bilgisi önemli ise yönlü graflar tercih edilmelidir.
Bir G grafı, D ile gösterilen düğümler (vertex/node) ile K ile gösterilen kenarlardan (edge) oluşan bir yapı şeklinde tanımlanabilir. Kenarlar, iki düğümü birleştirerek düğümler arasındaki ilişkiyi meydana getirmektedirler. Düğümler arasındaki bu ilişki (u,v) şeklinde ifade edilmektedir.
Düğümler arasındaki oklar çizilirken “a” düğümünden başlayarak “b” düğümüne giden yönlü bir kenar için (a, b) şeklinde ifade edilmektedir yani ilk düğüm yönlü kenarın başlangıcı, ikinci düğüm ise bitişi göstermektedir.
Ağırlıksız ve Ağırlıklı Graflar (Unweighted & Weighted Graphs)
Sadece iki düğümün bağlı olup olmaması önemseniyorsa böyle bir graf ağırlıksız olarak adlandırılır. Aralarında bir kenar bulunan düğümler de birbirlerine bitişik veya komşu düğümler olarak isimlendirilmektedir. Ağırlıksız graflar bize yalnızca iki düğümün bağlantılı olup olmadığını söyler bu nedenle aşağıdaki gibi sorgular için uygundurlar:
• u ve v düğümleri arasında bir yol var mı? • u’dan hangi düğümlere ulaşılabilir? • u ve v arasındaki en kısa yol üzerinde kaç tane düğüm bulunmaktadır?
Bununla birlikte birçok uygulamada kenarlar, eldeki sorunu çözmek için algoritmalarımızda kullanmamız gereken sayısal özelliklere sahiptir. Örneğin iki şehir arasındaki en kısa yolu ararken yol uzunlukları ve trafik yoğunluğu dikkate alınmalıdır. Böylece her e kenarı, ağırlık denen gerçek bir w(e) değeriyle ilişkilendirilmelidir. Bu tür graflara da ağırlıklı graf denmektedir.
Ağırlıklı graf, her kenarın sayısal bir ağırlığının verildiği bir graf türüdür. Bu nedenle ağırlıklı bir graf, etiketlerin genellikle pozitif sayılar olduğu özel bir etiketli graf türüdür. Ağırlıklı graflar yönlendirilmiş veya yönlendirilmemiş olabilir. Bir kenarın ağırlığı genellikle kenarın “maliyeti” olarak adlandırılır. Uygulamalarda ağırlık; bir rotanın uzunluğunun, bir hattın kapasitesinin, bir rota boyunca konumlar arasında hareket etmek için gereken enerjinin vb. bir ölçüsü olabilir. Ağırlıklı bir grafik G = (V, E), her e ∈ E kenarına bir w(e) ağırlığı atayan bir w fonksiyonu ile ilişkilendirilir.
Graf Tanımları
Graf kavramı, bazılarını birbirine bağlayan kenarları olan ve muhtemelen etiketlenmiş düğümlerin genellikle daireler ile gösterilen bir çizimidir. Graflar, birçok problemin çevrilebileceği ve çoğu zaman çözülebilecek bir model hâline getirildiği yapılardır. Bu kısımda grafların özel durumları ve özellikleri incelenecektir.
Komşu Düğümler (Adjacent)
Verilen bir G grafı üzerinde tanımlı di ve dj iki düğüm, kenar kümesinde tanımlı bir kenar ile ilişkilendiriliyorsa bu iki düğüm, komşu (adjacent) düğümlerdir. Başka bir ifade ile k kenarı, di ve dj düğümlerini bağlamaktadır veya di ve dj düğümleri k kenarının uç noktaları olduğu söylenebilir.
Komşuluk ve Bitişiklik
Komşuluk ilişkisi ile gösterilen bir G grafı, Gdd = {(di , dj ), ...} şeklinde gösterilirken bitişiklik ilişkisi ile gösterilen bir graf ise Gdk = {(di , kj ), …} şeklinde ifade edilmektedir.
Yönlendirilmiş Graf (Directed Graphs)
Bir G grafı üzerinde tanımlanmış kenarlar, düğümler arasındaki bağlantıların nerede başlayıp nerede bittiğini gösteren yönlendirme bilgisine sahip ise bu graflara yönlendirilmiş/yönlü graf denmektedir. Yönlü graflarda kenarlar için yönlendirme “< >” işaretleri ile yapılmaktadır.
Yönlendirilmemiş Graf (Undirected Graphs)
Yönsüz bir graf; tüm kenarların çift yönlü olduğu, birbirine bağlı bir dizi nesne (düğüm) olan bir grafiktir. Bir G grafında tanımlı kenarlardan hiçbiri yönlendirilmemiş ise bu graflara yönlendirilmemiş graf denmektedir. Yönlendirilmemiş bir graf bazen yönsüz ağ olarak da adlandırılmaktadır. Yönlendirilmemiş bir graf çizilirken kenarlar tipik olarak düğüm çiftleri arasında çizgiler olarak çizilir.
Yönlendirilmiş Kenar (Directed Edge)
Yönlendirilmiş kenar, yönlendirilmiş bir grafta bulunan kenara verilen addır. Bu yönlendirilmiş kenarın ok işareti ile temsil edilen bir yönlendirmeye sahip olması gerekmektedir. Bu okun kuyruğu ve başı, başlangıcı ve bitişi temsil eden düğümlerdir. Yönlendirilmiş kenarlar “tek yönlü sokaklar” olarak düşünülebilir. Yönlendirilmiş kenarlar üzerinden düğümden düğüme geçerken her zaman izin verilen yönde yani bir kenarın kuyruğundan başına doğru gidilmesi gerekmektedir. Yönsüz graflarda, kenardaki düğümlerin sırası önemli olmadığından bir kenar {v,w} veya {w,v} olarak temsil edilebilir. Bununla birlikte yönlendirilmiş kenar (v,w), v’nin kenarın kuyruğu yani başlangıç noktası ve w’nin kenarın başı yani bitiş noktası olduğunu simgelemektedir. Bu hâliyle (v,w) kenarı, (w,v) kenarının tam tersi bir yönü işaret etmektedir.
Yönlendirilmemiş Kenar (Undirected Edge)
Yönlendirilmemiş kenar, yönlendirilmemiş bir grafta bulunan bir kenardır. Yönlendirilmemiş kenar bir yönlendirmeye sahip değildir. Kenarın başlangıcı ve bitişi yoktur, sınırsız kenar çizgileri ile gösterilmektedir. Yönlendirilmemiş kenarlar ise “çift yönlü sokaklar” olarak düşünülebilir. Yönlendirilmemiş kenarlar üzerinden düğümden düğüme geçerken, istenilen doğrultuda hareket edilebilmektedir. Yönlendirilmemiş kenarlarda kenardaki düğümlerin sırası önemli olmadığından bir kenar {v,w} veya {w,v} olarak gösterilebilir.
Yol (Path)
Graf teorisinde çoğu tanımlamada yol, hepsi farklı olan bir düğümler dizisini birleştiren sonlu veya sonsuz bir kenar dizisine verilen addır. Yani bir graftaki yolun düğümlerin sırası olduğu söylenebilir. Kenar uzunlukları ya da ağırlıklar ise yolun uzunluğunu belirlemektedir. Yönlendirilmiş bir grafikte yönlendirilmiş bir yol, kenarların hepsinin aynı yönde yönlendirildiği varsayımı ile, bir dizi farklı düğümleri/köşeleri birleştiren sonlu veya sonsuz bir kenar dizisidir. Kenar içermeyen bir yol varsa bu yolun uzunluğu 0’dır. Şehirlerin her biri bir düğüm olduğu varsayıldığında Antalya’dan İstanbul’a Ankara üzerinden de, Balıkesir üzerinden de ulaşılabilecek yol oluşturulabilir.
Basit Yol (Simple Path)
Grafik teorisinde basit yol, bir grafta tekrar eden düğümleri olmayan bir yola verilen addır. V’nin düğümler kümesi ve E’nin de kenarlar kümesi olduğu yönlendirilmiş bir G(V, E) grafı olduğunu varsayalım. İki u ve v düğümü (u ∈ V, v ∈ V) arasındaki basit bir yol, aşağıdaki koşulları karşılayan bir düğümler dizisidir (v1, v2, …, vk): (1 ≤ i ≤ k)’nin V düğümleri kümesine ait olduğu tüm vi düğümleri u = v1, v = vk (1 ≤ i < k) şartını sağlayan ardışık her iki düğüm için (vi , vi+1), E kenarları kümesine ait bir e = (vi , vi+1) kenarı vardır. Dizide birden fazla geçilen düğüm bulunmaz; başka bir deyişle, basit yolda döngüsel bağlantı yoktur Bir grafta iki düğüm, u ve v verildiği bir örneği inceleyelim. Bizden iki düğüm ile u ve v arasındaki olası tüm basit yolların bulunması isteniyor.
Uzunluk (Length)
Grafın uzunluğunu, grafın içerdiği kenar sayısı olarak tanımlanabilir. Ayrıca, kenar uzunlukları verilen bir grafta, bir yol üzerindeki kenarların uzunlukları toplamı o yolun uzunluğudur.
İki Düğüm Arası Mesafe
Bir grafikteki iki düğüm arasındaki mesafe, en kısa yoldaki kenarların sayısıdır. Bu sayı bize iki düğüm arasındaki mevcut minimum mesafeyi vermektedir. Ayrıca iki düğüm arasında birden fazla en kısa yol da bulunabilmektedir.
Grafiğin Eksantrikliği
Eksantriklik, bir tepe noktasının diğer tepe noktasından maksimum uzaklığı olarak tanımlanmaktadır. Bir tepe noktasının diğer tüm tepe noktalarına olan maksimum uzaklığı, o tepe noktasının eksantrikliği olarak kabul edilir ve e(V) ile gösterilir.
Grafın Çapı
Grafın çapı, düğüm çifti arasındaki maksimum mesafedir. Grafın çap değerinin bulunması için tüm yollar bulunur ve sonra hepsinin maksimum değeri hesaplanır. Ayrıca tüm düğümlerden maksimum eksantriklik değerleri bulunarak da grafın çap bilgisi elde edilebilir.
Grafın Yarıçapı
Grafın yarıçapı, yalnızca çapı varsa vardır. Bir tepe noktası ile diğer tüm tepe noktaları arasındaki tüm maksimum mesafeler arasındaki minimum, Grafiğin G yarıçapı olarak kabul edilir. r(G) olarak gösterilir. Ayrıca tüm düğümlerden minimum eksantriklik değeri hesaplanarak da bulunabilir.
Grafın Merkezi
Eksantrikliği minimum olan tüm düğümlerden oluşmaktadır. Burada eksantriklik yarıçapa eşittir. Örneğin okul şehir merkezinde ise otobüslerin kat etmesi gereken mesafeyi azaltacaktır. İki düğümün eksantrikliği aynı ve diğerleri arasında minimum ise her iki düğüm de grafın merkezi olabilir. Grafiğin merkezini bulmak için, her bir düğümün eksantrikliğinin hesaplanarak bunların minimumunun bulunması gerekmektedir. Minimum eksantriklik tepe noktası merkez olarak kabul edilmektedir.
Bağlı veya Bağlı olmayan Graf (Connected Graph)
Bir graftaki tüm düğümler arasında en az bir kenar/yol varsa bu bir bağlı graftır. Tam tersi olarak bir grafta herhangi iki düğüm arasında bir kenar/yol bulunmuyorsa bu grafa da bağlı olmayan graf denmektedir.
Alt Graf (Subgraph)
G ve S isimli iki graftan S grafının düğüm ve kenarları, G grafının düğüm ve kenarlarının alt kümesi ise S grafı G grafının alt grafıdır. Daha anlaşılır bir dille bir alt graf, daha büyük bir grafın içindeki bir graftır.
Ağaçlar (Trees)
Graf teorisinde bir ağaç, herhangi iki düğümün tek bir yolla bağlandığı yönsüz bir graftır veya buna eşdeğer olarak bağlantılı, döngüsel olmayan, yönsüz bir graftır. Bir orman ise herhangi iki düğüm noktasının en fazla bir yolla bağlandığı yönsüz bir graftır veya eşdeğer olarak döngüsel olmayan yönsüz bir graf veya eşdeğer olarak ayrık bir ağaç birleşimine verilen addır.
Komple/Tam Graf (Complete Graph)
Bir tam graf, her bir graf düğüm çiftinin bir kenarla bağlandığı bir graftır yani tüm düğümler birbirlerine bir kenar ile bağlıdır. Daha eski literatürde, tam graflara bazen evrensel graflar da denmektedir.
Çoklu Graf (Multigraph)
Graf teorisinde çoklu graf, birden çok kenara yani aynı son düğümlere sahip kenarlara sahip olmasına izin verilen bir grafa verilen isimdir. Böylece iki düğüm birden fazla kenarla birleştirilebilir. Bu kenarlar paralel kenarlar olarak da adlandırılır.
Düğüm Derecesi (Node Degree)
Bir düğümün derecesi, o düğüme bağlı olan kenarların sayısıdır. Yönlendirilmiş bir grafta her düğümün iki derecesi bulunmaktadır. Çıkış derecesi, bir düğümden çıkan kenarların sayısıdır. Giriş derecesi ise bir düğüme gelen kenarların sayısıdır. Düğümün toplam derecesi, giriş ve çıkış derecelerinin toplamıdır. Dikkat edilmesi gereken bir durum da döngüsel kenarlar düğümlere hem giriş hem de çıkış yaptığı için iki defa sayılarak dereceyi 2 arttırmaktadır.
Komşuluk Matrisi (Adjacency Matrice)
Graflar ayrıca matrisler şeklinde de tanımlanabilir. Graflarda yolların ve döngülerin hesaplanmasını gerçekleştirmek için matris gösterimi kullanılır. Hesaplamalarda matris işlemleri kullanılır. Grafların en yaygın iki gösterimi şunlardır:
• Komşuluk / Bitişiklik Matrisi • Komşuluk / Bitişiklik Listesi
Bağlantı matrisi olarak da adlandırılan komşuluk matrisi, Vi ve Vj ’nin bitişik olup olmama durumuna göre (Vi , Vj) konumunda 0 veya 1 olan basit bir etiketli grafiği temsil etmek için kullanılan satırlar ve sütunlar içeren bir matristir.
Ağırlıklandırılmış grafta oluşan komşuluk matrisi, yönü olmadığı için simetrik bir matristir. Benzer şekilde yönlendirilmemiş ve ağırlıklandırılmamış grafta da 0 ve 1 değerleri ile oluşturulmuş bir simetrik matris elde edilmektedir.
Komşuluk Listesi (Adjacency List)
Bir graftaki her düğümün komşu düğümlerinin listesine verilen addır. Komşuluk listesi, bir grafı bağlantılı listeler dizisi olarak temsil etmektedir. Dizinin indisi bir düğümü temsil eder ve bağlantılı listesindeki her öğe, düğüm ile bir kenar oluşturan diğer düğümleri temsil etmektedir.
Komşuluk Listesinin Artıları
• Komşuluk listesi, depolama açısından verimlidir çünkü yalnızca kenarlar için değer saklanması gerekir. Milyonlarca düğümü ve kenarı olan seyrek bir graf için bu çok fazla yer tasarrufu anlamına gelebilir. • Ayrıca bir tepe noktasına bitişik tüm düğümleri kolayca bulmaya yardımcı olur.
Komşuluk Listesinin Eksileri
• Komşuluk listesini bulmak, komşuluk matrisinden daha hızlı değildir çünkü listenin oluşturulması için önce tüm bağlı düğümlerin keşfedilmesi gerekmektedir.
Bitişiklik Matrisi (Incidence Matrix)
Matematikte bitişiklik matrisi; genellikle bir olay ilişkisi olarak adlandırılan, iki nesne sınıfı arasındaki ilişkiyi gösteren mantıksal bir matristir. Birinci sınıf X ve ikincisi Y ise matrisin X’in her elemanı için bir satırı ve Y’nin her elemanı için bir sütunu bulunmaktadır. x ve y ilişkiliyse x satırı ve y sütunundaki değer 1’dir, ilişkili değilse 0 değeri verilmektedir. Bitişiklik matrisi, grafik teorisinde yaygın bir grafik temsilidir. Düğüm-düğüm çiftlerinin ilişkisini kodlayan komşuluk matrisinden farklıdır. Bitişiklik matrisi, adından da anlaşılacağı gibi düğümler ve kenarlar arasındaki bağlantıyı göstermektedir. Matrisin satırları düğümleri, sütunları da kenarları göstermektedir.
Graf Algoritmaları
Graflar; sosyal bilimlerden mühendisliğe, tıptan temel bilimlere kadar çok çeşitli dallarda problemlere algoritmik çözümler sunmaktadır. Eğer sistem bir şekilde düğümler ve aralarındaki ilişkiler de kenarlar ile gösterilebiliyorsa mevcut graf algoritmaları ile probleme çözüm yolu aranabilir. İki şehir arasındaki en kısa mesafeden bir kargo dağıtıcısının tüm adreslere en verimli şekilde uğraması gibi problemlere, graf algoritmaları ile algoritmik çözümler geliştirilebilir.
Önce Derinlik Araması (Depth First Search - DFS)
Önce Derinlik Araması veya Önce Derinlik Geçişi, bir grafiğin veya ağaç veri yapısının tüm düğümlerini aramak için kullanılan yinelemeli (recursive) bir algoritmadır. Geçiş, bir grafiğin tüm düğümlerini ziyaret etmek anlamına gelmektedir. Standart bir DFS uygulaması, grafiğin her düğümünü iki kategoriden birine yerleştirir:
• Ziyaret Edildi • Ziyaret Edilmedi
Algoritmanın amacı, döngülerden kaçınırken her düğümün ziyaret edilmiş olarak işaretlenmesidir.
DFS algoritmasının çalışma mantığı şu şekildedir:
1. Grafiğin düğümlerinden herhangi birini bir yığına (stack) ekleyerek başlayın. 2. Yığının en üst ögesini alın ve ziyaret edilenler listesine ekleyin.
3. Bu düğümün bitişik düğümlerinin bir listesini oluşturun. Ziyaret edilenler listesinde olmayanları yığının en üstüne ekleyin. 4. Yığın boşalana kadar 2. ve 3. adımları tekrarlamaya devam edin.
Önce Derinlik Araması İncelemesi
Önce Derinlik Arama algoritmasının nasıl çalıştığını bir örnek üzeirnde inceleyelim. 5 düğümlü yönsüz bir grafik kullanıyoruz. DFS algoritmasına düğüm 1’den başlayarak ziyaret edilenler listesine ekliyoruz ve bitişik tüm düğümleri yığına koyuyoruz. 2. adımda, yığının tepesindeki ögeyi yani 2’yi ziyaret edip bitişik düğümlerine gidiyoruz. 1 zaten ziyaret edildiğinden sıradaki eleman 3’ü ziyaret ediyoruz. 3. adımda 3. düğümün ziyaret edilmemiş bitişik bir düğümü olan 5 var bu yüzden onu yığının en üstüne ekleyip onu ziyaret ediyoruz. Son eleman olan 4 ziyaret edildikten sonra ziyaret edilmemiş bitişik düğüm kalmadı böylece grafiğin Derinlik İlk Geçişi tamamlanmış oldu.
DFS Sözde Kod (Öz Yinelemeli Kodlama)
init() metodunda, her düğümde DFS metodunun çalıştırıldığına dikkat edilmelidir bunun nedeni grafın bağlantısız iki farklı parçası olabileceğinden her düğümün kapsandığından emin olmak için her düğümde DFS algoritması çalıştırılmalıdır.
Önce Derinlik Aramanın Karmaşıklığı
DFS algoritmasının zaman karmaşıklığı, Düğüm sayısına D ve kenar sayısı da K olarak ifade edildiğinde O(D + K) şeklinde temsil edilmektedir. Algoritmanın uzay karmaşıklığı O(D)’dir.
• DFS Algoritması • Yol (path) bulmak için • Grafiğin ikili yani 2 parça olup olmadığını test etmek için • Bir grafiğin güçlü bir şekilde bağlantılı bileşenlerini bulmak için • Bir grafikteki döngüleri tespit etmek için gibi alanlarda kullanılmaktadır.
Önce Genişlik Araması (Breadth First Search-BFS)
Geçiş, bir grafiğin tüm düğümlerini ziyaret etmek anlamına gelmektedir. Breadth First Traversal veya Breadth First Search, bir grafın veya ağaç veri yapısının tüm düğümlerini aramak için oluşturulmuş özyinelemeli bir algoritmadır.
BFS algoritması
Standart bir BFS uygulaması, grafın her düğümünü iki kategoriden birine yerleştirir:
1. Ziyaret Edildi 2. Ziyaret Edilmedi
Algoritmanın amacı, döngülerden kaçınırken her düğümü ziyaret edilmiş olarak işaretlemektir. Algoritma şu şekilde çalışmaktadır:
1. Grafın düğümlerinden herhangi birini kuyruğun sonuna ekleyerek başlayın. 2. Kuyruğun ilk ögesini alın ve ziyaret edilenler listesine ekleyin. 3. Bu düğümün bitişik düğümlerinin bir listesini oluşturun. Ziyaret edilenler listesinde olmayanları sıranın en arkasına ekleyin. 4. Kuyruk boşalana kadar 2. ve 3. adımları tekrarlamaya devam edin.
Grafın bağlantısız iki farklı parçası olabilir, bu nedenle her düğümün kapsandığından emin olmak için her düğümde BFS algoritması da çalıştırılabilir.
BFS Algoritması Karmaşıklığı
BFS algoritmasının zaman karmaşıklığı, D’nin düğüm sayısı ve K’nin kenar sayısı olduğu O(D + K) şeklinde temsil edilir. Algoritmanın uzay karmaşıklığı O(D)’dir. BFS Algoritması
• Yol bulma algoritmaları • GPS navigasyonu için • Arama dizinine göre dizin oluşturmak için bir ağda maksimum akışı bulmak amacıyla FordFulkerson algoritmasında • Yönsüz bir grafikte döngü algılama • Minimum yayılan ağaç (Minimum Spanning Tree)
gibi alanlarda kullanılmaktadır.
DFS ve BFS Arasındaki Temel Farklar
• DFS, kenar tabanlı bir algoritma iken BFS, düğüm tabanlı bir algoritma olarak tasarlanmıştır. • DFS yığın veri yapısı veya özyineleme kullanırken BFS’de kuyruk veri yapısı kullanılmıştır. • DFS’de bellek alanı daha verimli bir şekilde kullanılırken BFS’de bellek alanının verimli şekilde kullanımı göz ardı edilmektedir. • BFS en uygun algoritma iken DFS en uygun değildir. • DFS, dar ve uzun ağaçlar oluştururken BFS, geniş ve kısa bir ağaç oluşturmaktadır.
BFS ve DFS grafik arama algoritmalarının çalışma süreleri birbirine yakındır fakat algoritmaların kullanıldığı alanlar değişmektedir. BFS her düğümü hafızada tutarken DFS keşfedilmemiş düğümler üzerinden tek bir yol bilgisini tutabilmek için doğrusal alan kaplamaktadır. BFS ilk sırada en uygun ve verimli hedefi aradığı için DFS’e göre daha uygun bir tercihtir. DFS ise derin çözümler sunar ve çözüm yoğun olduğunda daha verimli çalışmaktadır.