Графы: универсальный инструмент для связей — Блог
$ cat learn/03-graphs-intro.md

Графы: универсальный инструмент для связей

Алгоритмы Графы BFS DFS Топологическая сортировка

Графы: универсальный инструмент для связей

История

Теория графов родилась в 1736 году в статье Леонарда Эйлера о “Кенигсбергских мостах”. Эйлер доказал, что невозможно пройти по всем семи мостам Кенигсберга, не проходя ни один дважды.

Кенигсберг (1736):

    A ─────── B
    │        │
    │   N    │
    │        │
    D ─────── C

Можно ли пройти A→B→C→D→A, пройдя каждый мост ровно один раз?
Ответ Эйлера: НЕТ!

В XX веке графы стали основой computer science:

  • 1950-е: первые алгоритмы на графах
  • 1970-е: теоретико-множественный подход к алгоритмам
  • Сегодня: социальные сети, маршрутизация, зависимости пакетов

Реальные примеры из жизни

Социальные сети

Петр ─── Мария ─── Анна
  │        │
  │        └── Сергей
  │
  └─────────── Оля
       │          │
       └───── Иван

Каждый пользователь — вершина
Подписки/дружба — ребра

Дорожная сеть

        Москва
        /    \
   Калуга    Нижний Новгород
      │           │
      │       Владимир
      │           │
      └── Рязань ───

Города — вершины (100)
Дороги — ребра
Вес ребра = расстояние (км)

Зависимости пакетов (npm, pip)

boot loader → kernel → shell → app
              ↓
         network driver

Нельзя установить app, пока не установлены все зависимости!

Организационная схема компании

        CEO
        /  \
      CTO CPO
      /    /
   Dev  Design
    |
  Junior

Как это работает

Определения

  • Вершина (vertex/node) — объект, точка
  • Ребро (edge/link) — связь между вершинами
  • Путь — последовательность рёбер
  • Цикл — путь, начинающийся и заканчивающийся в одной вершине

Виды графов

Неориентированный          Ориентированный (directed)
     A ─── B                   A → B
     │    │                    ↓
     │    │                    ↓
     D ─── C                   D ← C

A connected to B         A points to B
                        D points to C

Взвешенный                 Невзвешенный
     A──(5)──B              A──���───B
     │         │           │
     (3)       (2)         │
     │         │           │
     D──(1)──C              D──────C

Представление графов

Матрица смежности (Adjacency Matrix)

    A B C D
  A 0 1 0 1
  B 1 0 1 0    Граф:
  C 0 1 0 1      A ── B
  D 1 0 1 0      │   │
                 D ── C

// adjacencyMatrix.h
#define MAXVERNUM 100
#define INFINITY 200

typedef struct {
    char vexs[MAXVERNUM];      // имена вершин
    int edges[MAXVERNUM][MAXVERNUM]; // матрица весов
    int numVertexes, numEdges;
} MGraph;

// Создание графа
void createMGraph(MGraph *G) {
    scanf("%d %d", &G->numVertexes, &G->numEdges);
    
    // Читаем вершины
    for (int i = 0; i < G->numVertexes; i++) {
        scanf(" %c", &G->vexs[i]);
    }
    
    // Инициализируем матрицу
    for (int i = 0; i < G->numVertexes; i++) {
        for (int j = 0; j < G->numVertexes; j++) {
            G->edges[i][j] = (i == j) ? 0 : INFINITY;
        }
    }
    
    // Читаем ребра
    for (int k = 0; k < G->numEdges; k++) {
        char v1, v2;
        int w;
        scanf(" %c %c %d", &v1, &v2, &w);
        
        int i = findVertex(G, v1);
        int j = findVertex(G, v2);
        
        G->edges[i][j] = w;
        G->edges[j][i] = w; // для неориентированного
    }
}

Список смежности (Adjacency List)

A → B → D
B → A → C
C → B → D
D → A → C

Граф:
A ── B
│   │
D ── C

// adjacencyList.h
typedef struct EdgeNode {
    int adjvex;           // индекс вершины
    int weight;          // вес (для взвешенного)
    struct EdgeNode *next;
} EdgeNode;

typedef struct {
    char data;           // данные вершины
    EdgeNode *firstEdge;  // первый сосед
} VertexNode;

typedef struct {
    VertexNode adjList[MAXVERNUM];
    int numVertexes, numEdges;
} ALGraph;

Матрица vs Список

ХарактеристикаМатрицаСписок
ПамятьO(V²)O(V + E)
Проверка смежностиO(1)O(degree)
Обход соседейO(V)O(degree)

Обходы графов

DFS (Depth-First Search) — поиск в глубину

       A
      / \
     B   C
    /   / \
   D   E   F

DFS: A → B → D → B → A → C → E → C → F
     или
     A → C → F → C → E → C → A → B → D

GDS: A → B → D → B → A → C → E → C → F

Аналогия: лабиринт — идём до упора, потом возвращаемся.

