Uvod u DFS algoritam
DFS je poznat i kao algoritam dubine prvog pretraživanja koji osigurava korake za prelazak svakog čvora grafikona bez ponavljanja čvora. Ovaj je algoritam isti kao i prva dubina dubine za stablo, ali razlikuje se u održavanju Boola da provjeri je li čvor već posjećen ili ne. To je važno za presjek grafikona, jer u grafu postoje i ciklusi. Slaganje se održava u ovom algoritmu za spremanje suspendiranih čvorova tijekom prolaska. Nazvan je tako po tome što prvo putujemo do dubine svakog susjednog čvora, a zatim nastavljamo prolaziti drugim susjednim čvorom.
Objasnite DFS algoritam
Ovaj je algoritam suprotan BFS algoritmu gdje se posjećuju svi susjedni čvorovi, a slijede ih susjedi sa susjednim čvorovima. Počinje istraživanje grafikona s jednog čvora i istražuje njegovu dubinu prije vraćanja unazad. Dvije stvari se razmatraju u ovom algoritmu:
- Posjeta kralježnici: odabir vrha ili čvora grafikona za prelazak.
- Istraživanje kralježnice: prelazak svih čvorova uz to.
Prvi pseudo kod za dubinu :
proc DFS_implement(G, v):
let St be a stack
St.push(v)
while St has elements
v = St.pop()
if v is not labeled as visited:
label v as visited
for all edge v to w in G.adjacentEdges(v) do
St.push(w)
Linearni presjek također postoji za DFS koji se može implementirati na 3 načina:
- Predbilježba
- U redu
- PostOrder
Obrnuti postorder je vrlo koristan način za kretanje i koristi se u topološkom razvrstavanju, kao i u različitim analizama. Također se održava snop za pohranu čvorova čije je istraživanje još u tijeku.
Prelaz grafikona u DFS-u
U DFS-u slijede koraci u nastavku za prelazak grafikona. Na primjer, dani grafikon započnimo s kretanjem od 1:
| Stog | Slijed prolaska | Stablo spanning |
| 1 |  |
|
 | 1, 4 |  |
 | 1, 4, 3 |  |
 | 1, 4, 3, 10 |  |
 | 1, 4, 3, 10, 9 |  |
 | 1, 4, 3, 10, 9, 2 |  |
 | 1, 4, 3, 10, 9, 2, 8 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
