Препоръчано, 2022

Избор На Редактора

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

Основната разлика между BFS и DFS е, че BFS продължава нивото на ниво, докато DFS следва първо пътя, започващ от крайния възел (връх), след това друг път от началото до края и т.н., докато не бъдат посетени всички възли. Освен това, BFS използва опашката за съхранение на възлите, докато DFS използва стека за пресичане на възлите.

BFS и DFS са методите за преливане, използвани при търсенето на графика. Обхождането на графиката е процесът на посещение на всички възли на графиката. Графиката е група Vertices 'V' и Edges 'E', които се свързват с върховете.

Сравнителна таблица

Основа за сравнение
BFSDFS
ОсновенВертикално базиран алгоритъмАлгоритъм на ръба
Структура на данните, използвана за съхраняване на възлитеОпашкакупчина
Потребление на паметНеефикасенефикасен
Структура на построеното дървоШирок и късТесен и дълъг
Преминаване по модаПървоначално се проучват най-старите невиждани върхове.В началото се изследват върховете по ръба.
оптималностОптимално за намиране на най-краткото разстояние, а не на разходите.Не е оптимално
ПриложениеРазглежда двустранната графика, свързания компонент и най-краткия път в графиката.Разглежда двустранно свързана графика, силно свързана графика, ациклична графика и топологичен ред.

Определение на 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.

Applications-

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

  1. BFS е вертекс-базиран алгоритъм, докато DFS е край-базиран алгоритъм.
  2. В BFS се използва структура на данните за опашката. От друга страна, DFS използва стек или рекурсия.
  3. Паметното пространство се използва ефективно в DFS, докато използването на пространството в BFS не е ефективно.
  4. BFS е оптимален алгоритъм, докато DFS не е оптимален.
  5. DFS изгражда тесни и дълги дървета. В противовес на това, BFS конструира широко и кратко дърво.

заключение

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

DFS дава по-дълбоки решения и не е оптимален, но работи добре, когато решението е плътно, докато BFS е оптимално, което първо търси оптималната цел.

Top