Skip to content

🕸️ Алгоритми върху Графи: Основи и Оптимизации

Графите са фундаментална структура от данни за моделиране на връзки между обекти (градове, компютри, хора, социални мрежи). Разбирането на графовите алгоритми е критично за успеха в информатични олимпиади. В този материал разглеждаме най-важните алгоритми за обхождане, намиране на най-кратък път, минимални покриващи дървета и топологично сортиране.

Основни представяния на граф: - Списък на съседство (vector<vector<int>> или vector<vector<pair<int,int>>>): Ефективен за разредени графи. - Матрица на съседство (bool adj[MAXN][MAXN]): Бърза проверка за съществуване на ребро, но изисква \(O(V^2)\) памет.

1. Обхождане на Граф

1.1. DFS (Обхождане в дълбочина)

DFS е алгоритъм за обхождане на граф, който изследва колкото се може по-навътре по даден клон, преди да се върне назад. Използва стек (имплицитно чрез рекурсия или explicit чрез std::stack).

Как работи: 1. Започваме от даден връх и го маркираме като посетен 2. Рекурсивно посещаваме всички непосетени съседи 3. Връщаме се назад, когато няма повече непосетени съседи

Пълна имплементация: 

vector<int> adj[MAXN];  // Списък на съседство
bool visited[MAXN];     // Маркиране на посетени върхове
vector<int> component;  // Текуща компонента

void dfs(int u) {
    visited[u] = true;
    component.push_back(u);  // Добавяме към текущата компонента

    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

// Намиране на всички свързани компоненти
void findComponents() {
    memset(visited, false, sizeof(visited));
    int numComponents = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            component.clear();
            dfs(i);
            numComponents++;
            // component съдържа всички върхове в текущата компонента
        }
    }
}

Сложност: \(O(V + E)\) - всеки връх и ребро се обработва точно веднъж.

Приложения: - Намиране на свързани компоненти в ненасочен граф - Проверка за цикли (ако срещнем посетен връх, различен от бащата) - Топологично сортиране в DAG - Намиране на мостове и артикулационни точки - Решаване на лабиринти

1.2. BFS (Обхождане в ширина)

BFS обхожда графа "слой по слой", използвайки опашка (std::queue). Първо посещава всички съседи на текущия връх, след това техните съседи и т.н.

Как работи: 1. Започваме от даден връх, поставяме го в опашката и го маркираме 2. Докато опашката не е празна: - Извличаме връх от опашката - За всеки непосетен съсед: маркираме го и го добавяме в опашката

Пълна имплементация: 

vector<int> adj[MAXN];
bool visited[MAXN];
int dist[MAXN];  // Разстояние от началния връх

void bfs(int start) {
    memset(visited, false, sizeof(visited));
    memset(dist, -1, sizeof(dist));

    queue<int> q;
    q.push(start);
    visited[start] = true;
    dist[start] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

// BFS с възстановяване на път
vector<int> reconstructPath(int start, int end) {
    vector<int> parent(n, -1);
    queue<int> q;
    q.push(start);
    parent[start] = start;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == end) break;  // Намерихме целта

        for (int v : adj[u]) {
            if (parent[v] == -1) {
                parent[v] = u;
                q.push(v);
            }
        }
    }

    // Възстановяване на пътя
    if (parent[end] == -1) return {};  // Няма път

    vector<int> path;
    for (int v = end; v != start; v = parent[v]) {
        path.push_back(v);
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    return path;
}

Сложност: \(O(V + E)\).

Приложения: - Най-кратък път в непретеглен граф (BFS гарантира минималния брой ребра) - Проверка дали граф е двуделен (оцветяване в два цвята) - Намиране на всички върхове на разстояние \(k\) от даден връх - 0-1 BFS за графи с тегла 0 и 1

2. Най-кратък път (Shortest Path)

2.1. Алгоритъм на Дейкстра (Dijkstra)

Алгоритъмът на Дейкстра намира най-краткия път от начален връх до всички останали върхове в граф с неотрицателни тегла. Използва приоритетна опашка за винаги да обработва върха с най-малко разстояние.

Идея: Постепенно "релаксираме" разстоянията, винаги избирайки най-близкия необработен връх.

Пълна имплементация с възстановяване на път: 

const long long INF = 1e18;
vector<pair<int, int>> adj[MAXN];  // {съсед, тегло}
long long dist[MAXN];
int parent[MAXN];

