Преди да разгледаме разликите между BFS и DFS, първо трябва да знаем за BFS и DFS поотделно.

Какво е BFS?

BFS означава Първо търсене в ширина . Известен е още като преминаване на реда на ниво . Структурата на данните на опашката се използва за обхождане на първо търсене в ширина. Когато използваме алгоритъма BFS за обхождане в графика, можем да считаме всеки възел за основен възел.

Нека разгледаме графиката по-долу за обхода на първо търсене в ширина.

референтни типове данни в java

Да предположим, че разглеждаме възел 0 като основен възел. Следователно преминаването ще започне от възел 0.

След като възел 0 бъде премахнат от опашката, той се отпечатва и маркира като a посетен възел.

След като възел 0 бъде премахнат от опашката, тогава съседните възли на възел 0 ще бъдат вмъкнати в опашка, както е показано по-долу:

Сега възел 1 ще бъде премахнат от опашката; той се отпечатва и маркира като посетен възел

След като възел 1 бъде премахнат от опашката, тогава всички съседни възли на възел 1 ще бъдат добавени в опашка. Съседните възли на възел 1 са 0, 3, 2, 6 и 5. Но трябва да вмъкнем само непосетени възли в опашка. Тъй като възли 3, 2, 6 и 5 са ​​непосетени; следователно тези възли ще бъдат добавени в опашка, както е показано по-долу:

Следващият възел е 3 в опашка. И така, възел 3 ще бъде премахнат от опашката, той се отпечатва и маркира като посетен, както е показано по-долу:

След като възел 3 бъде премахнат от опашката, тогава всички съседни възли на възел 3 с изключение на посетените възли ще бъдат добавени в опашка. Съседните възли на възел 3 са 0, 1, 2 и 4. Тъй като възли 0, 1 вече са посетени, а възел 2 присъства в опашка; следователно трябва да вмъкнем само възел 4 в опашка.

wumpus свят

Сега следващият възел в опашката е 2. Така че 2 ще бъде изтрит от опашката. Той се отпечатва и маркира като посетен, както е показано по-долу:

След като възел 2 бъде премахнат от опашката, тогава всички съседни възли на възел 2 с изключение на посетените възли ще бъдат добавени в опашка. Съседните възли на възел 2 са 1, 3, 5, 6 и 4. Тъй като възлите 1 и 3 вече са били посетени, а 4, 5, 6 вече са добавени в опашката; следователно не е необходимо да вмъкваме никакъв възел в опашката.

Следващият елемент е 5. Така че 5 ще бъде изтрит от опашката. Той се отпечатва и маркира като посетен, както е показано по-долу:

След като възел 5 бъде премахнат от опашката, тогава всички съседни възли на възел 5 с изключение на посетените възли ще бъдат добавени в опашката. Съседните възли на възел 5 са ​​1 и 2. Тъй като и двата възела вече са били посетени; следователно няма връх за вмъкване в опашка.

Следващият възел е 6. Така че 6 ще бъде изтрит от опашката. Той се отпечатва и маркира като посетен, както е показано по-долу:

След като възел 6 бъде премахнат от опашката, тогава всички съседни възли на възел 6 с изключение на посетените възли ще бъдат добавени в опашката. Съседните възли на възел 6 са 1 и 4. Тъй като възел 1 вече е бил посетен и възел 4 вече е добавен в опашката; следователно няма връх за вмъкване в опашката.

Следващият елемент в опашката е 4. Така че 4 ще бъде изтрит от опашката. Отпечатва се и се маркира като посетено.

След като възел 4 бъде премахнат от опашката, тогава всички съседни възли на възел 4 с изключение на посетените възли ще бъдат добавени в опашката. Съседните възли на възел 4 са 3, 2 и 6. Тъй като всички съседни възли вече са били посетени; така че няма връх за вмъкване в опашката.

Какво е DFS?

DFS означава Depth First Search. При DFS traversal се използва стековата структура на данните, която работи на принципа LIFO (Last In First Out). В DFS преминаването може да започне от всеки възел или можем да кажем, че всеки възел може да се счита за основен възел, докато основният възел не бъде споменат в проблема.

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

