Prima ricerca in profondità in Java

1. Panoramica

In questo tutorial, esploreremo la ricerca Depth-first in Java.

La ricerca in profondità (DFS) è un algoritmo di attraversamento utilizzato per le strutture di dati sia ad albero che a grafo. La ricerca approfondita va in profondità in ogni ramo prima di spostarsi per esplorare un altro ramo .

Nelle sezioni successive, daremo prima uno sguardo all'implementazione per un albero e poi un grafico.

Per vedere come implementare queste strutture in Java, dai un'occhiata ai nostri tutorial precedenti su Binary Tree and Graph.

2. Tree Depth-first Search

Esistono tre diversi ordini per attraversare un albero utilizzando DFS:

  1. Preordina Traversal
  2. Attraversamento in ordine
  3. Postorder Traversal

2.1. Preordina Traversal

In preorder traversal, attraversiamo prima la radice, poi i sottoalberi sinistro e destro.

Possiamo semplicemente implementare l'attraversamento del preordine usando la ricorsione :

  • Visita il nodo corrente
  • Attraversa la sottostruttura sinistra
  • Attraversa la sottostruttura destra
public void traversePreOrder(Node node) { if (node != null) { visit(node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }

Possiamo anche implementare l'attraversamento del preordine senza ricorsione.

Per implementare un attraversamento iterativo del preordine, avremo bisogno di uno Stack e seguiremo questi passaggi:

  • Spingi la radice nella nostra tattica
  • Mentre lo stack non è vuoto
    • Pop corrente nodo
    • Visita il nodo corrente
    • Spingere il bambino a destra , quindi il bambino a sinistra per impilare
public void traversePreOrderWithoutRecursion() { Stack stack = new Stack(); Node current = root; stack.push(root); while(!stack.isEmpty()) { current = stack.pop(); visit(current.value); if(current.right != null) { stack.push(current.right); } if(current.left != null) { stack.push(current.left); } } }

2.2. Attraversamento in ordine

Per l'attraversamento in ordine, attraversiamo prima la sottostruttura sinistra, poi la radice, infine la sottostruttura destra .

Attraversamento in ordine per un albero di ricerca binario significa attraversare i nodi in ordine crescente dei loro valori.

Possiamo semplicemente implementare l'attraversamento inordine usando la ricorsione:

public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); visit(node.value); traverseInOrder(node.right); } }

Possiamo anche implementare inorder traversal senza ricorsione :

  • Spinta radice nodo s tack
  • Mentre s tack non è vuoto
    • Continuare a spingere a sinistra bambino sulla pila, fino a raggiungere corrente più a sinistra del nodo figlio
    • Visita il nodo corrente
    • Spingi il bambino a destra sulla pila
public void traverseInOrderWithoutRecursion() { Stack stack = new Stack(); Node current = root; stack.push(root); while(! stack.isEmpty()) { while(current.left != null) { current = current.left; stack.push(current); } current = stack.pop(); visit(current.value); if(current.right != null) { current = current.right; stack.push(current); } } }

2.3. Postorder Traversal

Infine, nell'attraversamento postordine, attraversiamo la sottostruttura sinistra e destra prima di attraversare la radice .

Possiamo seguire la nostra precedente soluzione ricorsiva :

public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); visit(node.value); } }

Oppure, possiamo anche implementare l'attraversamento postordine senza ricorsione :

  • Spinta radice nodo s tack
  • Mentre s tack non è vuoto
    • Controlla se abbiamo già attraversato la sottostruttura sinistra e destra
    • In caso contrario, spingere il bambino destro e il bambino sinistro sulla pila
public void traversePostOrderWithoutRecursion() { Stack stack = new Stack(); Node prev = root; Node current = root; stack.push(root); while (!stack.isEmpty()) { current = stack.peek(); boolean hasChild = (current.left != null || current.right != null); boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null)); if (!hasChild || isPrevLastChild) { current = stack.pop(); visit(current.value); prev = current; } else { if (current.right != null) { stack.push(current.right); } if (current.left != null) { stack.push(current.left); } } } }

3. Ricerca prima in profondità del grafico

La principale differenza tra grafici e alberi è che i grafici possono contenere cicli .

Quindi, per evitare la ricerca in cicli, contrassegneremo ogni nodo quando lo visiteremo.

We'll see two implementations for graph DFS, with recursion, and without recursion.

3.1. Graph DFS with Recursion

First, let's start simple with recursion:

  • We'll start from a given node
  • Mark current node as visited
  • Visit current node
  • Traverse unvisited adjacent vertices
public void dfs(int start) { boolean[] isVisited = new boolean[adjVertices.size()]; dfsRecursive(start, isVisited); } private void dfsRecursive(int current, boolean[] isVisited) { isVisited[current] = true; visit(current); for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) dfsRecursive(dest, isVisited); } }

3.2. Graph DFS Without Recursion

We can also implement graph DFS without recursion. We'll simply use a Stack:

  • We'll start from a given node
  • Push start node into stack
  • While Stack not empty
    • Mark current node as visited
    • Visit current node
    • Push unvisited adjacent vertices
public void dfsWithoutRecursion(int start) { Stack stack = new Stack(); boolean[] isVisited = new boolean[adjVertices.size()]; stack.push(start); while (!stack.isEmpty()) { int current = stack.pop(); isVisited[current] = true; visit(current); for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) stack.push(dest); } } }

3.4. Topological Sort

There are a lot of applications for graph depth-first search. One of the famous applications for DFS is Topological Sort.

L'ordinamento topologico per un grafo orientato è un ordinamento lineare dei suoi vertici in modo che per ogni bordo il nodo sorgente preceda la destinazione.

Per essere ordinati topologicamente, avremo bisogno di una semplice aggiunta al DFS che abbiamo appena implementato:

  • Dobbiamo mantenere i vertici visitati in uno stack perché l'ordinamento topologico è i vertici visitati in ordine inverso
  • Inseriamo il nodo visitato nello stack solo dopo aver attraversato tutti i suoi vicini
public List topologicalSort(int start) { LinkedList result = new LinkedList(); boolean[] isVisited = new boolean[adjVertices.size()]; topologicalSortRecursive(start, isVisited, result); return result; } private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedList result) { isVisited[current] = true; for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) topologicalSortRecursive(dest, isVisited, result); } result.addFirst(current); }

4. Conclusione

In questo articolo, abbiamo discusso la ricerca approfondita per le strutture dati Tree e Graph.

Il codice sorgente completo è disponibile su GitHub.