Veri Yapısında DFS (Önce Derinlik Geçişi): Nedir, Sıralama ve Uygulamalar

Veri Yapısında DFS'nin Anlamı

Derinlik öncelikli geçiş olarak da bilinen Veri Yapısındaki DFS, öncelikle bir grafiğin veya ağaç veri yapısının tüm köşelerini aramak için kullanılan özyinelemeli bir algoritmadır. Geçiş, bir grafiğin her düğümünün ziyaret edilmesidir. Algoritma, kök düğümden (bir grafikteki kök düğüm olarak rastgele bir düğüm olabilir) başlar ve geri izlemeden önce her dal boyunca gidebildiği kadar ileri gider.

Buradaki fikir, kök veya rastgele düğümden başlamak ve düğümü işaretli tutmaktır. Bundan sonra, işaretlenmemiş bitişik düğüme geçmeniz ve işaretlenmemiş bitişik düğüm kalmayana kadar bu döngüye devam etmeniz gerekir. Ardından, işaretlenmemiş diğer düğümleri geriye doğru takip edin ve inceleyin ve bunları çaprazlayın. Son adım, yol içindeki düğümleri yazdırmaktır.

algoritma

Düğümün dizinini ve ziyaret edilen bir diziyi alacak özyinelemeli bir işlev formüle edin.

1. Geçerli düğümü ziyaret edildi olarak işaretli tutun ve ardından yazdırın.
2. Tüm bitişik notaları ve işaretlenmemiş notları çaprazlayın ve bitişik düğümün indeksi ile özyinelemeli işlevi çağırın.

Popüler Yazılım Mühendisliği Kurslarımızı keşfedin

Özellikleri

Veri Yapısında DFS'de zaman ve mekan analizi, uygulama alanına göre değişir. Teorik olarak, DFS esas olarak tam bir grafiği geçmek için kullanılır ve zaman alır O(|V|+|E|) burada |V| köşelerin sayısını ve |E| kenar sayısını gösterir. Bu grafik doğrusaldır.

Bu uygulamalarda, boşluk O(|V|) ayrıca arama yolunda depolanan köşe yığınını ve zaten ziyaret edilmiş olan köşe kümesini tutmak için son çare olarak kullanılır. Bu nedenle, zaman ve uzay sınırları ayarı, genişlik öncelikli aramaya benzer. Burada kullanılan iki algoritma, karmaşıklıklarına daha az bağımlıdır ve iki algoritma tarafından üretilen köşe sıralarının çeşitli özelliklerine daha çok bağlıdır.

Web taramasında veya yapay zekada çözümler bulmak gibi belirli etki alanlarıyla ilgili Veri Yapısında DFS uygulamaları söz konusu olduğunda, geçiş gerektiren grafik toplamda ziyaret edilemeyecek kadar önemli olabilir. Bu gibi durumlarda, arama yalnızca sınırlı bir derinlikte yürütülür; disk alanı veya bellek gibi sınırlı kaynaklar nedeniyle. Veri yapıları genellikle daha önce ziyaret edilen tüm köşelerin kümesini izlemek için kullanılmaz. Sınırlı bir derinlikte gerçekleştirilen bir arama, genişletilmiş kenarlar ve tepe noktaları birimi söz konusu olduğunda, zamanı hala doğrusal hale getirir.

Ancak, bazı köşeler birden çok kez aranabileceği ve diğerleri aranmayacağı için bu sayının grafiğin tamamıyla aynı boyutta olmadığını unutmayın.

Bu gibi durumlarda, DFS daha umut verici bir dal seçmek için buluşsal yöntemlere de yönelir. Son olarak, uygun derinlik sınırı belirlenemediğinde, a priori, yinelemeli derinleştirme DFS, bir dizi büyüme sınırı yoluyla tekrar tekrar uygulanır.

Dünyanın En İyi Üniversitelerinden Online Yazılım Geliştirme Kursları öğrenin . Kariyerinizi hızlandırmak için Yönetici PG Programları, Gelişmiş Sertifika Programları veya Yüksek Lisans Programları kazanın.

Derinlik İlk Arama Algoritması

Standart bir DFS uygulamasında bir grafiğin her köşe noktası iki kategoriden birine ayrılır:

1. Ziyaret Edilmedi
2. Ziyaret

Algoritma, her bir tepe noktasını tam olarak belirlemek ve onları ziyaret edildi olarak işaretlemek ve aynı zamanda döngüleri önlemek için kullanılır.

DFS algoritması şu şekilde çalışır:

1. Grafiğin herhangi bir köşesini bir yığına koyun.
2. Yığının üstündeki öğe, ziyaret edilenler listesine eklenmelidir.
3. Bu köşenin bitişik düğümlerinin bir listesini yapın ve ziyaret edilenler listesinde olmayanları yığının üstüne ekleyin.
4. Yığın boşalana kadar önceki adımları tekrarlamaya devam edin.

DFS siparişi

Köşe sıralamaları: DFS'de bir grafiğin veya ağacın köşelerini doğrusal olarak sıralamanın dört yolu vardır:

