Дълбочина първо търсене: Ръководство за обхождане на графика DFS с 6 примера за Leetcode

Решавали ли сте някога реалния лабиринт? Подходът, който повечето от нас предприемат, докато решават лабиринт, е, че следваме път, докато стигнем до задънена улица, а след това се връщаме и проследяваме стъпките си, за да намерим друг възможен път.

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

В днешния урок ще открием модел на DFS, който ще се използва за решаване на някои от важните въпроси за дървото и графиката за следващото ви интервю за Tech Giant! Ще разрешим някои средни и твърди проблеми с Leetcode, използвайки същата често срещана техника.

И така, нека започнем, нали?

Изпълнение

Тъй като DFS има рекурсивен характер, той може да бъде реализиран с помощта на стек.

DFS Magic Spell:

  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!