void dijkstra(int start) {
    fill(dist, dist + n, INF);
    fill(parent, parent + n, -1);
    dist[start] = 0;

    // Min-heap: {разстояние, връх}
    priority_queue<pair<long long, int>, 
                   vector<pair<long long, int>>, 
                   greater<pair<long long, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); 
        pq.pop();

        // Пропускаме остарели записи
        if (d > dist[u]) continue;

        // Релаксация на съседите
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

// Възстановяване на най-кратък път
vector<int> getPath(int start, int end) {
    if (dist[end] == INF) return {};  // Няма път

    vector<int> path;
    for (int v = end; v != -1; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

Сложност: \(O((V + E) \log V)\) с binary heap, \(O(V^2)\) с масив.

Важно: Дейкстра не работи коректно при отрицателни тегла!

Пример задача: Намиране на най-кратък път от град A до град B в мрежа от градове.

2.2. Алгоритъм на Белман-Форд (Bellman-Ford)

Bellman-Ford работи с отрицателни тегла и може да открива отрицателни цикли. Алгоритъмът релаксира всички ребра \(V-1\) пъти.

Идея: Ако има път с най-много \(k\) ребра, то след \(k\) итерации разстоянието ще бъде коректно.

Пълна имплементация: 

struct Edge {
    int from, to;
    long long weight;
};

vector<Edge> edges;
long long dist[MAXN];
int parent[MAXN];

bool bellmanFord(int start, int n) {
    fill(dist, dist + n, INF);
    fill(parent, parent + n, -1);
    dist[start] = 0;

    // Релаксация V-1 пъти
    for (int i = 0; i < n - 1; i++) {
        for (auto& e : edges) {
            if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
                dist[e.to] = dist[e.from] + e.weight;
                parent[e.to] = e.from;
            }
        }
    }

    // Проверка за отрицателен цикъл
    for (auto& e : edges) {
        if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
            return false;  // Има отрицателен цикъл
        }
    }

    return true;  // Няма отрицателен цикъл
}

// Намиране на всички върхове, достижими чрез отрицателен цикъл
void findNegativeCycleNodes(int n) {
    bool relaxed[MAXN] = {};

    // Още V итерации - разстоянията продължават да намаляват
    // само за върхове в/достижими от отрицателен цикъл
    for (int i = 0; i < n; i++) {
        for (auto& e : edges) {
            if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
                dist[e.to] = -INF;  // Маркираме като "безкрайно малко"
                relaxed[e.to] = true;
            }
        }
    }
}

Сложност: \(O(V \cdot E)\) - по-бавен от Дейкстра, но по-универсален.

Оптимизация: Можем да спрем по-рано, ако в някоя итерация няма релаксация.

Приложение: Задачи с отрицателни тегла, арбитраж във финанси.

2.3. Алгоритъм на Флойд-Уоршал (Floyd-Warshall)

Floyd-Warshall намира най-краткия път между всички двойки върхове чрез динамично програмиране. Използва се за малки графи (до \(\approx\) 400-500 върха).

Идея: \(dp[k][i][j]\) = най-кратък път от \(i\) до \(j\), използвайки само върхове \(0...k\) като междинни. Може да се оптимизира до 2D масив.

Пълна имплементация: 

const long long INF = 1e18;
long long dist[MAXN][MAXN];
int next[MAXN][MAXN];  // За възстановяване на път

void floydWarshall(int n) {
    // Инициализация
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = INF;
            }
            next[i][j] = -1;
        }
    }

    // Добавяме ребрата
    for (auto [u, v, w] : edges) {
        dist[u][v] = w;
        next[u][v] = v;
    }

    // Основен алгоритъм
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next[i][j] = next[i][k];
                    }
                }
            }
        }
    }

    // Проверка за отрицателни цикли
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) {
            // Има отрицателен цикъл, достижим от i
        }
    }
}

// Възстановяване на път от u до v
vector<int> reconstructPath(int u, int v) {
    if (next[u][v] == -1) return {};  // Няма път

    vector<int> path = {u};
    while (u != v) {
        u = next[u][v];
        path.push_back(u);
    }
    return path;
}

Сложност: \(O(V^3)\) - три вложени цикъла.

Приложения: - Намиране на транзитивно затваряне на граф - Откриване на отрицателни цикли - Минимакс/максимин пътища (с модификация)