1. DFS algoritması tarafından ilk nasıl ziyaret edildiklerini düzenleyen köşelerin listesi, ön sipariş olarak bilinir. Aramanın ilerlemesini açıklamanın kısa bir yoludur.
2. Algoritma tarafından en son ziyaret edildikleri sıraya göre köşelerin listesi, sipariş sonrası olarak bilinir.
3. İlk ziyaretlerinin karşısındaki sıradaki köşelerin listesi, ters bir ön sipariştir. Bu nedenle, sonradan sipariş vermekle karıştırılmamalıdır.
4. Son ziyaretlerinin karşısındaki sıradaki köşelerin listesi, sıranın tersidir. Ön sipariş vermekle karıştırılmamalıdır.

Ek olarak, ikili ağaçlar için sıralı ve ters sıralama vardır.

Bir Grafik için Derinlik İlk Arama veya DFS

Bir grafiğin DFS'si, bir ağacın DFS'si ile hemen hemen aynıdır. Tek fark, ağaçların aksine grafiklerin döngüleri olabilir. Bir düğüm birden çok kez ziyaret edilebilir ve düğümün işlenmesini önlemek için bir Boole tarafından ziyaret edilen dizi kullanılır.

Derinlik İlk Aramanın Çıktısı

Derinlik öncelikli arama, aramada halihazırda ulaşılan köşelerin yayılan ağacı açısından daha kolay tasvir edilir. Bu yayılan ağaca dayanarak, orijinal grafik kenarları üç sınıfa ayrılır: ağacın düğümünün altlarından birine işaret ettiği ön kenarlar, düğümün atalarından birine işaret ettiği arka kenarlar ve çapraz kenarlar. , önceki işlevlerden hiçbirini yapmaz.

Derinlik İlk Geçiş (DFS) Uygulamaları

Derinlik öncelikli arama, aşağıdaki algoritmalarda bir yapı taşı olarak kullanılır:

• Bağlı bileşenler aranıyor.
• 2-(köşe veya kenar) bağlantılı bileşenleri bulma.
• Grafiğin köprülerini bulma.
• 3-(köşe veya kenar) bağlantılı bileşenleri bulma.
• Topolojik sıralama.
• Güçlü bir şekilde bağlantılı bileşenleri bulma.
• Bir türün filogenetik bir ağaçtaki bir türe mi yoksa başka bir türe mi benzediğini bulmak.
• Düzlemsellik testi.
• Herhangi bir grubun limit setini belirlemek için kelimeler üretmek.
• Labirent gibi tek çözümü olan bulmacaları çözmek.
• Labirent üretimi .
• Grafiklerde ikili bağlantı aranıyor.

Python'da DFS Sözde Kodu ve Uygulaması

init() işlevi, tüm köşelerin ziyaret edildiğinden emin olmak için aşağıdaki sözde koddaki her düğümde çalıştırılır. Bu, grafiklerde birbiriyle bağlantısız çeşitli alanlar olabileceğinden özellikle önemlidir.

İşte sözde kod:

DFS(G, u)

u.ziyaret edilen = doğru

her v ∈ G.Adj[u] için

v.ziyaret edildiyse == yanlış

DFS(G,v)

içinde() {

Her u için ∈ G

u.ziyaret edilen = yanlış

Her u için ∈ G

DFS(G, u)

}

İşte Python'daki DFS uygulaması:

grafik = {

'5' : ['3','7'],

'2' : ['1', '3'],

'6' : ['7'],

'3' : [],

'4' : ['6'],

'7' : []

}

ziyaret edildi = set()

def dfs(ziyaret edildi, grafik, düğüm):

düğüm ziyaret edilmemişse:

yazdır (düğüm)

ziyaret edildi.add(düğüm)

[düğüm] grafiğindeki komşu için:

dfs(ziyaret edildi, grafik, komşu)

print(“Bu, DFS:”)

dfs(ziyaret edildi, grafik, '5')

Çıktı:

Bu DFS: 5

Popüler Yazılım Mühendisliği Kurslarımızı keşfedin

Derinlik İlk Aramanın karmaşıklığı

John Reif, Derinlik İlk Arama'nın hesaplama karmaşıklığını araştırdı. Kesin olmak gerekirse, bir grafikte verilen gerçek G'dir, O, tekrarlayan DFS algoritması tarafından belirlenen standart sıra olsun. G grafiği, O ise yedekli DFS algoritmasının sıralama çıktısını temsil eder. Bu çıktı, sözlükbilimsel DFS sıralaması olarak bilinir.

Çözüm

DFS algoritmasının temel amacı, hedef grafiklerdeki döngüleri önleyen her bir köşeyi ziyaret etmektir. Arama operasyonları veya sipariş operasyonlarının gelişmiş uygulamalarına dahil olmak istiyorsanız, kesinlikle Derinlik İlk Arama ve Veri Yapısı konusunda premium ve bütünsel bir kurs izlemeyi düşünmelisiniz.

upGrad , Bilgisayar Bilimlerinde Yüksek Lisans ve Büyük Veride Uzmanlaşma gibi bazı üst düzey DFS kurslarına sahiptir .

Bir sonraki adımınızı atmakta zorlanıyorsanız ve uzman tavsiyesi arıyorsanız, upGrad Mentorluk size sektördeki en iyi kariyer danışmanları ve uzmanlarıyla bire bir seanslar sunmayı amaçlamaktadır.