Алгоритмы с нуля

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

Суть Граф это вершины + рёбра. Неориентированный против ориентированного. Невзвешенный против взвешенного. Два представления: список смежности (O(V+E) память, соседи O(степень)) и матрица смежности (O(V²) память, проверить ребро O(1)). Таблица компромисса.

◷ 24 min

Ты знаешь деревья: корень в верхней части, дети ниже, рёбра указывают вниз. Дерево это особый граф — один где есть ровно один путь между любыми двумя узлами и нет циклов. Теперь расслабь то правило. Граф это любое собрание вершин (узлов) соединённых рёбрами — без ограничения. Ты можешь иметь циклы (A → B → A), множественные пути между узлами, рёбра указывающие обе стороны (или одна сторона), и веса на рёбрах. Графы везде: дорожные сети (города это вершины, дороги это рёбра), социальные сети (люди это вершины, дружбы это рёбра), сеть (страницы это вершины, ссылки это рёбра). Прежде чем ты сможешь искать граф, найти путь, или вычислить что-либо, ты должен выбрать как представить его в памяти. Этот урок обхватывает два главных представления: список смежности и матрица смежности. Каждый меняет память на время в другом пути.

Цель

После этого урока ты можешь определить граф и его словарь (вершина, ребро, сосед, степень, путь, цикл, связный). Ты можешь различить ориентированный от неориентированного, взвешенный от невзвешенного. Ты можешь построить список смежности в коде (массив/карта от вершины к списку соседей) и прочитать результат — зная что это используется O(V + E) память и позволяет тебе итерировать соседей вершины за O(степень) время. Ты можешь построить матрицу смежности (V×V сетка где ячейка [u][v] отмечает ребро) и понять что это используется O(V²) память но отвечает на “есть ли ребро u-v?” за O(1) время. Ты можешь сравнить компромиссы: список побеждает для редких графов (мало рёбер), матрица побеждает для плотных графов (много рёбер) и для быстрой проверки ребра. Ты трассируешь оба представления на конкретном графе, и ты можешь кодировать оба. Ты узнаёшь что деревья это графы без циклов. Следующий урок это поиск в глубину (DFS), где ты исследуешь граф ребро за ребром.

Идея

Что это граф?

Граф это пара (V, E):

V: набор вершин (или узлов). Пример: {A, B, C, D}.
E: набор рёбер соединяющих пары вершин. Пример: {(A, B), (B, C), (C, D), (D, A)}.

Визуально:

  A --- B
  |     |
  D --- C

Здесь V = {A, B, C, D} и E = {(A, B), (B, C), (C, D), (D, A)}.

Ключевой словарь

Ребро: Связь между двумя вершинами.
Вершина (или узел): Точка в графе.
Сосед (или соседний): Если есть ребро (u, v), то u и v это соседи; v это сосед u.
Степень вершины: Количество рёбер связанных с ней. В квадрате выше, каждая вершина имеет степень 2.
Путь: Последовательность вершин где последовательные вершины это соседи. Пример: A → B → C это путь.
Цикл: Путь, который начинается и заканчивается на одной вершине, с по крайней мере одним ребром. Пример: A → B → C → D → A это цикл.
Связный (неориентированный): Граф где есть путь между каждой парой вершин.

Ориентированный против неориентированного

Неориентированный: Ребро (A, B) значит ты можешь идти от A к B и от B к A. Это симметричный.
Ориентированный: Ребро A → B значит ты можешь идти от A к B только. Это односторонний. Часто называется орграф.

Пример:

Неориентированный:   A --- B       Ориентированный:   A --> B
                                                       ^     |
                                                       +---- C

В неориентированном графе, ты можешь пересечь A ↔ B. В ориентированном графе, ты можешь идти A → B → C, но не обратно от C к A (нет ребра C → A).

Взвешенный против невзвешенного

Невзвешенный: Каждое ребро не имеет значения; либо оно существует, либо оно не существует.
Взвешенный: Каждое ребро имеет числовой вес (стоимость, расстояние, ёмкость). Пример: дорожная сеть где вес это расстояние в км.

Пример:

Невзвешенный:   A --- B       Взвешенный:   A --5-- B
                                            |       /
                                            3      2
                                            |     /
                                            C----

Деревья это графы

Дерево это граф без циклов. Более точно: дерево это связный граф с V вершинами и ровно V-1 рёбрами. Дерево не имеет циклов, и есть ровно один путь между любыми двумя вершинами.

Два представления: список смежности и матрица смежности

Графы это абстрактны. Чтобы работать с ними в коде, ты должен выбрать конкретное представление. Два главных выбора:

Список смежности: Для каждой вершины, храни список её соседей (или исходящих рёбер).
Матрица смежности: V×V сетка где ячейка [u][v] указывает есть ли ребро от u к v.

Мы детализируем оба.

Пример графа для обоих представлений

