Bu yazımızda veri yapısında DFS algoritmasını ele alacağız. Bir ağaç veri yapısının veya bir grafiğin tüm köşelerini aramak için özyinelemeli bir algoritmadır. Derinlik öncelikli arama (DFS) algoritması, G grafiğinin ilk düğümüyle başlar ve hedef düğümü veya çocuğu olmayan düğümü bulana kadar daha derine gider.
Özyinelemeli doğası nedeniyle, yığın veri yapısı DFS algoritmasını uygulamak için kullanılabilir. DFS'yi uygulama süreci BFS algoritmasına benzer.
ravel python'da ne yapar
DFS geçişini uygulamaya yönelik adım adım süreç şu şekilde verilmiştir:
- Öncelikle grafikteki toplam köşe sayısını içeren bir yığın oluşturun.
- Şimdi geçişin başlangıç noktası olarak herhangi bir köşeyi seçin ve bu köşeyi yığının içine itin.
- Bundan sonra, ziyaret edilmeyen bir köşeyi (yığın üstündeki köşeye bitişik) yığının en üstüne itin.
- Şimdi, yığının tepesindeki köşeden ziyaret edilecek köşe kalmayıncaya kadar 3. ve 4. adımları tekrarlayın.
- Hiçbir köşe kalmamışsa geri dönün ve yığından bir köşe noktası açın.
- Yığın boşalana kadar 2, 3 ve 4. adımları tekrarlayın.
DFS algoritmasının uygulamaları
DFS algoritmasının kullanıldığı uygulamalar şu şekilde verilmiştir:
- Topolojik sıralamayı uygulamak için DFS algoritması kullanılabilir.
- İki köşe arasındaki yolları bulmak için kullanılabilir.
- Grafikteki döngüleri tespit etmek için de kullanılabilir.
- DFS algoritması tek çözümlü bulmacalar için de kullanılır.
- DFS, bir grafiğin iki parçalı olup olmadığını belirlemek için kullanılır.
Algoritma
Aşama 1: SET STATUS = 1 (hazır durum), G'deki her düğüm için
Adım 2: Yığındaki başlangıç düğümü A'yı itin ve STATUS = 2'ye (bekleme durumu) ayarlayın
Aşama 3: STACK boşalana kadar 4. ve 5. Adımları tekrarlayın
Adım 4: Üst düğüm N'yi açın. İşleyin ve DURUM = 3'e (işlenmiş durum) ayarlayın
Adım 5: N'nin hazır durumdaki (STATUS = 1) tüm komşularını yığına itin ve STATUS = 2'yi (bekleme durumu) ayarlayın
[DÖNGÜ SONU]
Adım 6: ÇIKIŞ
Python'un boyutu
Sahte kod
DFS(G,v) ( v is the vertex where the search starts ) Stack S := {}; ( start with an empty stack ) for each vertex u, set visited[u] := false; push S, v; while (S is not empty) do u := pop S; if (not visited[u]) then visited[u] := true; for each unvisited neighbour w of uu push S, w; end if end while END DFS() DFS algoritması örneği
Şimdi bir örnek kullanarak DFS algoritmasının çalışmasını anlayalım. Aşağıdaki örnekte 7 köşesi olan yönlü bir grafik bulunmaktadır.
Şimdi H düğümünden başlayarak grafiği incelemeye başlayalım.
Aşama 1 - İlk önce H'yi yığının üzerine itin.
yuvarlak matematik java
STACK: H
Adım 2 - Yığındaki en üstteki öğeyi, yani H'yi POP yapın ve yazdırın. Şimdi, H'nin tüm komşularını hazır durumdaki yığına PUSH edin.
Print: H]STACK: A
Aşama 3 - Yığındaki en üstteki öğeyi, yani A'yı POP yapın ve yazdırın. Şimdi, A'nın hazır durumdaki tüm komşularını yığının üzerine PUSH edin.
Print: A STACK: B, D
4. Adım - Yığındaki en üstteki öğeyi, yani D'yi POP yapın ve yazdırın. Şimdi, D'nin tüm komşularını hazır durumdaki yığına PUSH edin.
Print: D STACK: B, F
Adım 5 - Yığındaki en üstteki öğeyi, yani F'yi POP yapın ve yazdırın. Şimdi, F'nin tüm komşularını hazır durumdaki yığına PUSH edin.
Print: F STACK: B
Adım 6 - Yığındaki en üstteki öğeyi, yani B'yi POP yapın ve yazdırın. Şimdi, B'nin tüm komşularını hazır durumdaki yığının üzerine PUSH edin.
Print: B STACK: C
Adım 7 - Yığındaki en üstteki öğeyi, yani C'yi POP yapın ve yazdırın. Şimdi, C'nin tüm komşularını hazır durumdaki yığının üzerine PUSH yapın.
Print: C STACK: E, G
Adım 8 - Yığındaki en üstteki öğeyi POP, yani G'yi POP yapın ve G'nin hazır durumdaki tüm komşularını yığının üzerine itin.
Print: G STACK: E
9. Adım - Yığındaki en üstteki öğeyi POP yapın, yani E ve E'nin hazır durumdaki tüm komşularını yığının üzerine itin.
Print: E STACK:
Artık tüm grafik düğümleri geçilmiştir ve yığın boştur.
gri kod
Derinlik öncelikli arama algoritmasının karmaşıklığı
DFS algoritmasının zaman karmaşıklığı Ç(V+E) Burada V, grafikteki köşelerin sayısı ve E, grafikteki kenarların sayısıdır.
DFS algoritmasının uzay karmaşıklığı O(V)'dir.
DFS algoritmasının uygulanması
Şimdi DFS algoritmasının Java'daki uygulamasını görelim.
Bu örnekte kodu göstermek için kullandığımız grafik şu şekilde verilmiştir:
/*A sample java program to implement the DFS algorithm*/ import java.util.*; class DFSTraversal { private LinkedList adj[]; /*adjacency list representation*/ private boolean visited[]; /* Creation of the graph */ DFSTraversal(int V) /*'V' is the number of vertices in the graph*/ { adj = new LinkedList[V]; visited = new boolean[V]; for (int i = 0; i <v; i++) adj[i]="new" linkedlist(); } * adding an edge to the graph void insertedge(int src, int dest) { adj[src].add(dest); dfs(int vertex) visited[vertex]="true;" *mark current node as visited* system.out.print(vertex + ' '); iterator it="adj[vertex].listIterator();" while (it.hasnext()) n="it.next();" if (!visited[n]) dfs(n); public static main(string args[]) dfstraversal dfstraversal(8); graph.insertedge(0, 1); 2); 3); graph.insertedge(1, graph.insertedge(2, 4); graph.insertedge(3, 5); 6); graph.insertedge(4, 7); graph.insertedge(5, system.out.println('depth first traversal for is:'); graph.dfs(0); < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/28/dfs-algorithm-3.webp" alt="DFS algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the depth-first search technique, its example, complexity, and implementation in the java programming language. Along with that, we have also seen the applications of the depth-first search algorithm.</p> <p>So, that's all about the article. Hope it will be helpful and informative to you.</p> <hr></v;>