В тази статия ще обсъдим DFS алгоритъма в структурата на данните. Това е рекурсивен алгоритъм за търсене във всички върхове на дървовидна структура от данни или графика. Алгоритъмът за първо търсене в дълбочина (DFS) започва с началния възел на графика G и отива по-дълбоко, докато намерим целевия възел или възела без деца.
Поради рекурсивния характер структурата на данните на стека може да се използва за прилагане на DFS алгоритъма. Процесът на внедряване на DFS е подобен на алгоритъма BFS.
Процесът стъпка по стъпка за внедряване на обхождането на DFS е даден, както следва -
- Първо, създайте стек с общия брой върхове в графиката.
- Сега изберете който и да е връх като начална точка на обхождане и натиснете този връх в стека.
- След това натиснете непосетен връх (в съседство с върха в горната част на стека) към върха на стека.
- Сега повторете стъпки 3 и 4, докато не останат върхове за посещение от върха на върха на стека.
- Ако не е останал връх, върнете се и извадете връх от стека.
- Повторете стъпки 2, 3 и 4, докато стекът се изпразни.
Приложения на DFS алгоритъм
Приложенията за използване на алгоритъма DFS са дадени както следва -
- DFS алгоритъмът може да се използва за реализиране на топологично сортиране.
- Може да се използва за намиране на пътищата между два върха.
- Може да се използва и за откриване на цикли в графиката.
- Алгоритъмът DFS се използва и за пъзели с едно решение.
- DFS се използва за определяне дали една графика е двустранна или не.
Алгоритъм
Етап 1: SET STATUS = 1 (състояние на готовност) за всеки възел в G
strint към вътр
Стъпка 2: Натиснете началния възел A в стека и задайте неговия СТАТУТ = 2 (състояние на изчакване)
Стъпка 3: Повторете стъпки 4 и 5, докато STACK се изпразни
Стъпка 4: Извадете горния възел N. Обработете го и задайте неговия СТАТУТ = 3 (обработено състояние)
Стъпка 5: Избутайте в стека всички съседи на N, които са в състояние на готовност (чийто СТАТУТ = 1) и задайте техния СТАТУТ = 2 (състояние на изчакване)
[КРАЙ НА ЦИКЪЛА]
Стъпка 6: ИЗХОД
байтов масив към низ java
Псевдокод
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 алгоритъм
Сега нека разберем работата на DFS алгоритъма, като използваме пример. В примера, даден по-долу, има насочен граф със 7 върха.
Сега нека започнем да изследваме графиката, започвайки от възел H.
Етап 1 - Първо бутнете H върху стека.
за цикъл в скрипта на обвивката
STACK: H
Стъпка 2 - Извадете горния елемент от стека, т.е. H, и го отпечатайте. Сега PUSH всички съседи на H в стека, които са в състояние на готовност.
Print: H]STACK: A
Стъпка 3 - Извадете горния елемент от стека, т.е. A, и го отпечатайте. Сега PUSH всички съседи на A в стека, които са в състояние на готовност.
Print: A STACK: B, D
Стъпка 4 - Извадете горния елемент от стека, т.е. D, и го отпечатайте. Сега PUSH всички съседи на D в стека, които са в състояние на готовност.
Print: D STACK: B, F
Стъпка 5 - Извадете горния елемент от стека, т.е. F, и го отпечатайте. Сега PUSH всички съседи на F в стека, които са в състояние на готовност.
Print: F STACK: B
Стъпка 6 - Извадете горния елемент от стека, т.е. B, и го отпечатайте. Сега, PUSH всички съседи на B в стека, които са в състояние на готовност.
Print: B STACK: C
Стъпка 7 - Извадете горния елемент от стека, т.е. C, и го отпечатайте. Сега PUSH всички съседи на C в стека, които са в състояние на готовност.
plsql
Print: C STACK: E, G
Стъпка 8 - POP горния елемент от стека, т.е. G и PUSH всички съседи на G в стека, които са в състояние на готовност.
Print: G STACK: E
Стъпка 9 - POP горния елемент от стека, т.е. E и PUSH всички съседи на E върху стека, които са в състояние на готовност.
Print: E STACK:
Сега всички възли на графиката са преминати и стекът е празен.
Сложност на алгоритъма за търсене в дълбочина
Времевата сложност на DFS алгоритъма е O(V+E) , където V е броят на върховете, а E е броят на ръбовете в графиката.
Пространствената сложност на DFS алгоритъма е O(V).
Внедряване на DFS алгоритъм
Сега нека видим изпълнението на DFS алгоритъма в Java.
В този пример графиката, която използваме, за да демонстрираме кода, е дадена по следния начин -
/*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;>