// traverse.c
void DFS(ALGraph *G, int i, int *visited) {
    visited[i] = 1;
    printf("%c ", G->adjList[i].data);
    
    EdgeNode *p = G->adjList[i].firstEdge;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

void DFSTraverse(ALGraph *G) {
    int visited[MAXVERNUM] = {0};
    for (int i = 0; i < G->numVertexes; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
}

BFS (Breadth-First Search) — поиск в ширину

       A
      / \
     B   C
    /   / \
   D   E   F

BFS: A → B → C → D → E → F

Аналогия: волна распространяется от центра.

void BFS(ALGraph *G, int i, int *visited) {
    Queue q;
    create_queue(&q);
    
    visited[i] = 1;
    insert(&q, i);
    
    while (!is_empty(&q)) {
        int v = delete(&q);
        printf("%c ", G->adjList[v].data);
        
        EdgeNode *p = G->adjList[v].firstEdge;
        while (p) {
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = 1;
                insert(&q, p->adjvex);
            }
            p = p->next;
        }
    }
}

Сравнение DFS и BFS

ХарактеристикаDFSBFS
СтруктураСтекОчередь
ПамятьO(h)O(V)
nearest firstнетда
Кратчайший путьнетда
Зацикливаниеда (mark visited)да (mark visited)

Топологическая сортировка

Задача: упорядочить задачи с зависимостями.

Задачи:
1. Подготовить резюме
2. Найти вакансии
3. Пройти собеседование
4. Получить оффер

Зависимости:
- Чтобы найти вакансии → нужно резюме
- Чтобы пройти собеседование → нужно найти вакансии
- Чтобы получить оффер → нужно пройти собеседование

Топологический порядок:
Резюме → Вакансии → Собеседование → Оффер

Алгоритм Кана (Kahn’s Algorithm)

Шаг 1: Найти все вершины с in-degree = 0 (нет входящих рёбер)

Шаг 2: Удалить их и все исходящие рёбра

Повторять пока граф не пуст

// topological_sort.c
void topologicalSort(MGraph *G) {
    int inDegree[MAXVERNUM] = {0};
    Queue q;
    create_queue(&q);
    
    // Считаем in-degree для каждой вершины
    for (int i = 0; i < G->numVertexes; i++) {
        for (int j = 0; j < G->numVertexes; j++) {
            if (G->edges[i][j] != 0 && G->edges[i][j] != INFINITY) {
                inDegree[j]++;
            }
        }
    }
    
    // Добавляем вершины с in-degree = 0
    for (int i = 0; i < G->numVertexes; i++) {
        if (inDegree[i] == 0) {
            insert(&q, i);
        }
    }
    
    // Обрабатываем очередь
    int count = 0;
    while (!is_empty(&q)) {
        int i = delete(&q);
        printf("%c ", G->vexs[i]);
        count++;
        
        // Уменьшаем in-degree соседей
        for (int j = 0; j < G->numVertexes; j++) {
            if (G->edges[i][j] != 0 && G->edges[i][j] != INFINITY) {
                inDegree[j]--;
                if (inDegree[j] == 0) {
                    insert(&q, j);
                }
            }
        }
    }
    
    if (count < G->numVertexes) {
        printf("\nОшибка: граф содержит цикл!\n");
    }
}

Пример работы

Граф зависимостей:

    CV ──────┐
    ↓        │
  Jobs ────→ Interview ───→ Offer

in-degree:
CV: 0
Jobs: 1
Interview: 1
Offer: 1

Шаг 1: CV имеет in-degree = 0 → добавляем в очередь
Шаг 2: Удаляем CV, уменьшаем in-degree Jobs → Jobs = 0 → добавляем
Шаг 3: Удаляем Jobs, уменьшаем in-degree Interview → Interview = 0 → добавляем
Шаг 4: Удаляем Interview, уменьшаем in-degree Offer → Offer = 0 → добавляем
Шаг 5: Удаляем Offer

Результат: CV → Jobs → Interview → Offer

Примеры использования

1. Поиск кратчайшего пути (GPS)

Маршрут и�� точки A в точку F:

    A──2──B──1──F
    │   │      │
    4  3      2
    │   │      │
    D──1──C──2──E

BFS дает кратчайший путь по количеству рёбер:
A → B → F (2 ребра)

2. Анализ социальных сетей

Найти "центральных" пользователей:

- Кто больше всех влияет?
- Кто является "мостом" между группами?
- Кто с кем связан через 3 рукопожатия?

3. Зависимости пакетов

npm install react:
- react → require react-dom
- react-dom → require react
- OK!

Установить app:
- app → require lib_a → require lib_b → require cycle!
- Ошибка: цикл обнаружен!

Сложность операций

ОперацияМатрицаСписок
СозданиеO(V²)O(V + E)
DFSO(V + E)O(V + E)
BFSO(V²)O(V + E)
Топ. сортировкаO(V²)O(V + E)

Ключевые выводы

  1. Графы — универсальная структура для связей между объектами

  2. Представление: матрица (плотные графы) vs список (разреженные)

  3. DFS — идём в глубину, использует стек, находит любой путь

  4. BFS — идём в ширину, использует очередь, находит кратчайший путь

  5. Топологическая сортировка — упорядочивание с зависимостями (DAG)

Что дальше?

Следующий этап — алгоритмы на графах:

  • MST (Prim, Krushal) — минимальное остовное дерево
  • Кратчайшие пути (Dijkstra, Bellman-Ford)
  • Floyd-Warshall — все кратчайшие пу��и
← Все статьи