BFS и DFS са методите за преливане, използвани при търсенето на графика. Обхождането на графиката е процесът на посещение на всички възли на графиката. Графиката е група Vertices 'V' и Edges 'E', които се свързват с върховете.
Сравнителна таблица
| Основа за сравнение | BFS | DFS |
|---|---|---|
| Основен | Вертикално базиран алгоритъм | Алгоритъм на ръба |
| Структура на данните, използвана за съхраняване на възлите | Опашка | купчина |
| Потребление на памет | Неефикасен | ефикасен |
| Структура на построеното дърво | Широк и къс | Тесен и дълъг |
| Преминаване по мода | Първоначално се проучват най-старите невиждани върхове. | В началото се изследват върховете по ръба. |
| оптималност | Оптимално за намиране на най-краткото разстояние, а не на разходите. | Не е оптимално |
| Приложение | Разглежда двустранната графика, свързания компонент и най-краткия път в графиката. | Разглежда двустранно свързана графика, силно свързана графика, ациклична графика и топологичен ред. |
Определение на BFS
Първо търсене на ширина (BFS) е методът за преминаване, използван в графиките. Той използва опашка за съхраняване на посетените върхове. В този метод акцентът е върху върховете на графиката, първо се избира един връх, след което се посещава и маркира. Върховете, съседни на посетения връх, се посещават и съхраняват последователно в опашката. По същия начин съхранените върхове се третират един по един и техните съседни върхове се посещават. Един възел е напълно проучен, преди да посети някой друг възел в графиката, с други думи, той първо преминава през най-малките неизследвани възли.
пример
Имаме графика, чиито върхове са A, B, C, D, E, F, G. Като се има предвид A като отправна точка. Стъпките, включени в процеса, са:
- Vertex A се разширява и съхранява в опашката.
- Версиите B, D и G наследници на A се разширяват и съхраняват в опашката, докато Vertex A се отстранява.
- Сега Б в предния край на опашката се премахва заедно със съхранението на неговите наследници на върховете Е и F.
- Точката D е в предния край на опашката и нейният свързан възел F вече е посетен.
- Vertex G се премахва от опашката и има наследник E, който вече е бил посетен.
- Сега E и F са премахнати от опашката и нейният приемник на върха C се пресича и съхранява в опашката.
- Накрая се премахва и С и опашката е празна, което означава, че сме готови.
- Генерираният изход е - A, B, D, G, E, F, C.
BFS може да бъде полезна за намиране дали графиката има свързани компоненти или не. Също така може да се използва за откриване на двустранна графика .
Графиката е двустранна, когато върховете на графата се разделят на две несвързани групи; няма два съседни върха в един и същ набор. Друг метод за проверка на двустранна графика е да се провери появата на нечетен цикъл в графиката. Двустранната графика не трябва да съдържа нечетен цикъл.
BFS също е по-добре при намирането на най-краткия път в графиката може да се разглежда като мрежа.
Определение на DFS
Методът за преливане на дълбочина (DFS) използва стека за съхраняване на посетените върхове. DFS е метод, базиран на ръба и работи в рекурсивен вид, където върховете се изследват по протежение на пътя (ръб). Проучването на един възел е спряно веднага след като се открие друг неизследван възел и най-дълбоките неизследвани възли са пресечени най-напред. DFS преминава / посещава всеки връх точно веднъж и всеки ръб се проверява точно два пъти.
пример
Подобно на BFS позволява да се използва една и съща графика за извършване на DFS операции, а включените стъпки са:
- Като се има предвид А като начален връх, който се изследва и съхранява в стека.
- B последователният връх на A се съхранява в стека.
- Точка В има две последователи Е и F, сред които по азбучен ред Е се изследва първо и се съхранява в стека.
- Наследникът на връх E, т.е. G се съхранява в стека.
- Точка G има два свързани върха и и двете вече са посетени, така че G се изважда от стека.
- По същия начин, E s също се отстранява.
- Сега върхът В е в горната част на стека, неговият друг възел (връх) F се изследва и съхранява в стека.
- Точка F има две последователни C и D, между които C се пресича първо и се съхранява в стека.
- Vertex C има само един предшественик, който вече е бил посетен, така че е премахнат от стека.
- Сега връх D, свързан с F, се посещава и съхранява в стека.
- Тъй като върх D няма никакви невиждани възли, следователно D се премахва.
- По същия начин, F, B и A също се появяват.
- Генерираният изход е - A, B, E, G, F, C, D.
Приложенията на DFS включват инспектиране на два графа свързани графика, силно свързана графика, ациклична графика и топологичен ред .
Графиката се нарича две ръбове, свързани, ако и само ако остава свързана, дори ако един от нейните ръбове е отстранен. Това приложение е много полезно в компютърните мрежи, където отказът на една връзка в мрежата няма да засегне оставащата мрежа и ще бъде свързан.
Силно свързаната графика е графика, в която трябва да съществува път между подредената двойка върхове. DFS се използва в насочената графика за търсене на пътя между всеки подреден чифт върхове. DFS може лесно да разрешава проблеми с свързването.
Ключови разлики между BFS и DFS
- BFS е вертекс-базиран алгоритъм, докато DFS е край-базиран алгоритъм.
- В BFS се използва структура на данните за опашката. От друга страна, DFS използва стек или рекурсия.
- Паметното пространство се използва ефективно в DFS, докато използването на пространството в BFS не е ефективно.
- BFS е оптимален алгоритъм, докато DFS не е оптимален.
- DFS изгражда тесни и дълги дървета. В противовес на това, BFS конструира широко и кратко дърво.
заключение
BFS и DFS, и двете техники за търсене на графики имат подобно време на работа, но различно потребление на пространство, DFS приема линейно пространство, защото трябва да помним един път с неизследвани възли, докато BFS поддържа всеки възел в паметта.
DFS дава по-дълбоки решения и не е оптимален, но работи добре, когато решението е плътно, докато BFS е оптимално, което първо търси оптималната цел.
