Introduzione all'algoritmo DFS

DFS è noto come algoritmo di ricerca della prima profondità che fornisce i passaggi per attraversare ogni singolo nodo di un grafico senza ripetere alcun nodo. Questo algoritmo è lo stesso di Depth First Traversal per un albero ma differisce nel mantenere un valore booleano per verificare se il nodo è già stato visitato o meno. Questo è importante per l'attraversamento del grafico, poiché nel grafico esistono anche dei cicli. In questo algoritmo viene mantenuto uno stack per memorizzare i nodi sospesi durante l'attraversamento. È chiamato così perché prima viaggiamo fino alla profondità di ciascun nodo adiacente e quindi continuiamo a percorrere un altro nodo adiacente.

Spiega l'algoritmo DFS

Questo algoritmo è contrario all'algoritmo BFS in cui sono visitati tutti i nodi adiacenti seguiti dai vicini ai nodi adiacenti. Inizia a esplorare il grafico da un nodo e ne esplora la profondità prima di tornare indietro. Due cose sono considerate in questo algoritmo:

  • Visitare un vertice: selezione di un vertice o nodo del grafico da attraversare.
  • Esplorazione di un vertice: attraversare tutti i nodi adiacenti a quel vertice.

Pseudo codice per la prima ricerca della profondità :

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)

Traversal lineare esiste anche per DFS che può essere implementato in 3 modi:

  • Preordinare
  • In ordine
  • postorder

Il postordine inverso è un modo molto utile per attraversare e utilizzare l'ordinamento topologico e varie analisi. Viene inoltre gestito uno stack per memorizzare i nodi la cui esplorazione è ancora in sospeso.

Traversa del grafico in DFS

In DFS, i passaggi seguenti sono seguiti per attraversare il grafico. Ad esempio, un dato grafico, iniziamo l'attraversamento da 1:

Pila Sequenza trasversale Spanning Tree
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

Spiegazione dell'algoritmo DFS

Di seguito sono riportati i passaggi per l'algoritmo DFS con vantaggi e svantaggi:

Step1: Il nodo 1 viene visitato e aggiunto alla sequenza e all'albero di spanning.

Step2: Vengono esplorati i nodi adiacenti di 1 che è 4, quindi 1 viene spinto per impilare e 4 viene spinto nella sequenza, oltre a spanning tree.

Step3: viene esplorato uno dei nodi adiacenti di 4 e quindi 4 viene spinto nella pila e 3 entra nella sequenza e si estende sull'albero.

Step4: I nodi adiacenti di 3 vengono esplorati spingendolo sullo stack e 10 entra nella sequenza. Poiché non esiste un nodo adiacente a 10, quindi 3 viene estratto dallo stack.

Passaggio 5: viene esplorato un altro nodo adiacente di 3 e 3 viene inserito nello stack e viene visitato 9. Nessun nodo adiacente di 9 quindi 3 viene espulso e viene visitato l'ultimo nodo adiacente di 3 cioè 2.

Un processo simile è seguito per tutti i nodi fino a quando lo stack diventa vuoto, il che indica la condizione di arresto per l'algoritmo di attraversamento. - -> le linee tratteggiate nella struttura ad albero si riferiscono ai bordi posteriori presenti nel grafico.

In questo modo, tutti i nodi nel grafico vengono attraversati senza ripetere nessuno dei nodi.

Vantaggi e svantaggi

  • Vantaggi: i requisiti di memoria per questo algoritmo sono molto inferiori. Minore complessità in termini di spazio e tempo rispetto a BFS.
  • Svantaggi: la soluzione non è garantita Applicazioni. Ordinamento topologico. Trovare ponti di grafico.

Esempio per implementare l'algoritmo DFS

Di seguito è riportato l'esempio per implementare l'algoritmo DFS:

Codice:

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);
)
)

Produzione:

Spiegazione del programma precedente: Abbiamo creato un grafico con 5 vertici (0, 1, 2, 3, 4) e abbiamo usato l'array visitato per tenere traccia di tutti i vertici visitati. Quindi per ogni nodo i cui nodi adiacenti esistono lo stesso algoritmo si ripete fino a quando tutti i nodi sono visitati. Quindi l'algoritmo torna a chiamare il vertice e pop dallo stack.

Conclusione

Il requisito di memoria di questo grafico è inferiore rispetto a BFS in quanto è necessario mantenere solo uno stack. Di conseguenza viene generato un albero spanning DFS e una sequenza di attraversamento ma non è costante. La sequenza di attraversamento multiplo è possibile a seconda del vertice iniziale e del vertice di esplorazione scelti.

Articoli consigliati

Questa è una guida all'algoritmo DFS. Qui discutiamo passo passo della spiegazione, attraversiamo il grafico in un formato tabella con vantaggi e svantaggi. Puoi anche consultare i nostri altri articoli correlati per saperne di più -

  1. Che cos'è HDFS?
  2. Algoritmi di apprendimento profondo
  3. Comandi HDFS
  4. Algoritmo SHA

Categoria: