117. Обхождане в ширина и в дълбочина

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

Раздел в разширената разработка.

Самостоятелна задача

Условие

Графът е ненасочен с ребра A–B, A–C, B–D, D–C и C–E. Започваме от A. Съседите се разглеждат по азбучен ред. При BFS отбелязваме върха при добавяне в опашката. При рекурсивен DFS отбелязваме върха при влизане във функцията. Записваме реда на първото отбелязване.

  1. Какъв е редът при BFS?
  2. Какъв е редът при DFS?
  3. На колко ребра от A е E по най-къс път?
  4. Защо при обработката на 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';                                      // Минаваме на нов ред след обхождането в дълбочина.
}                                                      // Край на програмата.

Изтегли main.cpp.

В речника Обхождане в ширина (BFS) · Обхождане в дълбочина (DFS).