Давайте используем простой ориентированный граф с 4 вершинами (0, 1, 2, 3) и 5 рёбрами:

Визуально:

  0 → 1
  ↓   ↓
  2 → 3
  ↑   ↓
  +---+

Представление 1: Список смежности

Для каждой вершины, список её соседей (исходящие рёбра).

0: [1, 2]
1: [3]
2: [3]
3: [2]

В коде, используй массив массивов, массив карт, или карта списков (в зависимости от языка и есть ли вершины 0-индексные целые или ярлыки как “A”, “B”, “C”).

Представление 2: Матрица смежности

4×4 матрица. Ячейка [u][v] = 1 если есть ребро u → v, иначе 0.

Строка 0 это [0, 1, 1, 0]: вершина 0 указывает на 1 и 2. Строка 1 это [0, 0, 0, 1]: вершина 1 указывает на 3. Строка 3 это [0, 0, 1, 0]: вершина 3 указывает на 2.

Список рёбер (краткое упоминание)

Третье представление: список рёбер. Пример: [(0, 1), (0, 2), (1, 3), (2, 3), (3, 2)]. Это редко главное представление для общей работы графов, но это используется в некоторых специализированных алгоритмах (как Краскал для минимального остовного дерева).

Код

Построение списка смежности


      1
      // Для ориентированного графа с V вершинами (0 к V-1)
    

      2
      function buildAdjacencyList(V, edges) {
    

      3
      // Создай массив списков (один за вершину)
    

      4
      const adj = Array.from({ length: V }, () => []);
    

      5
       
    

      6
      // Для каждого ребра [u, v], добавь v к списку соседей u
    

      7
      for (const [u, v] of edges) {
    

      8
        adj[u].push(v);
    

      9
      }
    

      10
       
    

      11
      return adj;
    

      12
      }
    

      13
       
    

      14
      // Пример: граф с 4 вершинами, 5 рёбер
    

      15
      const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 2]];
    

      16
      const adj = buildAdjacencyList(4, edges);
    

      17
      console.log(adj);
    

      18
      // Вывод:
    

      19
      // [ [1, 2], [3], [3], [2] ]

L3 Создай массив V пустых списков, один за вершину.
L6 Для каждого ребра (u, v), добавь v к списку u.
L11 Этот граф имеет рёбра 0→1, 0→2, 1→3, 2→3, 3→2.
L12 adj[0] = [1, 2]: вершина 0 имеет соседей 1 и 2.

Построение матрицы смежности


      1
      // Для ориентированного графа с V вершинами (0 к V-1)
    

      2
      function buildAdjacencyMatrix(V, edges) {
    

      3
      // Создай V×V матрицу, инициализировано к 0
    

      4
      const adj = Array.from({ length: V }, () => Array(V).fill(0));
    

      5
       
    

      6
      // Для каждого ребра [u, v], установи adj[u][v] = 1
    

      7
      for (const [u, v] of edges) {
    

      8
        adj[u][v] = 1;
    

      9
      }
    

      10
       
    

      11
      return adj;
    

      12
      }
    

      13
       
    

      14
      // Пример: одинаковый граф
    

      15
      const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 2]];
    

      16
      const adj = buildAdjacencyMatrix(4, edges);
    

      17
      console.log(adj);
    

      18
      // Вывод:
    

      19
      // [ [ 0, 1, 1, 0 ],
    

      20
      //   [ 0, 0, 0, 1 ],
    

      21
      //   [ 0, 0, 0, 1 ],
    

      22
      //   [ 0, 0, 1, 0 ] ]

L3 Создай V×V матрицу, все ячейки первоначально 0.
L6 Для каждого ребра (u, v), установи ячейку [u][v] = 1.
L14 adj[0][1] = 1: есть ребро от 0 к 1.

Пошаговый разбор


      1
      edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 2]];
    

      2
      adj_list = buildAdjacencyList(4, edges);
    

      3
      adj_matrix = buildAdjacencyMatrix(4, edges);

Сложность

Список смежности: O(V + E) память, быстрая итерация соседей

Ты хранишь одну запись за вершину, плюс одну запись за ребро. Итого: V + E записей.

Память: O(V + E). Для редких графов (E ≪ V²), это намного меньше чем O(V²).
Итерируй соседей u: O(степень(u)). Ты просто читаешь список u.
Проверь есть ли ребро (u, v)?: O(степень(u)). Ты должен сканировать список соседей u.
Вставь/удали ребро: O(степень(u)) чтобы найти и удалить. Для некоторых вариантов, O(1) если ты используешь множество вместо списка.

Пример: дерево с 1,000 вершинами имеет ровно 999 рёбер. Список смежности использует O(1000 + 999) ≈ 2000 памяти. Матрица смежности будет использовать 1000² = 1,000,000 ячеек.

Матрица смежности: O(V²) память, O(1) проверка ребра

