Пошук по глибині: Посібник з обходу графіків DFS із 6 прикладами Leetcode

Ви коли-небудь вирішували реальний лабіринт? Підхід, який використовує більшість із нас під час розв’язання лабіринту, полягає в тому, що ми йдемо шляхом, поки не дійдемо до глухого кута, а потім повернемося назад і пройдемо по своїх кроках, щоб знайти інший можливий шлях.

Це саме така аналогія пошуку глибини (DFS). Це популярний алгоритм обходу графіків, який починається з кореневого вузла і проходить так далеко, наскільки це можливо, по даній гілці, а потім повертається назад, поки не знайде ще один незвіданий шлях для дослідження. Цей підхід продовжується до тих пір, поки не будуть відвідані всі вузли графіка.

У сьогоднішньому підручнику ми збираємось відкрити шаблон DFS, який буде використаний для вирішення деяких важливих питань щодо дерева та графіків для вашого наступного інтерв’ю Tech Giant! Ми будемо вирішувати деякі середні та тверді завдання Leetcode, використовуючи одну і ту ж загальну техніку.

Отже, давайте почнемо, чи не так?

Впровадження

Оскільки DFS має рекурсивний характер, він може бути реалізований за допомогою стека.

Чарівний заклинання DFS:

  1. Просуньте вузол до стека
  2. Поп вузол
  3. Отримати невідвіданих сусідів видаленого вузла, підштовхнути їх до стеку
  4. Повторюйте кроки 1, 2 та 3, доки стек не буде порожнім

Обхід графіків

Загалом для бінарних дерев існує 3 основних обходу DFS:

  1. Попереднє замовлення: корінь, ліворуч, праворуч АБО корінь, праворуч, ліворуч
  2. Оформити замовлення: вліво, вправо, корінь АБО вправо, вліво, корінь
  3. По порядку: ліворуч, корінь, праворуч АБО праворуч, корінь, ліворуч

144. Обхід попереднього замовлення двійкового дерева (складність: середня)

Щоб вирішити це питання, нам потрібно лише згадати наш магічний заклинання. Давайте розберемося в моделюванні дуже добре, оскільки це основний шаблон, який ми будемо використовувати для вирішення решти проблем.

Спочатку ми засовуємо кореневий вузол у стек. Поки стек не порожній, ми висуваємо його та засовуємо його праву та ліву дочірню частину в стек.

Коли ми виводимо кореневий вузол, ми негайно поміщаємо його в наш список результатів. Таким чином, першим елементом у списку результатів є корінь (звідси і назва, попереднє замовлення).

Наступним елементом, що вискакується зі стека, буде верхній елемент стека прямо зараз: лівий дочірній елемент кореневого вузла. Процес продовжується аналогічним чином, поки весь графік не буде пройдений, і всі значення вузлів двійкового дерева не увійдуть до отриманого списку.

145. Обхід бінарного дерева після замовлення (Складність: важко)

Обхід попереднього замовлення виконується коренем ліворуч-праворуч , а після замовлення - праворуч-ліворуч . Це означає, що обхід після замовлення - це якраз реверс обходу перед замовленням.

Отже, одне з рішень, яке може зараз прийти мені на думку, - просто змінити отриманий масив обходу попереднього замовлення. Але подумайте - це обійдеться O (n) складності часу, щоб змінити його.

Більш розумне рішення - скопіювати та вставити точний код обходу попереднього замовлення, але розмістити результат у верхній частині зв’язаного списку (індекс 0) на кожній ітерації. Додавання елемента в заголовок пов’язаного списку займає постійний час. Класно, правда?

94. Обхід бінарного дерева в порядку (складність: середній)

Наш підхід до вирішення цієї проблеми подібний до попередніх. Але тут ми відвідаємо все з лівого боку вузла, надрукуємо вузол, а потім відвідаємо все, що знаходиться з правого боку вузла.

323. Кількість підключених компонентів у неорієнтованому графіку

(Складність: середня)

Наш підхід полягає у створенні змінної з назвою ans, яка зберігає кількість підключених компонентів.

По-перше, ми ініціалізуємо всі вершини як невідвідані. Ми почнемо з вузла, і, виконуючи DFS на цьому вузлі (звичайно, використовуючи наше магічне заклинання), він позначить усі вузли, підключені до нього, як відвідані. Значення ans буде збільшено на 1.

 import java.util.ArrayList; import java.util.List; import java.util.Stack; public class NumberOfConnectedComponents { public static void main(String[] args){ int[][] edge = {{0,1}, {1,2},{3,4}}; int n = 5; System.out.println(connectedcount(n, edge)); } public static int connectedcount(int n, int[][] edges) { boolean[] visited = new boolean[n]; List[] adj = new List[n]; for(int i=0; i

200. Number of Islands (Difficulty: Medium)

This falls under a general category of problems where we have to find the number of connected components, but the details are a bit tweaked.

Instinctually, you might think that once we find a “1” we initiate a new component. We do a DFS from that cell in all 4 directions (up, down, right, left) and reach all 1’s connected to that cell. All these 1's connected to each other belong to the same group, and thus, our value of count is incremented by 1. We mark these cells of 1's as visited and move on to count other connected components.

Original text


547. Friend Circles (Difficulty: Medium)

This also follows the same concept as finding the number of connected components. In this question, we have an NxN matrix but only N friends in total. Edges are directly given via the cells so we have to traverse a row to get the neighbors for a specific "friend".

Notice that here, we use the same stack pattern as our previous problems.

That's all for today! I hope this has helped you understand DFS better and that you have enjoyed the tutorial. Please recommend this post if you think it may be useful for someone else!