3. Минимално Покриващо Дърво (MST)

Минималното покриващо дърво е подмножество от ребрата, което свързва всички върхове с минимална обща сума на теглата.

3.1. Алгоритъм на Крускал (Kruskal)

Крускал сортира всички ребра по тегло и ги добавя едно по едно, ако не образуват цикъл. Използва Disjoint Set Union (DSU) за ефективна проверка.

Пълна имплементация: 

struct Edge {
    int u, v;
    long long weight;

    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

// Disjoint Set Union (Union-Find)
int parent[MAXN], rankDSU[MAXN];

void initDSU(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rankDSU[i] = 0;
    }
}

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // Path compression
    }
    return parent[x];
}

bool unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return false;  // Вече в едно множество

    // Union by rank
    if (rankDSU[px] < rankDSU[py]) swap(px, py);
    parent[py] = px;
    if (rankDSU[px] == rankDSU[py]) rankDSU[px]++;

    return true;
}

long long kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end());  // Сортиране по тегло
    initDSU(n);

    long long mstWeight = 0;
    vector<Edge> mstEdges;  // Ребрата в MST

    for (auto& e : edges) {
        if (unite(e.u, e.v)) {  // Ако не образуват цикъл
            mstWeight += e.weight;
            mstEdges.push_back(e);

            if (mstEdges.size() == n - 1) break;  // MST е готово
        }
    }

    // Проверка дали графът е свързан
    if (mstEdges.size() != n - 1) {
        return -1;  // Няма MST (графът е несвързан)
    }

    return mstWeight;
}

Сложност: \(O(E \log E)\) заради сортирането.

3.2. Алгоритъм на Прим (Prim)

Прим изгражда MST инкрементално, започвайки от произволен връх и винаги добавяйки най-евтиното ребро, което свързва дървото с нов връх.

Пълна имплементация: 

vector<pair<int, long long>> adj[MAXN];  // {съсед, тегло}
bool inMST[MAXN];

long long prim(int start, int n) {
    fill(inMST, inMST + n, false);

    // Min-heap: {тегло, {връх, от-къде}}
    priority_queue<pair<long long, pair<int, int>>,
                   vector<pair<long long, pair<int, int>>>,
                   greater<pair<long long, pair<int, int>>>> pq;

    long long mstWeight = 0;
    vector<pair<int, int>> mstEdges;

    // Започваме от start
    pq.push({0, {start, -1}});

    while (!pq.empty()) {
        auto [w, vp] = pq.top();
        auto [v, from] = vp;
        pq.pop();

        if (inMST[v]) continue;  // Вече в MST

        inMST[v] = true;
        mstWeight += w;
        if (from != -1) {
            mstEdges.push_back({from, v});
        }

        // Добавяме съседите в опашката
        for (auto [u, ew] : adj[v]) {
            if (!inMST[u]) {
                pq.push({ew, {u, v}});
            }
        }
    }

    // Проверка дали всички върхове са в MST
    for (int i = 0; i < n; i++) {
        if (!inMST[i]) return -1;  // Графът е несвързан
    }

    return mstWeight;
}

Сложност: \(O(E \log V)\) с приоритетна опашка.

Кога да използваме кой: - Крускал: По-лесен за имплементация, добър за разредени графи - Прим: По-ефективен за плътни графи, по-добър за динамични модификации

4. Топологично Сортиране

Топологичното сортиране подрежда върховете на DAG (Directed Acyclic Graph) така, че за всяко ребро \(u \to v\), \(u\) се появява преди \(v\) в подредбата. Съществува само за ациклични графи.

4.1. DFS подход

Използваме DFS и добавяме върховете в резултата при излизане от рекурсията (postorder), след това обръщаме реда.

Имплементация: 

vector<int> adj[MAXN];
bool visited[MAXN];
vector<int> topoOrder;

void topoDFS(int u) {
    visited[u] = true;

    for (int v : adj[u]) {
        if (!visited[v]) {
            topoDFS(v);
        }
    }

    topoOrder.push_back(u);  // Добавяме при излизане
}

vector<int> topologicalSort(int n) {
    fill(visited, visited + n, false);
    topoOrder.clear();

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            topoDFS(i);
        }
    }

    reverse(topoOrder.begin(), topoOrder.end());
    return topoOrder;
}

