DFS АЛГОРИТЪМ - УРОК ЗА DS

В тази статия ще обсъдим 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) /*&apos;V&apos; 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&apos;s all about the article. Hope it will be helpful and informative to you.</p> <hr></v;>

TechCodeview

Алгоритъм DFS (първо търсене в дълбочина).