Ты хранишь V×V сетку.

Память: O(V²). Всегда, независимо от количества рёбер.
Проверь есть ли ребро (u, v)?: O(1). Просто посмотри на ячейку [u][v].
Итерируй соседей u: O(V). Ты должен сканировать строку u.
Вставь/удали ребро: O(1). Просто установи или очисти ячейку [u][v].

Пример: одинаковое 1,000-вершинное дерево тратит впустую 1,000,000 ячеек даже хотя только 999 используются.

Когда используй каждый

Операция	Список смежности	Матрица смежности
Память	O(V + E)	O(V²)
Итерируй соседей u	O(степень(u))	O(V)
Проверь “ребро (u, v)?”	O(степень(u))	O(1)
Вставь/удали ребро	O(степень(u)) или O(1)	O(1)
Лучший для	Редкие графы	Плотные графы

Редкие против плотных

Редкий: Мало рёбер, E ≈ O(V). Используй список смежности. Память O(V), время проверить ребро O(V) (малые списки).
Плотный: Много рёбер, E ≈ O(V²). Используй матрицу смежности. Память это уже O(V²), и быстрая проверка ребра это стоит это.
Главное правило: Если E ≈ V или E < V log V, предпочитай список смежности. Если E > V² / 4, предпочитай матрицу смежности.

Практика 0 / 6

Какая сложность памяти списка смежности для ориентированного графа с V вершинами и E рёбер?

В матрице смежности, сколько времени это занимает, чтобы проверить есть ли ребро от вершины u к вершине v?

Чтобы итерировать всех соседей вершины u, какое представление это типично быстрее: список смежности или матрица смежности?

Граф имеет 5 вершин и 6 рёбер. Сколько памяти делает список смежности используют против матрицы смежности?

В ориентированном графе, входящая степень вершины это количество входящих рёбер. Со списком смежности, как ты нашёл бы входящую степень вершины u?

Граф имеет V = 100 вершин. Для какого количества рёбер E делает список смежности используют одинаковую память как матрица смежности?

lesson.inset.undefined

Почему представления имеют значение. Одинаковый граф может быть реализован двумя способами, с очень разными представлениями. Если твой алгоритм проверяет “есть ли ребро (u, v)?” миллионы раз, матрица смежности это игровой переломный момент. Если ты часто итерируешь всех соседей, список смежности побеждает. Большинство реальных сетей (социальные графы, дорожные сети, сеть) это редкие — миллиарды узлов, но не все пары соединены — так списки смежности доминируют. Но если ты работаешь с малым, плотным графом (как полный граф), матрица это проще и быстрее.

lesson.inset.undefined

Путание “посещения ребра” с “посещением соседей.” Когда ты построишь список смежности от списка рёбер, ты итерируешь рёбра (не вершины). Если ты видишь E рёбер, ты итерируешь E раз. Но когда ты используешь список чтобы итерировать соседей вершины u, время зависит от степени u, не на E. Вершина со степенью 2 имеет 2 соседей, даже если граф имеет 1000 рёбер.

lesson.inset.undefined

Несвязные графы. Граф это несвязный если некоторые вершины имеют нет пути к другим. Оба представления обрабатывают это нормально: вершина может иметь нет соседей (пустой список, или строка нулей в матрице). Граф это просто не полностью связный. Ты всё ещё можешь спросить “есть ли ребро (u, v)?” и получить “нет.”

lesson.inset.undefined

Неориентированные графы. Если граф это неориентированный, ребро (u, v) значит ты можешь идти обе стороны: u → v и v → u. В списке смежности, ты должен добавить оба (u к списку v и v к списку u). В матрице, установи оба [u][v] и [v][u] к 1. Это удваивает память относительно ориентированного графа с одинаковыми рёбра, но представления остаются одинаковые — просто симметричные.

Проверь себя

Викторина

Объясни что такое список смежности и матрица смежности, и опиши ключевой компромисс между ними.

Итог

Граф это вершины + рёбра. Различи ориентированный (односторонний) от неориентированного (симметричный), и взвешенный (рёбра имеют стоимости) от невзвешенного. Используй словарь: вершина, сосед, степень, путь, цикл.

Два главных представления:

Список смежности: Для каждой вершины, список её соседей. O(V + E) память. Быстрая итерация соседей O(степень(u)), медленная проверка ребра O(степень(u)).
Матрица смежности: V×V сетка, ячейка [u][v] = 1 если ребро существует. O(V²) память. Мгновенная проверка ребра O(1), медленная итерация соседей O(V).

Выбери список для редких графов (мало рёбер), матрица для плотных графов или если быстрота проверки ребра это критична. Дерево это граф без циклов — это редкий (E = V - 1).

Следующее: поиск в глубину (DFS) — как исследовать граф следуя рёбра и посещая каждую достижимую вершину.

Продолжить восхождение ↑Поиск в глубину (DFS)