Графи: Представяне и Основни Алгоритми в C++
▶⚡ Накратко
За Изпита🎯Учебни Цели
След края на тази лекция вие ще можете да:
- ✓Разбиране на терминологията и свойствата на графите (върхове, ребра, насочени/ненасочени графи)
- ✓Сравняване и имплементиране на матрица и списък на съседство в C++
- ✓Имплементиране на BFS и DFS алгоритми за обхождане на графи
- ✓Прилагане на графи за решаване на практически проблеми
- ✓Анализ на производителност и избор на оптимално представяне
Въведение и Мотивация
Какво са графите и защо са важни?
Граф е нелинейна структура от данни, състояща се от върхове (nodes/vertices) и ребра (edges/connections). За разлика от масиви или дървета, графите могат да моделират сложни, взаимносвързани отношения без ограничения как се свързват възлите - това ги прави идеалната структура за представяне на всичко от социални мрежи до градски карти.
- Моделиране на реални връзки: Градове/системи като възли, връзки/пътища като ребра
- Опростяване на сложността: Структуриране и визуализация на мрежи и тяхната динамика
- Основа за алгоритми: Анализ на свързаност, оптимални пътища, общности и т.н.
Приложения на графите в реалния свят
🌐 Социални Мрежи
Потребители като върхове, приятелства като ребра; позволява препоръки за приятели и откриване на общности
🗺️ Карти и Навигация
Локации като върхове, пътища като ребра; алгоритми за най-кратък път
🌍 Интернет структура
Уеб страници като върхове, хипервръзки като ребра; използва се в търсачки и web crawlers
🎬 Препоръчителни системи
Потребители, продукти и предпочитания като мрежов граф
📞 Телекомуникации
Телефони/рутери като върхове, комуникационни линии като ребра
🚚 Транспортни мрежи
Самолети, влакове или доставки като граф за оптимизация
C++ Контейнери: Vectors, Lists и Maps
Преглед
STL на C++ предоставя три основни контейнера, всеки със уникални свойства, които влияят как конструираме и манипулираме графи:
| Контейнер | Структура | Памет | Достъп | Insert/Delete | Търсене |
|---|---|---|---|---|---|
vector | Динамичен масив | Последователна | O(1) (random) | O(1) накрая | O(n) |
list | Двойно свързан списък | Несвързана | O(n) | O(1) (iterator) | O(n) |
map | Балансирано двоично дърво | Несвързана | O(log n) (key) | O(log n) | O(log n) |
- vector: Отличен за бърз достъп и списъци на съседство с умерена степен на върховете
- list: Добър за динамични операции insert/delete през списъка
- map: Идеален за асоцииране на допълнителна информация (тегла, свойства) и нестандартни идентификатори на върхове
Big-O Сложност: Освежаване
- O(1): Константно време/памет (напр. достъп до масив)
- O(log n): Логаритмично време (напр. търсене в
map) - O(n): Линейно време (напр. обхождане на масив/списък)
- O(n²): Квадратично време (напр. вложени цикли, матрица на съседство за плътни графи)
- Матрица на съседство: O(V²) памет, моментална проверка за ребро (O(1)), но разхищава място при разредени графи
- Списък на съседство: O(V+E) памет, ефективен за разредени графи, но по-бавна проверка за ребро
Основи на Графите
Дефиниция на граф
- Върхове (Nodes): Точки/обекти (напр. потребители, градове)
- Ребра (Links): Връзки/отношения между двойки върхове
Нотация: ( G = (V, E) )
където:
- V е множество от върхове
- E е множество от ребра
Типове графи
Ненасочен граф
Ребрата нямат посока. Приятелството е двупосочно.
Пример: Facebook приятелства
Насочен граф (Digraph)
Ребрата имат посока.
Пример: Twitter "follows" - A следи B не означава че B следи A
Нетеглен граф
Всички ребра са равни.
Пример: Дали два града са свързани с директен път
Теглен граф
Ребрата имат стойности - разстояние, цена, капацитет и т.н.
Пример: Разстояния между градове в километри
Плътност на графа
Плътен граф
Разреден граф
Плътността на графа влияе дали матрица или списък на съседство е по-ефективен!
Представяне на Графи
1. Матрица на Съседство (Adjacency Matrix)
V × V матрица където клетка [i][j] е:
1(или тегло) ако съществува ребро от i към j0ако не съществува ребро
Имплементация в C++:
// Създаване на матрица на съседство за n върха
int n = 5; // брой върхове
vector<vector<int>> adjMatrix(n, vector<int>(n, 0));
// Добавяне на ребро от u към v
int u = 0, v = 1;
adjMatrix[u][v] = 1;
// За ненасочен граф добавяме и обратното ребро
adjMatrix[v][u] = 1;
// За теглен граф използваме теглото вместо 1
adjMatrix[u][v] = weight;
Анализ на сложност:
| Операция | Сложност |
|---|---|
| Памет | O(V²) |
| Проверка за ребро | O(1) |
| Добавяне на ребро | O(1) |
| Премахване на ребро | O(1) |
| Обхождане на всички ребра | O(V²) |
| Намиране на съседи на връх | O(V) |
- Плътни графи с много ребра
- Често се правят проверки за наличие на ребро
- Малки графи където паметта не е проблем
- Когато е нужен бърз достъп до ребра
- ❌ Разхищава памет при разредени графи (много нули)
- ❌ O(V²) памет дори за графи с малко ребра
- ❌ Бавно обхождане на съседите на връх
2. Списък на Съседство (Adjacency List)
Масив (или map) от списъци/вектори където всеки връх съхранява списък на своите съседи.
Имплементация в C++:
// Вариант 1: Vector of vectors (за последователни ID-та на върхове)
int n = 5; // брой върхове
vector<vector<int>> adj(n);
// Добавяне на ребро от u към v
int u = 0, v = 1;
adj[u].push_back(v);
// За ненасочен граф
adj[v].push_back(u);
// Вариант 2: Map of lists (за произволни ID-та)
map<int, list<int>> adj;
adj[u].push_back(v);
// Вариант 3: За теглени графи
map<int, list<pair<int, int>>> adjWeighted; // {съсед, тегло}
adjWeighted[u].push_back({v, weight});
Анализ на сложност:
| Операция | Сложност |
|---|---|
| Памет | O(V + E) |
| Проверка за ребро | O(degree(v)) ≈ O(V) worst case |
| Добавяне на ребро | O(1) амортизирано |
| Премахване на ребро | O(degree(v)) |
| Обхождане на всички ребра | O(V + E) |
| Намиране на съседи на връх | O(1) достъп до списъка |
- Разредени графи където E << V²
- Когато често обхождаме съседите на връх
- Големи графи където паметта е критична
- Когато рядко проверяваме за конкретно ребро
- ❌ По-бавна проверка дали съществува конкретно ребро
- ❌ Малко по-сложна имплементация
Сравнение: Матрица vs Списък на Съседство
Матрица на Съседство
Списък на Съседство
| Характеристика | Матрица | Списък |
|---|---|---|
| Памет | O(V²) | O(V+E) |
| Проверка за ребро | O(1) | O(degree) |
| Обхождане (BFS/DFS) | O(V²) | O(V+E) |
| Insert/Delete ребро | O(1) | O(1) / O(degree) |
| Плътни графи | ✅ | ❌ |
| Разредени графи | ❌ | ✅ |
Breadth-First Search (BFS) - Търсене вШирочина
Концепция
BFS обхожда графа ниво по ниво от начален възел, посещавайки всички непосредствени съседи преди да се премести навън.
Характеристики:
- Структура от данни: Опашка (Queue - FIFO)
- Най-добър за: Намиране на най-кратки пътища в нетеглени графи, обхождане по нива
Стъпки на BFS (Псевдокод)
BFS(граф, начален_връх):
1. Маркирай начален_връх като посетен
2. Добави начален_връх в опашка
3. Докато опашката не е празна:
a. Извади връх от опашката
b. За всеки непосетен съсед:
- Маркирай като посетен
- Добави в опашката
Имплементация в C++
#include <queue>
#include <vector>
#include <iostream>
void BFS(const vector<vector<int>>& adj, int start) {
int n = adj.size();
vector<bool> visited(n, false);
queue<int> q;
// Започваме от начален връх
visited[start] = true;
q.push(start);
cout << "BFS обхождане: ";
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
// Обхождаме всички съседи
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
cout << endl;
}
Нека имаме следния граф:
0 --- 1 --- 3
| |
2 --- 4
Adjacency list:
0: [1, 2]
1: [0, 3, 4]
2: [0, 4]
3: [1]
4: [1, 2]
BFS от връх 0:
| Стъпка | Опашка | Посетен | Изход |
|---|---|---|---|
| 1 | [0] | 0 | 0 |
| 2 | [1, 2] | 0,1,2 | 0, 1 |
| 3 | [2, 3, 4] | 0,1,2,3,4 | 0, 1, 2 |
| 4 | [3, 4] | 0, 1, 2, 3 | |
| 5 | [4] | 0, 1, 2, 3, 4 |
Резултат: 0, 1, 2, 3, 4
Анализ на сложност
| Метрика | Сложност | Обяснение |
|---|---|---|
| Време | O(V + E) | Всеки връх и ребро се посещава веднъж |
| Памет | O(V) | За опашката и visited масива |
- ✅ Най-кратък път в нетеглени графи
- ✅ Social connections - приятели в рамките на k степени
- ✅ Web crawling - обхождане на уеб страници
- ✅ Network broadcasting - разпространение на пакети
- ✅ Level-order traversal - обхождане по нива
Depth-First Search (DFS) - Търсене в Дълбочина
Концепция
DFS изследва колкото е възможно по-дълбоко по един клон преди да се връща назад (backtrack).
Характеристики:
- Структура от данни: Стек (Stack - LIFO) или рекурсия
- Най-добър за: Откриване на цикли, намиране на компоненти, изследване на всички свързаности
Стъпки на DFS (Рекурсивен)
DFS(връх):
1. Маркирай връх като посетен
2. За всеки непосетен съсед:
a. Рекурсивно извикай DFS(съсед)
Имплементация в C++ (Рекурсивна)
#include <vector>
#include <iostream>
void DFS_recursive(const vector<vector<int>>& adj, int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
DFS_recursive(adj, neighbor, visited);
}
}
}
void DFS(const vector<vector<int>>& adj, int start) {
int n = adj.size();
vector<bool> visited(n, false);
cout << "DFS обхождане (рекурсивно): ";
DFS_recursive(adj, start, visited);
cout << endl;
}
Имплементация в C++ (Итеративна)
#include <stack>
#include <vector>
#include <iostream>
void DFS_iterative(const vector<vector<int>>& adj, int start) {
int n = adj.size();
vector<bool> visited(n, false);
stack<int> s;
s.push(start);
cout << "DFS обхождане (итеративно): ";
while (!s.empty()) {
int v = s.top();
s.pop();
if (!visited[v]) {
visited[v] = true;
cout << v << " ";
// Добавяме съседите в стека (в обратен ред за консистентност)
for (auto it = adj[v].rbegin(); it != adj[v].rend(); ++it) {
if (!visited[*it]) {
s.push(*it);
}
}
}
}
cout << endl;
}
Същият граф:
0 --- 1 --- 3
| |
2 --- 4
DFS от връх 0 (предполагаме съседите са в нарастващ ред):
| Стъпка | Стек (рекурсия) | Посетен | Изход |
|---|---|---|---|
| 1 | [0] | 0 | 0 |
| 2 | [0, 1] | 0, 1 | 0, 1 |
| 3 | [0, 1, 3] | 0, 1, 3 | 0, 1, 3 |
| 4 | [0, 1, 4] | 0, 1, 3, 4 | 0, 1, 3, 4 |
| 5 | [0, 1, 4, 2] | 0, 1, 3, 4, 2 | 0, 1, 3, 4, 2 |
Резултат: 0, 1, 3, 4, 2
Забележка: Редът може да варира в зависимост от реда на съседите
Анализ на сложност
| Метрика | Сложност | Обяснение |
|---|---|---|
| Време | O(V + E) | Всеки връх и ребро се посещава веднъж |
| Памет | O(V) | За стека/call stack и visited масива |
- ✅ Откриване на цикли в графи
- ✅ Топологично сортиране на насочени ациклични графи
- ✅ Силно свързани компоненти (Strongly Connected Components)
- ✅ Намиране на свързани компоненти
- ✅ Backtracking проблеми (лабиринти, судоку)
- ✅ Проверка за двуделност (bipartite check)
Сравнение: BFS vs DFS
BFS (Breadth-First Search)
DFS (Depth-First Search)
| Критерий | BFS | DFS |
|---|---|---|
| Структура | Queue | Stack/Recursion |
| Обхождане | По нива | В дълбочина |
| Най-кратък път | ✅ Да (нетеглен) | ❌ Не |
| Цикли | ❌ По-трудно | ✅ Лесно |
| Памет | O(width) | O(depth) |
| Имплементация | Итеративна | Рекурсивна/Итеративна |
Примери и Казуси
Пример 1: Социална мрежа - Приятелски връзки
Моделирайте потребители като върхове, приятелства като ненасочени ребра. Намерете всички приятели в рамките на k степени от даден потребител.
Решение: Използвайте BFS
vector<int> friendsWithinKDegrees(
const vector<vector<int>>& adj,
int start,
int k
) {
vector<int> result;
vector<bool> visited(adj.size(), false);
queue<pair<int, int>> q; // {връх, разстояние}
q.push({start, 0});
visited[start] = true;
while (!q.empty()) {
auto [v, dist] = q.front();
q.pop();
if (dist > 0 && dist <= k) {
result.push_back(v);
}
if (dist < k) {
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push({neighbor, dist + 1});
}
}
}
}
return result;
}
Пример 2: Откриване на цикли в насочен граф
Проверете дали насочен граф съдържа цикъл.
Решение: Използвайте DFS с оцветяване (color marking)
enum Color { WHITE, GRAY, BLACK };
bool hasCycleDFS(
const vector<vector<int>>& adj,
int v,
vector<Color>& color
) {
color[v] = GRAY; // Текуща обработка
for (int neighbor : adj[v]) {
if (color[neighbor] == GRAY) {
return true; // Back edge = цикъл!
}
if (color[neighbor] == WHITE) {
if (hasCycleDFS(adj, neighbor, color)) {
return true;
}
}
}
color[v] = BLACK; // Завършена обработка
return false;
}
bool hasCycle(const vector<vector<int>>& adj) {
int n = adj.size();
vector<Color> color(n, WHITE);
for (int v = 0; v < n; v++) {
if (color[v] == WHITE) {
if (hasCycleDFS(adj, v, color)) {
return true;
}
}
}
return false;
}
- WHITE: Невидян връх
- GRAY: В процес на обработка (в текущия DFS път)
- BLACK: Завършена обработка
Ако срещнем GRAY връх от текущия път → има back edge → цикъл!
Пример 3: Броене на свързани компоненти
Намерете броя на свързаните компоненти в ненасочен граф.
Решение: DFS или BFS от всеки непосетен връх
void DFS_component(
const vector<vector<int>>& adj,
int v,
vector<bool>& visited
) {
visited[v] = true;
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
DFS_component(adj, neighbor, visited);
}
}
}
int countConnectedComponents(const vector<vector<int>>& adj) {
int n = adj.size();
vector<bool> visited(n, false);
int count = 0;
for (int v = 0; v < n; v++) {
if (!visited[v]) {
DFS_component(adj, v, visited);
count++; // Нова компонента!
}
}
return count;
}
Тест:
Граф:
0: [1]
1: [0, 2]
2: [1]
3: [4]
4: [3]
5: []
Резултат: 3 компоненти
- Компонента 1: {0, 1, 2}
- Компонента 2: {3, 4}
- Компонента 3: {5}
Реални Приложения и Стратегии
🔍 Fraud Detection
Проблем: Откриване на измамни транзакции
Решение: DFS за откриване на цикли в транзакционни мрежи
Компании: Zurich Insurance, PayPal
✈️ Flight Recommendations
Проблем: Препоръчване на полети с най-малко пресядания
Решение: BFS за най-кратък път
Компании: WestJet, Kayak
🗺️ Navigation Systems
Проблем: Real-time routing в градове
Решение: Динамични актуализации на графи + Dijkstra/BFS
Компании: Google Maps, Waze
📞 Telecom Networks
Проблем: Анализ на устойчивост на мрежата
Решение: Connected components за проследяване на зависимости
Компании: AT&T, Verizon
Чести Грешки и Best Practices
❌ Забравяне да маркираме върхове като посетени
- Води до безкрайни цикли!
❌ Неправилна инициализация на visited array
- Уверете се че всички върхове започват като невидени
❌ Използване на грешен контейнер
- Queue за BFS, Stack за DFS!
❌ Забравяне на edge cases
- Празен граф, един връх, несвързани компоненти
✅ Винаги маркирайте върховете като посетени веднага след като ги добавите в опашката/стека
✅ Тествайте с малки примери преди да мащабирате
✅ Помислете за edge cases - празни графи, self-loops, несвързани графи
✅ Документирайте вашите предположения - насочен/ненасочен, теглен/нетеглен
✅ Използвайте подходящо представяне според плътността на графа
Резюме и Ключови Точки
Матрица на Съседство
Предимства:
- O(1) проверка за ребро
- Проста имплементация
Недостатъци:
- O(V²) памет
- Бавно обхождане
Използвай за: Плътни графи, чести проверки за ребра
Списък на Съседство
Предимства:
- O(V+E) памет
- Ефективно обхождане
Недостатъци:
- По-бавна проверка за ребро
Използвай за: Разредени графи, големи графи
BFS
Характеристики:
- Queue (FIFO)
- Ниво по ниво
- O(V+E) време
Използвай за: Най-кратък път (нетеглен), level-order traversal
DFS
Характеристики:
- Stack/Recursion (LIFO)
- В дълбочина
- O(V+E) време
Използвай за: Цикли, топологично сортиране, компоненти
Напреднали Теми (Преглед)
Тази лекция положи основите. Напред ви очакват:
- Dijkstra's Algorithm: Най-кратък път в теглени графи
- Topological Sort: Сортиране на насочени ациклични графи (DAG)
- Minimum Spanning Tree: Kruskal's и Prim's алгоритми
- Strongly Connected Components: Kosaraju's и Tarjan's алгоритми
- Network Flow: Max-Flow Min-Cut теорема
- A Search*: Евристично търсене за пътища
Допълнителни Ресурси
Онлайн Туториали
- GeeksforGeeks - Graph Data Structure - Comprehensive guide
- CP-Algorithms - Graph Theory - Advanced algorithms
- Visualgo - Graph Traversal - Interactive visualization
Визуализация и Инструменти
- Graph Online - Create and visualize graphs
- Graph Editor - Interactive graph tool
Видео Лекции
- MIT 6.006 - Graph Algorithms - Comprehensive lecture
- Abdul Bari - Graph Theory - Clear explanations
Практически Задачи
- LeetCode - Graph Problems - От лесни до трудни
- HackerRank - Graph Theory - Практически задачи
- Codeforces - Graph Tag - Състезателни задачи
Книги и Статии
- "Introduction to Algorithms" (CLRS) - Chapters 22-26
- "Algorithms" by Sedgewick and Wayne - Graph chapters
- "Competitive Programming 3" - Graph theory section