117. Обхождане в ширина и в дълбочина
BFS обхожда по слоеве чрез опашка. DFS следва една посока до изчерпване и после се връща, например чрез рекурсия. Отбелязването на посетените върхове спира повторното им обработване.
Раздел в разширената разработка.
Самостоятелна задача
Условие
Графът е ненасочен с ребра A–B, A–C, B–D, D–C и C–E. Започваме от A. Съседите се разглеждат по азбучен ред. При BFS отбелязваме върха при добавяне в опашката. При рекурсивен DFS отбелязваме върха при влизане във функцията. Записваме реда на първото отбелязване.
- Какъв е редът при BFS?
- Какъв е редът при DFS?
- На колко ребра от A е E по най-къс път?
- Защо при обработката на B не добавяме A повторно?
Отговори за самопроверка
Отговор 1
A, B, C, D, E.
Отговор 2
A, B, D, C, E.
Отговор 3
На две, по A–C–E.
Отговор 4
A е отбелязан още в началото.
Изпълним пример
Върховете са 0–3, а всеки ред на neighbors изброява съседите на съответния връх. Сравни изхода от опашката с този от рекурсивното обхождане на същия граф.
#include <iostream> // Включваме библиотеката, която ни дава cout за печат на екрана.
#include <queue> // Включваме библиотеката за опашки от тип queue.
#include <vector> // Включваме библиотеката за списъци от тип vector.
using namespace std; // Така можем да пишем cout вместо std::cout.
vector<int> neighbors[] = {{1, 2}, {0, 3}, {0}, {1}}; // За всеки от четирите върха записваме номерата на съседите му.
void depthFirst(int vertex, bool seen[]) { // Функцията обхожда в дълбочина от подадения връх.
seen[vertex] = true; // Отбелязваме текущия връх като посетен.
cout << vertex << ' '; // Печатаме номера му, последван от интервал.
for (int next : neighbors[vertex]) { // Вземаме поред всеки съсед на текущия връх.
if (!seen[next]) // С ! проверяваме дали съседът още не е отбелязан.
depthFirst(next, seen); // Обхождаме от този съсед, преди да продължим към следващия.
} // Край на цикъла.
} // Край на функцията.
int main() { // Оттук започва изпълнението на програмата.
bool seen[4] = {true, false, false, false}; // За обхождането в ширина отбелязваме само началния връх 0.
queue<int> waiting; // Създаваме опашка за върховете, които предстои да обработим.
waiting.push(0); // Добавяме началния връх в опашката.
while (!waiting.empty()) { // Работим, докато в опашката има поне един връх.
int vertex = waiting.front(); // Вземаме номера на първия чакащ връх.
waiting.pop(); // Махаме го от опашката, защото сега го обработваме.
cout << vertex << ' '; // Печатаме номера на текущия връх.
for (int next : neighbors[vertex]) { // Вземаме поред съседите на този връх.
if (!seen[next]) { // Проверяваме дали съседът още не е отбелязан.
seen[next] = true; // Отбелязваме го веднага, за да не го добавим отново от друг съсед.
waiting.push(next); // Слагаме го в края на опашката за по-късна обработка.
} // Край на действията при изпълнено условие.
} // Край на цикъла.
} // Край на цикъла.
cout << '\n'; // Минаваме на нов ред след обхождането в ширина.
bool seenDepth[4] = {}; // Подготвяме отделен масив за обхождането в дълбочина. Всички стойности започват с false.
depthFirst(0, seenDepth); // Пускаме обхождането в дълбочина от връх 0.
cout << '\n'; // Минаваме на нов ред след обхождането в дълбочина.
} // Край на програмата.
В речника Обхождане в ширина (BFS) · Обхождане в дълбочина (DFS).