BFS срещу DFS – Разлика между тях

Какво е BFS?

BFS е алгоритъм, който се използва за графично изобразяване на данни или търсене на дърво или преминаващи структури. Алгоритъмът ефективно посещава и маркира всички ключови възли в графика по точен широк начин.

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

Веднъж посетени, всички възли се маркират. Тези итерации продължават, докато всички възли на графиката бъдат успешно посетени и маркирани. Пълната форма на BFS е търсене в ширина.

Какво е DFS?

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

Разлика между BFS и DFS двоично дърво

Ето важните разлики между BFS и DFS.

BFS	DFS
BFS намира най-краткия път до дестинацията.	DFS отива в дъното на поддърво, след което се връща назад.
Пълната форма на BFS е търсене в ширина.	Пълната форма на DFS е първо търсене в дълбочина.
Той използва опашка, за да следи следващото място за посещение.	Той използва стек, за да следи следващото място за посещение.
BFS преминава според нивото на дървото.	DFS преминава според дълбочината на дървото.
Реализира се чрез FIFO списък.	Реализира се чрез LIFO списък.
Изисква повече памет в сравнение с DFS.	Изисква по-малко памет в сравнение с BFS.
Този алгоритъм дава най-плиткото решение на пътя.	Този алгоритъм не гарантира най-плиткото решение за път.
Няма нужда от обратно проследяване в BFS.	Има нужда от обратно проследяване в DFS.
Никога не можете да бъдете хванати в капан на крайни цикли.	Можете да бъдете хванати в безкрайни цикли.
Ако не намерите никаква цел, може да се наложи да разширите много възли, преди да бъде намерено решението.	Ако не намерите никаква цел, може да възникне обратно проследяване на листния възел.

Пример за BFS

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

Пример за BFS

Стъпка 1)

Имате графика от седем числа, вариращи от 0 до 6.

Стъпка 2)

0 или нула е маркиран като основен възел.

Стъпка 3)

0 се посещава, маркира и вмъква в структурата на данните на опашката.

Стъпка 4)

Останалите 0 съседни и непосетени възли се посещават, маркират и вмъкват в опашката.

Стъпка 5)

Итерациите на преминаване се повтарят, докато се посетят всички възли.

Пример за DFS

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

Стъпка 1)

Започнахме от връх 0. Алгоритъмът започва с поставянето му в посетения списък и едновременно с това поставя всичките му съседни върхове в структура на данни наречен стек.

Стъпка 2)

Ще посетите елемента, който е в горната част на стека, например 1 и ще отидете до съседните му възли. Това е така, защото 0 вече е бил посетен. Затова посещаваме връх 2.

Стъпка 3)

Връх 2 има непосетен близък връх в 4. Следователно добавяме това в стека и го посещаваме.

Стъпка 4)

И накрая, ще посетим последния връх 3, той няма никакви непосетени съседни възли. Завършихме обхождането на графиката с помощта на DFS алгоритъм.

Приложения на BFS

Ето приложенията на BFS:

Непретеглени графики

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

P2P мрежи

BFS може да се внедри за локализиране на всички най-близки или съседни възли в peer to peer мрежа. Това ще намери необходимите данни по-бързо.

Уеб роботи

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

Мрежово излъчване

Излъченият пакет се ръководи от алгоритъма на BFS, за да намери и достигне до всички възли, за които има адреса.

Приложения на DFS

Ето важни приложения на DFS:

Претеглена графика

В претеглена графика обхождането на DFS графика генерира дърво с най-кратък път и минимално обхващащо дърво.

Откриване на цикъл в графика

Една графика има цикъл, ако сме намерили заден край по време на DFS. Следователно трябва да стартираме DFS за графиката и да проверим за задните ръбове.

Намиране на пътя

Можем да се специализираме в алгоритъма DFS за търсене на път между два върха.

Топологично сортиране

Използва се предимно за планиране на задачи от дадените зависимости сред групата задачи. В компютърните науки се използва при планиране на инструкции, сериализиране на данни, логически синтез, определяне на реда на задачите за компилиране.

Търсене на силно свързани компоненти на графика

Използва се в DFS графика, когато има път от всеки връх в графиката до други оставащи върхове.

Решаване на пъзели само с едно решение

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