Разлика между BFS VS DFS
Първо търсене на ширина (BFS) и първо търсене на дълбочина (DFS) са два важни алгоритъма, използвани за търсене. Първото търсене на широта започва от първото възел и след това се премества през нивата, които са по-близо до кореновия възел, докато алгоритъмът за дълбоко търсене на дълбочина започва с първия възел и след това завършва пътя си до крайния възел на съответния път. И двата алгоритъма преминават през всеки възел по време на търсенето. За двата алгоритъма са написани различни кодове за изпълнение на процеса на преминаване. Те също се считат за важни алгоритми за търсене в изкуствения интелект.
В тази тема ще научим за BFS VS DFS.
Как работят BFS и DFS?
Работният механизъм на двата алгоритъма е обяснен по-долу с примери. Моля, обърнете се към тях за по-добро разбиране на използвания подход.
Пример за първо търсене на широчина
- Стъпка 1: N1 е коренният възел, така че ще започне от тук. N1 е свързан с три възли N2, N3 и N4. И трите възли все още не са посетени. И така, започваме от N2 и го съхраняваме на опашката. Така че опашката с име Q съдържа само N2.
Q: N2
- Стъпка 2: След това възелът, който е свързан към N1, е N3. Тъй като преминахме или посетихме възела, ще го съхраним на опашката. И така, актуализираната опашка е
Q: N3, N2
- Стъпка 3: След това възелът, който е свързан с коренния възел, е N4. Ще го съхраняваме на опашката.
Q: N4, N3, N2
- Стъпка 4: Всички възли, които са свързани към N1, се съхраняват в опашката. Сега ние премахваме N2 от опашката, както е по принцип First in First Out (FIFO) и намираме възлите, които са свързани към N2, т.е. N5. N5 не се посещава веднъж, така че ще го съхраняваме на опашката.
Q: N5, N4, N3
- Стъпка 5: Всички върхове са посетени, така че продължаваме да премахваме възлите от опашката, докато тя не се изпразни.
Пример за първо търсене на дълбочина
- Стъпка 1: Ще започнем с N1 като начален възел и ще го съхраним в стек S. N1 е свързан с три съседни възла N2, N3 и N4. Започвайки с N2 (можете да започнете азбучно или числово), ще поставим това в стека.
S: N2 (отгоре), N1
- Стъпка 2: Сега съседните възли на N2 са N1 и N5. Тъй като N1 вече присъства в стека, което означава, че е посетен, така че ще вземем N5 и ще го поставим в стека S.
S: N5 (отгоре), N2, N1
- Стъпка 3: Сега съседните възли на N5 са N3 и N4. Започваме ще N3 и го поставяме в стека.
S: N3 (отгоре), N5, N2, N1
Сега N3 е свързан с N5 и N1, които вече присъстват в стека, което означава, че са посетени, така че ще премахнем N3 от стека според принципа Last in First Out (LIFO).
S: N5 (отгоре), N2, N1
- Стъпка 4: Сега ще поставим последния възел, който не бяхме попаднали в цялото преминаване през N4 и ще го поставим в стека.
S: N4 (отгоре), N5, N2, N1
- Стъпка 5: Сега не сме останали с никакви други възли, така че ще проверим в стека дали има възли, свързани със съответните присъстващи в него възли, които не са посетени. Ако всички свързани възли са посетени, ще премахнем възлите в стека. Например, N4 няма свързващи възли, които не проверихме, така че ще го премахнем от стека. По същия начин можем да проверим и за други възли. Алгоритъмът спира, след като стека е празен.
Сравнение между главата на BFS VS DFS (Инфографика)
По-долу са първите 6 разлики между BFS VS DFS
Ключови разлики между BFS и DFS
Нека обсъдим някои от основните ключови разлики между BFS срещу DFS
- Търсене на първа широта (BFS) започва от коренния възел и посещава всички съответни възли, прикачени към него, докато DFS стартира от коренния възел и завършва пълния път, прикрепен към възела.
- BFS следва подхода на опашката, докато DFS следва подхода на Stack.
- Подходът, използван в BFS, е оптимален, докато процесът, използван в DFS, не е оптимален.
- Ако нашата цел е да намерим най-краткия път, отколкото BFS се предпочита пред DFS.
Таблица за сравнение на BFS и DFS
Нека да обсъдим топ сравнение между BFS срещу DFS
| BFS | DFS |
| Пълната форма на BFS е Breadth-First Search. | Пълната форма на DFS е дълбоко първо търсене |
| BFS има за цел да намери най-краткото разстояние и той започва от първия или корен възел и се премества през всичките му възли, прикрепени към съответните възли. Можете да получите ясен поглед върху работния му механизъм, след като преминете по-долу примера. | DFS следва подход, базиран на дълбочина и завършва пълния път през всички възли, прикрепени към съответния възел. Можете да получите ясен поглед върху работния му механизъм, след като преминете по-долу примера. |
| Извършва се по принципа на опашката, който е подходът First In First Out (FIFO). | Извършва се с помощта на принципа Stack, който е подходът Last In First out (LIFO). |
| Възлите, които са преминали повече от веднъж, се премахват от опашката. | Посетените възли се вмъкват в стека и по-късно, ако няма повече възли за посещение, те се премахват. |
| Той е сравнително по-бавен от дълбочината на първо търсене. | Той е по-бърз от алгоритъма за търсене на първата широчина. |
| Разпределението на паметта е повече от алгоритъма за първо търсене на дълбочина. | Разпределението на паметта е сравнително по-малко от алгоритъма за търсене на първата широта |
заключение
Има много приложения, при които горните алгоритми се използват като машинно обучение или за намиране на решения, свързани с изкуствен интелект и др. Те се използват главно в графики, за да открият дали е двустранен или не, за откриване на цикли или компоненти, които са свързани. Те също се считат за важни алгоритми за намиране на пътя или за намиране на най-краткото разстояние. В зависимост от изискванията на бизнеса можем да използваме два алгоритъма. Въпреки това, Breadth-First Search се счита за оптимален начин, а не за алгоритъма за първо търсене на дълбочина.
Препоръчителни статии
Това е ръководство за BFS VS DFS. Тук обсъждаме ключовите разлики на BFS VS DFS с инфографиката и таблицата за сравнение. Може да разгледате и следните статии, за да научите повече -
- Алгоритъм на BFS
- TeraData срещу Oracle
- Големи данни срещу хранилище на данни
- Големи данни срещу Apache Hadoop: Сравнение на топ 4, които трябва да научите