Skip to content

🌐 Понятие за граф

Графите са фундаментални структури от данни, които се използват за моделиране на взаимовръзки между обекти. Те намират приложение в различни области като компютърни науки, логистика, мрежови анализ, социални мрежи и много други. Изучаването на графите предоставя основа за разбиране на сложни алгоритми и приложения, които се използват широко в практиката.

📋 Съдържание

  1. Дефиниция и видове графи
  2. Основни компоненти на графите
  3. Видове представяне на графи
    • Матрица на съседство
    • Списък на съседство
    • Списък на ребра
  4. Операции върху графи
  5. Обхождане на графи
    • BFS (Breadth-First Search)
    • DFS (Depth-First Search)
  6. Специални видове графи
    • Цикли
    • Дървета
    • Бипартитни графи
  7. Приложения на графите
  8. Примери и код
  9. Заключение

🖋️ Дефиниция и видове графи

Граф \( G = (V, E) \) се състои от: - \( V \): Набор от върхове (или възли). - \( E \): Набор от ребра, които свързват двойки върхове.

Видове графи

  1. Насочени графи (Directed Graphs):
  2. Ребрата имат посока (\( (u, v) \neq (v, u) \)).

  3. Пример: Граф на уеб страници, където всяка страница има линкове към други.

  4. Ненасочени графи (Undirected Graphs):

  5. Ребрата нямат посока (\( (u, v) = (v, u) \)).

  6. Пример: Моделиране на приятелства в социална мрежа.

  7. Тежести върху графи (Weighted Graphs):

  8. Всяко ребро има асоциирана тежест или разход (напр. разстояние, време, разходи).

  9. Свързани графи (Connected Graphs):

  10. Съществува път между всяка двойка върхове.

  11. Дървета (Trees):

  12. Свързан граф без цикли.

  13. Специален случай на граф, използван в много алгоритми.

  14. Бипартитни графи (Bipartite Graphs):

  15. Върховете могат да бъдат разделени на два множества, като всяко ребро свързва връх от едното множество с връх от другото.

⚙️ Основни компоненти на графите

  1. Върхове (Vertices): Обектите, които се свързват.
  2. Ребра (Edges): Връзките между върховете.
  3. Степен на върха (Degree):
  4. Ненасочен граф: Брой инцидентни ребра.
  5. Насочен граф:
    • In-degree: Брой входящи ребра.
    • Out-degree: Брой изходящи ребра.
  6. Пътища (Paths): Последователност от върхове, свързани с ребра.
  7. Цикли (Cycles): Затворен път, при който първият и последният връх съвпадат.

📊 Видове представяне на графи

1. Матрица на съседство

2D масив \( n \times n \), където \( A[i][j] \) е: - 1 (или теглото), ако има ребро между \( i \) и \( j \). - 0, ако няма ребро.

Пример:

Ненасочен граф с върхове \( \{A, B, C\} \):

A B C
A 0 1 1
B 1 0 1
C 1 1 0

2. Списък на съседство

Списък, където всеки връх е свързан с набор от съседни върхове.

Пример:

A: B, C
B: A, C
C: A, B

3. Списък на ребра

Списък от двойки \( (u, v) \), представляващи ребрата на графа.

Пример:

(A, B)
(A, C)
(B, C)

🔄 Операции върху графи

  1. Добавяне на върхове: Добавя нов връх в графа.
  2. Премахване на върхове: Премахва съществуващ връх и свързаните с него ребра.
  3. Добавяне на ребра: Създава връзка между два върха.
  4. Премахване на ребра: Премахва съществуваща връзка между два върха.

🔍 Обхождане на графи

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

Обхожда графа ниво по ниво.

Алгоритъм:

  1. Добави началния връх в опашка.
  2. Маркирай го като посетен.
  3. Докато опашката не е празна:
  4. Извади върха и го обработи.
  5. Добави съседите му в опашката, ако не са посетени.

Примерен код (C++):

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(int start, vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 4},
        {1, 5},
        {1, 2, 5},
        {3, 4}
    };

    bfs(0, graph);
    return 0;
}

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

Обхожда графа, като се спуска по всяка възможна пътека.

Примерен код (C++):

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 4},
        {1, 5},
        {1, 2, 5},
        {3, 4}
    };

    vector<bool> visited(graph.size(), false);
    dfs(0, graph, visited);
    return 0;
}

🌟 Специални видове графи

  1. Циклични графи: Графи, които съдържат поне един цикъл.
  2. Ациклични графи: Графи без цикли.
  3. Планарни графи: Графи, които могат да се нарисуват в равнина без пресичане на ребра.
  4. Плътни и редки графи:
  5. Плътни: Броят на ребрата е близък до максималния.
  6. Редки: Броят на ребрата е малък спрямо върховете.

🌟 Приложения на графите

  1. Социални мрежи: Моделиране на връзки между потребителите.
  2. Комуникационни мрежи: Оптимизация на маршрути и управление на трафик.
  3. Алгоритми за търсене: Двоично дърво, лабиринти и маршрути.
  4. Изкуствен интелект: Графи на състояния, използвани в машинно обучение и планиране.
  5. Логистика: Оптимизация на доставки и маршрути.

📚 Заключение

Графите са мощен инструмент за решаване на сложни задачи, предоставящи интуитивен начин за представяне на връзки между обекти. Чрез различните техники за представяне, обхождане и анализиране, те намират приложение в широк спектър от индустрии. Познаването на графите и свързаните алгоритми е ключово за разбирането и разработката на съвременни технологии. Препоръчва се задълбочено изучаване на основните концепции и редовна практика с реални примери, за да се овладее тяхното приложение.