Дълбочина Първо търсене в Java

1. Общ преглед

В този урок ще проучим търсенето с дълбочина първо в Java.

Търсенето с дълбочина първо (DFS) е алгоритъм за обхождане, използван както за структурите на данни за дърво, така и за графика. Търсенето с дълбочина първо се задълбочава във всеки клон, преди да се премести да изследва друг клон .

В следващите раздели първо ще разгледаме изпълнението на дърво и след това графика.

За да видите как да внедрите тези структури в Java, разгледайте предишните ни уроци за двоично дърво и графика.

2. Дърво дълбочина първо търсене

Има три различни реда за обхождане на дърво с помощта на DFS:

  1. Обръщане на предварителна поръчка
  2. Вътрешно обръщане
  3. Обръщане след поръчка

2.1. Обръщане на предварителна поръчка

При обръщане на предварителни поръчки първо обхождаме корена, след това лявото и дясното поддървета.

Можем просто да реализираме обръщане на предварителна поръчка, използвайки рекурсия :

  • Посетете текущия възел
  • Преместете лявото поддърво
  • Преминаване от дясно поддърво
public void traversePreOrder(Node node) { if (node != null) { visit(node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }

Също така можем да реализираме обръщане на предварителна поръчка без рекурсия.

За да приложим итеративно обръщане на предварителна поръчка, ще ни е необходим стек и ще преминем през тези стъпки:

  • Натиснете корен в нашето прилепване
  • Докато стекът не е празен
    • Поп текущ възел
    • Посетете текущия възел
    • Бутнете дясно дете, след това ляво дете, за да стекате
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. Вътрешно обръщане

За вътрешно обхождане първо обхождаме лявото поддърво, след това корен, след което накрая дясното поддърво .

Inorder обход за двоично дърво за търсене означава обхождане на възлите в нарастващ ред на техните стойности.

Можем просто да приложим обръщане в ред, като използваме рекурсия:

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

Също така можем да внедрим обръщане в ред без рекурсия :

  • Push корен възел да е халс
  • Докато s tack не е празен
    • Продължавайте да натискате лявото дете върху стека, докато стигнем до най- лявото дете на текущия възел
    • Посетете текущия възел
    • Избутайте дясното дете върху стека
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. Обръщане след поръчка

И накрая, при обръщане след поръчка, ние обхождаме лявото и дясното поддърво, преди да прекосим корена .

Можем да следваме предишното ни рекурсивно решение :

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

Или можем да реализираме обръщане след поръчка без рекурсия :

  • Натиснете коренния възел в s tack
  • Докато s tack не е празен
    • Проверете дали вече сме преминали през ляво и дясно поддърво
    • В противен случай натиснете дясното и лявото дете върху стека
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. Търсене на дълбочина на графиката

Основната разлика между графиките и дърветата е, че графиките могат да съдържат цикли .

Така че, за да избегнем търсене в цикли, ще маркираме всеки възел, когато го посетим.

Ще видим две реализации за DFS на графика, с рекурсия и без рекурсия.

3.1. Графирайте DFS с рекурсия

Първо, нека започнем просто с рекурсия:

  • Ще започнем от даден възел
  • Маркирайте текущия възел като посетен
  • Посетете текущия възел
  • Прекоси непосетени съседни върхове
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. Графирайте DFS без рекурсия

Също така можем да внедрим DFS на графика без рекурсия. Ние просто ще използваме Stack :

  • Ще започнем от даден възел
  • Натиснете стартовия възел в стека
  • Докато стекът не е празен
    • Маркирайте текущия възел като посетен
    • Посетете текущия възел
    • Натиснете непосетени съседни върхове
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. Топологично сортиране

Има много приложения за търсене на дълбочина на графиката. Едно от известните приложения за DFS е Топологично сортиране.

Топологичното сортиране за насочена графика е линейно подреждане на нейните върхове, така че за всеки ръб изходният възел да идва преди местоназначението.

За да получим топологично сортиране, ще ни трябва просто допълнение към DFS, което току-що внедрихме:

  • Трябва да държим посетените върхове в стек, защото топологичното сортиране е посетените върхове в обратен ред
  • Притискаме посетения възел към стека само след обхождане на всички негови съседи
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. Заключение

В тази статия обсъдихме първоначалното търсене както за структурата на данните Tree, така и за Graph.

Пълният изходен код е достъпен на GitHub.