Какво е BFS?
BFS е алгоритъм, който се използва за графика на данни или търсене в дърво или обхождане на структури. Алгоритъмът ефективно посещава и маркира всички ключови възли в графика по точен начин.
Този алгоритъм избира един възел (начална или изходна точка) в графика и след това посещава всички възли, съседни на избрания възел. След като алгоритъмът посети и маркира началния възел, той се придвижва към най-близките непосетени възли и ги анализира.
Веднъж посетени, всички възли са маркирани. Тези повторения продължават, докато всички възли на графиката бъдат успешно посетени и маркирани. Пълната форма на BFS е търсенето с ширина първо.
В този BSF Vs. DFS Binary tree tutorial, ще научите:
- Какво е BFS?
- Какво е DFS?
- Пример за BFS
- Пример за DFS
- Разлика между BFS и DFS двоично дърво
- Приложения на BFS
- Приложения на DFS
Какво е DFS?
DFS е алгоритъм за намиране или обхождане на графики или дървета в посока към дълбочината. Изпълнението на алгоритъма започва от кореновия възел и изследва всеки клон преди обратното проследяване. Той използва структура от данни на стека, за да запомни, да получи следващия връх и да започне търсене, когато се появи задънена улица във всяка итерация. Пълната форма на DFS е търсене с дълбочина първо.
Пример за BFS
В следващия пример за DFS използвахме графика с 6 върха.
Пример за BFS
Етап 1)
Имате графика от седем числа, вариращи от 0 - 6.
Стъпка 2)
0 или нула е маркирана като основен възел.
Стъпка 3)
0 се посещава, маркира и вмъква в структурата на данните за опашката.
Стъпка 4)
Останалите 0 съседни и непосетени възли се посещават, маркират и вмъкват в опашката.
Стъпка 5)
Преминаващите се итерации се повтарят, докато не бъдат посетени всички възли.
Пример за DFS
В следващия пример за DFS използваме ненасочена графика с 5 върха.
Етап 1)
Започнахме от връх 0. Алгоритъмът започва, като го поставя в посетения списък и едновременно поставя всички съседни върхове в структурата на данните, наречена стек.
Стъпка 2)
Ще посетите елемента, който е в горната част на стека, например 1, и ще преминете към съседните му възли. Това е така, защото 0 вече е посетен. Следователно посещаваме връх 2.
Стъпка 3)
Vertex 2 има непосетен близък връх в 4. Затова добавяме това в стека и го посещаваме.
Стъпка 4)
И накрая, ще посетим последния връх 3, той няма непосетени съседни възли. Завършихме обхода на графиката, използвайки DFS алгоритъм.
Разлика между BFS и DFS двоично дърво
| BFS | DFS |
| BFS намира най-краткия път до дестинацията. | DFS отива в дъното на поддърво, след което се връща назад. |
| Пълната форма на BFS е Breadth-First Search. | Пълната форма на DFS е дълбочина първо търсене. |
| Той използва опашка, за да следи следващото място за посещение. | Той използва стек, за да следи следващото място за посещение. |
| BFS преминава според нивото на дървото. | DFS преминава според дълбочината на дървото. |
| Прилага се с помощта на FIFO списък. | Прилага се с помощта на списък LIFO. |
| Изисква повече памет в сравнение с DFS. | Изисква по-малко памет в сравнение с BFS. |
| Този алгоритъм дава най-плиткото решение на пътя. | Този алгоритъм не гарантира най-плиткото решение на пътя. |
| Няма нужда от проследяване в BFS. | Необходимо е обратното проследяване в DFS. |
| Никога не можете да бъдете в капан в крайни цикли. | Можете да бъдете в капан в безкрайни цикли. |
| Ако не намерите цел, може да се наложи да разширите много възли, преди решението да бъде намерено. | Ако не намерите никаква цел, може да възникне обратното проследяване на листния възел. |
Приложения на BFS
Ето приложенията на BFS:
Непретеглени графики:
BFS алгоритъмът може лесно да създаде най-краткия път и минимално обхващащо дърво, за да посети всички върхове на графиката във възможно най-кратко време с висока точност.
P2P мрежи:
BFS може да бъде реализиран за намиране на всички най-близки или съседни възли в равнопоставена мрежа. Това ще намери необходимите данни по-бързо.
Уеб робота:
Търсачките или уеб роботите могат лесно да изграждат множество нива на индекси, като използват BFS. Внедряването на BFS започва от източника, който е уеб страницата, и след това посещава всички връзки от този източник.
Мрежово излъчване:
Излъчваният пакет се ръководи от алгоритъма BFS, за да намери и достигне до всички възли, за които има адреса.
Приложения на DFS
Ето важни приложения на DFS:
Претеглена графика:
В претеглена графика, обхождането на графика DFS генерира дървото с най-краткия път и минималното обхващащо дърво.
Откриване на цикъл в графика:
Графиката има цикъл, ако намерим заден ръб по време на DFS. Следователно трябва да стартираме DFS за графиката и да проверим за задните ръбове.
Намиране на път:
Можем да се специализираме в DFS алгоритъма за търсене на път между два върха.
Топологично сортиране:
Използва се предимно за планиране на задания от дадените зависимости сред групата работни места. В компютърните науки се използва при планиране на инструкции, сериализация на данни, логически синтез, определяне на реда на задачите за компилиране.
Търсене на силно свързани компоненти на графика:
Той се използва в DFS графика, когато има път от всеки връх в графиката до други останали върхове.
Решаване на пъзели само с едно решение:
DFS алгоритъмът може лесно да бъде адаптиран за търсене на всички решения на лабиринт чрез включване на възли по съществуващия път в посетения набор.
КЛЮЧОВИ РАЗЛИКИ:
- BFS намира най-краткия път до местоназначението, докато DFS отива в долната част на поддърво, след което се връща обратно.
- Пълната форма на BFS е търсене с ширина първо, докато пълната форма на DFS е търсене с дълбочина.
- BFS използва опашка, за да следи следващото място за посещение. като има предвид, че DFS използва стек, за да следи следващото място за посещение.
- BFS преминава според нивото на дървото, докато DFS преминава според дълбочината на дървото.
- BFS се прилага чрез списък FIFO, от друга страна DFS се използва чрез списък LIFO.
- В BFS никога не можете да бъдете в капан в крайни цикли, докато в DFS можете да бъдете в капан в безкрайни цикли.