118. Покриващо дърво и времева сложност
В свързан ненасочен граф ребрата, с които BFS открива новите върхове, образуват покриващо дърво. То съдържа всички върхове и няма цикъл. Със списъци на съседство BFS и DFS отнемат O(V + E) време.
Раздел в разширената разработка.
Самостоятелна задача
Условие
Свързан ненасочен граф има ребра A–B, A–C, B–C и C–D. Пускаме BFS от A. Съседите се разглеждат по азбучен ред и се отбелязват при добавяне в опашката. Записваме ребро само при първо откриване на връх. V е броят върхове, E е броят ребра. При списъци всяко ненасочено ребро се вижда от двата края. При матрица проверяваме цял ред за всеки връх.
- Кои ребра записва BFS?
- Защо B–C не влиза в дървото?
- Колко ребра има полученото дърво и има ли цикъл?
- Как се оценява времето със списъци на съседство и с матрица?
Отговори за самопроверка
Отговор 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'; // Накрая печатаме броя на всички проверки на съседи.
} // Край на програмата.
В речника Покриващо дърво · Времева сложност.