Разлика между BFS и DFS

BFS срещу DFS

Първо търсене на широчина (известен също като BFS) е метод за търсене, използван за разширяване на всички възли на определена графика. Тя изпълнява тази задача чрез търсене на всяко едно решение, за да разгледа и разшири тези възли (или комбинация от последователности в тях). Като такъв, BFS не използва евристичен алгоритъм (или алгоритъм, който търси решение чрез множество сценарии). След като всички възли са получени, те се добавят към опашка, известна като опашката First In, First Out. Онези възли, които не са изследвани, се „съхраняват“ в контейнер, обозначен като „отворен“; веднъж изследвани те се транспортират до контейнер с надпис „затворен“.

Дълбокото първо търсене (известен също като DFS) е метод на търсене, който се заравя по-дълбоко в дъщерен възел на търсене, докато не бъде постигната цел (или докато няма възел без други пермутации или „деца“). След като се намери една цел, търсенето връща към предишен възел, който е преминал с решение, повтаряйки процеса, докато всички възли са били успешно търсени. Като такива възлите продължават да бъдат оставяни настрана за по-нататъшно проучване - това се нарича нерекурсивно изпълнение.

Характеристиките на BFS са пространство и времева сложност, пълнота, доказателство за пълнота и оптималност. Космическата сложност се отнася до съотношението на броя на възлите на най-дълбокото ниво на търсене. Времевата сложност се отнася до действителното количество „време“, използвано за разглеждане на всеки път, който възел ще измине при търсене. Пълнотата е по същество търсене, което намира решение в графика, независимо от това какъв вид е графиката. Доказателството за пълнотата е най-плиткото ниво, на което се открива цел в възел на определена дълбочина. И накрая, оптималността се отнася до BFS, който не се претегля - това е графика, използвана за единична стъпка.

A DFS е най-естественият изход, използващ разклоняващо се дърво - което е дърво, съставено от всички върхове и някои ръбове в неориентирана графика. В тази формация графиката е разделена на три класа: Предни ръбове, насочени от възел към дъщерен възел; задни ръбове, насочени от възел към по-ранен възел; и кръстосани ръбове, които не правят нито едно от тях.

Резюме:

1. BFS търси всяко решение в графика, за да разшири своите възли; DFS се рови дълбоко в дъщерния възел, докато не бъде постигната цел.

2. Характеристиките на BFS са сложност на пространството и времето, пълнота, доказателство за пълнота и оптималност; най-естественият резултат за DFS е разклоняващото се дърво с три класа: предни ръбове, задни ръбове и напречни ръбове.