Нека разгледаме графиката по-долу за обхода на първо търсене в дълбочина.

какво е обработка на изключения в java

Разгледайте възел 0 като основен възел.

шаблон за проектиране на строител

Първо вмъкваме елемента 0 в стека, както е показано по-долу:

Възелът 0 има два съседни възела, т.е. 1 и 3. Сега можем да вземем само един съседен възел, 1 или 3, за преминаване. Да предположим, че разглеждаме възел 1; следователно 1 се вмъква в стек и се отпечатва, както е показано по-долу:

Сега ще разгледаме съседните върхове на възел 1. Непосетените съседни върхове на възел 1 са 3, 2, 5 и 6. Можем да разгледаме всеки от тези четири върха. Да предположим, че вземем възел 3 и го вмъкнем в стека, както е показано по-долу:

Помислете за непосетените съседни върхове на възел 3. Непосетените съседни върхове на възел 3 са 2 и 4. Можем да вземем всеки от върховете, т.е. 2 или 4. Да предположим, че вземем връх 2 и го вмъкнем в стека, както е показано по-долу:

Непосетените съседни върхове на възел 2 са 5 и 4. Можем да изберем един от върховете, т.е. 5 или 4. Да предположим, че вземем връх 4 и го вмъкнем в стека, както е показано по-долу:

Сега ще разгледаме непосетените съседни върхове на възел 4. Непосетеният съседен връх на възел 4 е възел 6. Следователно елемент 6 се вмъква в стека, както е показано по-долу:

След като вмъкнем елемент 6 в стека, ще разгледаме непосетените съседни върхове на възел 6. Тъй като няма непосетени съседни върхове на възел 6, така че не можем да преминем отвъд възел 6. В този случай ще изпълним връщане назад . Най-горният елемент, т.е. 6, ще изскочи от стека, както е показано по-долу:

Най-горният елемент в стека е 4. Тъй като няма непосетени съседни върхове, останали от възел 4; следователно възел 4 се изважда от стека, както е показано по-долу:

Следващият най-горен елемент в стека е 2. Сега ще разгледаме непосетените съседни върхове на възел 2. Тъй като е останал само един непосетен възел, т.е. 5, така че възел 5 ще бъде избутан в стека над 2 и ще бъде отпечатан както е показано по-долу:

Сега ще проверим съседните върхове на възел 5, които все още не са посетени. Тъй като не е останал връх за посещение, изваждаме елемент 5 от стека, както е показано по-долу:

Не можем да преместим още 5, така че трябва да извършим обратно проследяване. При обратно проследяване най-горният елемент ще изскочи от стека. Най-горният елемент е 5, който ще изскочи от стека, и се връщаме към възел 2, както е показано по-долу:

f-низ питон

Сега ще проверим непосетените съседни върхове на възел 2. Тъй като не е останал съседен връх, който да бъде посетен, извършваме обратно проследяване. При обратно проследяване най-горният елемент, т.е. 2, ще бъде изскочен от стека и ние се връщаме към възел 3, както е показано по-долу:

Сега ще проверим непосетените съседни върхове на възел 3. Тъй като няма останал съседен връх, който да бъде посетен, извършваме обратно проследяване. При обратно проследяване най-горният елемент, т.е. 3, ще бъде изскочен от стека и ние се връщаме към възел 1, както е показано по-долу:

След като извадим елемент 3, ще проверим непосетените съседни върхове на възел 1. Тъй като няма останал връх, който да бъде посетен; следователно ще се извърши обратно проследяване. При обратно проследяване най-горният елемент, т.е. 1, ще бъде изскочен от стека и ние се връщаме към възел 0, както е показано по-долу:

Ще проверим съседните върхове на възел 0, които все още не са посетени. Тъй като не е останал съседен връх, който да бъде посетен, извършваме обратно проследяване. В това само един елемент, т.е. 0, останал в стека, ще бъде изваден от стека, както е показано по-долу:

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

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

Следните са разликите между BFS и DFS: