118. Покриващо дърво и времева сложност

В свързан ненасочен граф ребрата, с които BFS открива новите върхове, образуват покриващо дърво. То съдържа всички върхове и няма цикъл. Със списъци на съседство BFS и DFS отнемат O(V + E) време.

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

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

Условие

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

  1. Кои ребра записва BFS?
  2. Защо B–C не влиза в дървото?
  3. Колко ребра има полученото дърво и има ли цикъл?
  4. Как се оценява времето със списъци на съседство и с матрица?

Отговори за самопроверка

Отговор 1

A–B, A–C и C–D.

Отговор 2

Когато разгледаме B, C вече е открит от A.

Отговор 3

Три. Всеки връх освен A се присъединява с едно ребро към вече открит връх, така че цикъл няма.

Отговор 4

Със списъци O(V + E). С матрица O(V²), защото преглеждаме V реда с по V клетки.

Изпълним пример

В графа има триъгълник 0–1–2 и връзка 1–3. Програмата брои прегледаните записи за съседство и извежда ребро при всяко първо откриване.

#include <iostream>                                       // Включваме библиотеката, която ни дава cout за печат на екрана.
#include <queue>                                          // Включваме библиотеката за опашки от тип queue.
#include <vector>                                         // Включваме библиотеката за списъци от тип vector.
using namespace std;                                      // Така можем да пишем cout вместо std::cout.

int main() {                                              // Оттук започва изпълнението на програмата.
    vector<int> neighbors[] = {{1, 2}, {0, 2, 3}, {0, 1}, {1}};  // За всеки връх записваме номерата на съседите му.
    bool seen[4] = {true, false, false, false};           // Отбелязваме връх 0 като открит. Останалите започват неотбелязани.
    queue<int> waiting;                                   // Създаваме опашка за откритите върхове, които чакаме да обработим.
    waiting.push(0);                                      // Добавяме началния връх 0 в опашката.
    int checks = 0;                                       // Започваме броя на проверките от 0.

    while (!waiting.empty()) {                            // Повтаряме, докато има чакащи върхове.
        int vertex = waiting.front();                     // Вземаме номера на първия чакащ връх.
        waiting.pop();                                    // Премахваме го от опашката, защото сега ще проверим съседите му.
        for (int next : neighbors[vertex]) {              // Проверяваме поред всеки съсед на текущия връх.
            checks++;                                     // Прибавяме 1 за проверката на текущия съсед.
            if (!seen[next]) {                            // Проверяваме дали откриваме съседа за първи път.
                seen[next] = true;                        // Отбелязваме съседа като открит, за да го добавим само веднъж.
                waiting.push(next);                       // Слагаме го в края на опашката, за да проверим и неговите съседи.
                cout << vertex << '-' << next << '\n';    // Печатаме реброто, по което за първи път стигнахме до този връх.
            }                                             // Край на действията при изпълнено условие.
        }                                                 // Край на цикъла.
    }                                                     // Край на цикъла.

    cout << "Checks: " << checks << '\n';                 // Накрая печатаме броя на всички проверки на съседи.
}                                                         // Край на програмата.

Изтегли main.cpp.

В речника Покриващо дърво · Времева сложност.