Objašnjenje DFS algoritma
Ispod su koraci do DFS algoritma s prednostima i nedostacima:
1. korak: Posjećuje se čvor 1 i dodaje se nizu kao i stablu raspona.
Korak 2: Ispituju se susjedni čvorovi od 1 koji je 4, a 1 se gura u snop, a 4 gura u redoslijed, kao i raspoređeno stablo.
Korak: Istražuje se jedan od susjednih čvorova od 4 i tako se 4 gurne u snop, a 3 ulazi u stablo niza i raspona.
4. korak: Susjedni čvorovi od 3 istražuju se pritiskom na snop i 10 ulazi u niz. Kako nema susjednog čvora 10, tako 3 iskoči iz snopa.
Korak 5: Istražuje se drugi susjedni čvor od 3 i 3 se gura na gomilu i 9 se posjećuje. Nije iskočen nijedan susjedni čvor od 9, a posjećuje se posljednji susjedni čvor 3, tj. 2.
Sličan postupak slijedi za sve čvorove dok snop ne postane prazan što ukazuje na uvjet zaustavljanja algoritma za kretanje. - -> isprekidane crte na prostirci odnose se na stražnje rubove prisutne na grafu.
Na taj su način presječeni svi čvorovi na grafikonu bez ponavljanja bilo kojeg od čvorova.
Prednosti i nedostatci
- Prednosti: ovaj memorijski zahtjev za ovaj algoritam je vrlo manji. Manja složenost prostora i vremena u odnosu na BFS.
- Nedostaci: Primjena nije zajamčena. Topološka sortiranje. Pronalaženje mostova grafa.
Primjer za implementaciju DFS algoritma
Ispod je primjer implementacije DFS algoritma:
Kodirati:
import java.util.Stack;
public class DepthFirstSearch (
static void depthFirstSearch(int()() matrix, int source)(
boolean() visited = new boolean (matrix.length);
visited(source-1) = true;
Stack stack = new Stack();
stack.push(source);
int i, x;
System.out.println("Depth of first order is");
System.out.println(source);
while(!stack.isEmpty())(
x= stack.pop();
for(i=0;i if(matrix(x-1)(i) == 1 && visited(i) == false)(
stack.push(x);
visited(i)=true;
System.out.println(i+1);
x=i+1;
i=-1;
)
)
)
)
public static void main(String() args)(
int vertices=5;
int()() mymatrix = new int(vertices)(vertices);
for(int i=0;i for(int j=0;j mymatrix(i)(j)= i+j;
)
)
depthFirstSearch(mymatrix, 5);
)
)import java.util.Stack;
public class DepthFirstSearch (
static void depthFirstSearch(int()() matrix, int source)(
boolean() visited = new boolean (matrix.length);
visited(source-1) = true;
Stack stack = new Stack();
stack.push(source);
int i, x;
System.out.println("Depth of first order is");
System.out.println(source);
while(!stack.isEmpty())(
x= stack.pop();
for(i=0;i if(matrix(x-1)(i) == 1 && visited(i) == false)(
stack.push(x);
visited(i)=true;
System.out.println(i+1);
x=i+1;
i=-1;
)
)
)
)
public static void main(String() args)(
int vertices=5;
int()() mymatrix = new int(vertices)(vertices);
for(int i=0;i for(int j=0;j mymatrix(i)(j)= i+j;
)
)
depthFirstSearch(mymatrix, 5);
)
)import java.util.Stack;
public class DepthFirstSearch (
static void depthFirstSearch(int()() matrix, int source)(
boolean() visited = new boolean (matrix.length);
visited(source-1) = true;
Stack stack = new Stack();
stack.push(source);
int i, x;
System.out.println("Depth of first order is");
System.out.println(source);
while(!stack.isEmpty())(
x= stack.pop();
for(i=0;i if(matrix(x-1)(i) == 1 && visited(i) == false)(
stack.push(x);
visited(i)=true;
System.out.println(i+1);
x=i+1;
i=-1;
)
)
)
)
public static void main(String() args)(
int vertices=5;
int()() mymatrix = new int(vertices)(vertices);
for(int i=0;i for(int j=0;j mymatrix(i)(j)= i+j;
)
)
depthFirstSearch(mymatrix, 5);
)
)import java.util.Stack;
public class DepthFirstSearch (
static void depthFirstSearch(int()() matrix, int source)(
boolean() visited = new boolean (matrix.length);
visited(source-1) = true;
Stack stack = new Stack();
stack.push(source);
int i, x;
System.out.println("Depth of first order is");
System.out.println(source);
while(!stack.isEmpty())(
x= stack.pop();
for(i=0;i if(matrix(x-1)(i) == 1 && visited(i) == false)(
stack.push(x);
visited(i)=true;
System.out.println(i+1);
x=i+1;
i=-1;
)
)
)
)
public static void main(String() args)(
int vertices=5;
int()() mymatrix = new int(vertices)(vertices);
for(int i=0;i for(int j=0;j mymatrix(i)(j)= i+j;
)
)
depthFirstSearch(mymatrix, 5);
)
)
Izlaz:
Objašnjenje gornjeg programa: Napravili smo graf s 5 vrhova (0, 1, 2, 3, 4) i upotrijebili posjećeni niz za praćenje svih posjećenih vrhova. Tada se za svaki čvor čiji susjedni čvorovi postoje isti algoritam ponavlja dok svi čvorovi nisu posjećeni. Tada se algoritam vraća na vertex pozivanja i ubacuje ga iz snopa.
Zaključak
Potrebna memorija ovog grafikona je manja u odnosu na BFS jer je potreban samo jedan snop. DFS rasponsko stablo i redoslijed uspostave generiraju se kao rezultat, ali nije konstantan. Mogući su višestruki presjeci, ovisno o odabranom polaznom i vršku istraživanja.
Preporučeni članci
Ovo je vodič za DFS algoritam. Ovdje ćemo detaljno objasniti objašnjenje, prelistavati graf u obliku tablice s prednostima i nedostacima. Možete i pregledati naše druge povezane članke da biste saznali više -
- Što je HDFS?
- Algoritmi dubokog učenja
- HDFS naredbe
- SHA algoritam