4.2. Алгоритъм на Кан (Kahn's Algorithm)

Използва входящата степен (indegree) на всеки връх. Започваме с върховете с indegree 0 и постепенно "премахваме" ребрата.

Имплементация: 

vector<int> adj[MAXN];
int indegree[MAXN];

vector<int> kahnTopologicalSort(int n) {
    fill(indegree, indegree + n, 0);

    // Изчисляваме входяща степен
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            indegree[v]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topoOrder;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);

        // "Премахваме" ребрата от u
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // Ако не сме включили всички върхове, има цикъл
    if (topoOrder.size() != n) {
        return {};  // Графът има цикъл
    }

    return topoOrder;
}

Сложност: \(O(V + E)\) за двата подхода.

Приложения: - Планиране на задачи със зависимости - Разрешаване на dependencii в build системи - Определяне на реда на курсове с prerequisites

Пример: Даден е списък от курсове и prerequesite-и. В какъв ред трябва да вземете курсовете?

5. Практични Съвети и Често Срещани Грешки

5.1. Избор на подходящ алгоритъм

Таблица за избор на алгоритъм:

Задача Условия Алгоритъм
Най-кратък път Непретеглен граф BFS
Най-кратък път Положителни тегла Dijkstra
Най-кратък път Отрицателни тегла Bellman-Ford
Всички двойки път Малък граф (\(V \leq 500\)) Floyd-Warshall
MST Разреден граф Kruskal
MST Плътен граф Prim
Проверка за цикли DAG Топологично сортиране

5.2. Често срещани грешки

1. Използване на Dijkstra с отрицателни тегла 

// ГРЕШНО! Dijkstra не работи с отрицателни тегла
// Използвайте Bellman-Ford вместо това

2. Забравяне на проверка за остарели записи в Dijkstra 

// ПРАВИЛНО:
if (d > dist[u]) continue;  // Много важно!

3. Грешна инициализация на dist масив 

// ГРЕШНО:
memset(dist, INF, sizeof(dist));  // Заявява байтове!

// ПРАВИЛНО:
fill(dist, dist + n, INF);

4. Integer overflow при пътища 

// Използвайте long long за разстояния!
vector<long long> dist(n, INF);

5.3. Оптимизации

0-1 BFS: За графи с тегла само 0 и 1, използвайте deque вместо priority_queue: 

void bfs01(int start) {
    vector<long long> dist(n, INF);
    deque<int> dq;

    dist[start] = 0;
    dq.push_back(start);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;

                if (w == 0) {
                    dq.push_front(v);  // Тегло 0 - предимство
                } else {
                    dq.push_back(v);   // Тегло 1 - накрая
                }
            }
        }
    }
}

6. Задачи за упражнение

Леки задачи (за начинаещи):

  1. CSES - Building Roads: Намиране на компоненти с DFS/BFS
  2. CSES - Message Route: Най-кратък път с BFS
  3. CSES - Labyrinth: Обхождане на лабиринт с BFS
  4. Codeforces 277A: Свързани компоненти

Средни задачи:

  1. CSES - Shortest Routes I: Dijkstra
  2. CSES - Shortest Routes II: Floyd-Warshall
  3. CSES - Road Reparation: MST с Kruskal
  4. CSES - Course Schedule: Топологично сортиране
  5. Codeforces 20C: Dijkstra с възстановяване на път
  6. CSES - High Score: Bellman-Ford с отрицателни цикли

Трудни задачи:

  1. CSES - Flight Discount: Dijkstra с модификации
  2. UVa 558: Wormholes (Bellman-Ford)
  3. CSES - Investigation: Броене на най-кратки пътища
  4. Codeforces 295B: Floyd-Warshall с модификации

🏁 Заключение

Графовите алгоритми са фундаментална част от състезателното програмиране и информатичните олимпиади. Ключът към успеха е:

  1. Разбиране кога кой алгоритъм да използваме - вижте таблицата по-горе
  2. Внимание към детайлите - проверка за overflow, правилна инициализация, обработка на ъгловите случаи
  3. Практика - решавайте много задачи, за да затвърдите концепциите
  4. Анализ на сложността - винаги проверявайте дали избраният алгоритъм ще се справи със ограниченията

Овладяването на тези алгоритми ще ви даде силна основа за решаване на сложни графови задачи в олимпиади като IOI, CEOI и Balkan OI. Успех!