Представление графов: как компьютер видит связи

🎯 Зачем это нужно?

Представь, что ты разрабатываешь Instagram 📱. У тебя миллиард пользователей, каждый может подписаться на любого другого. Как хранить эти связи в памяти компьютера? Один неправильный выбор - и твоё приложение “упадёт” от нехватки RAM!

🌐 Netflix использует граф “пользователь-фильм” для рекомендаций 🚗 Uber строит граф дорог для поиска маршрутов
🧠 GPT представляет текст как граф связей между словами 📊 PageRank Google = граф ссылок между сайтами

Разные задачи требуют разных представлений графов. Сегодня разберёмся, какое выбрать!

📚 История вопроса

В 1950-х граф из 10 вершин казался огромным - помещался на бумаге. Сегодня Facebook работает с графом из 3 миллиардов вершин! 🤯

Первые программисты хранили граф как “кто с кем связан” - список пар. Но когда граф стал большим, на поиск одной связи уходили секунды. Нужны были новые способы!

💡 Интуиция

Граф - это как карта метро 🚇. У нас есть станции (вершины) и переходы между ними (рёбра). Но как эту карту объяснить компьютеру?

Способ 1: Матрица смежности = большая таблица размером N×N. В клетке (i,j) пишем 1, если есть ребро из i в j, иначе 0.

Способ 2: Список смежности = для каждой вершины список её соседей. Как телефонная книга: “Вася знает Петю, Машу, Олега”.

[МЕДИА: image_01] Описание: Сравнение матрицы смежности и списка смежности для простого графа Промпт: “educational comparison of adjacency matrix vs adjacency list representation, simple graph with 5 vertices, clear visual distinction between matrix table and list format, modern clean design, blue and orange color scheme”

📐 Формальное определение

Для графа G = (V, E), где |V| = n:

Матрица смежности A: A[i][j] = {1, если (i,j) ∈ E; 0, иначе}

Список смежности: Массив L[1..n], где L[i] содержит всех соседей вершины i

Сложности:

где m = |E| - число рёбер, degree - степень вершины

🔍 Примеры с разбором

Пример 1: Социальная сеть школы

У нас 4 ученика: Аня(1), Боря(2), Вера(3), Гоша(4) Дружат: Аня-Боря, Аня-Вера, Боря-Гоша

Матрица смежности:

   1 2 3 4
1 [0 1 1 0]
2 [1 0 0 1]  
3 [1 0 0 0]
4 [0 1 0 0]

Список смежности:

1: [2, 3]
2: [1, 4]
3: [1]
4: [2]

[МЕДИА: image_02] Описание: Визуализация графа социальной сети с матрицей и списком смежности Промпт: “social network graph visualization with 4 students, friendship connections, side-by-side comparison of adjacency matrix and list representations, educational style, friendly colors”

Пример 2: Анализ памяти для Instagram

Instagram: ~2 млрд пользователей, ~200 связей на пользователя в среднем

Матрица смежности: 2×10⁹ × 2×10⁹ × 1 байт = 4×10¹⁸ байт = 4 экзабайта! 💥

Список смежности: 2×10⁹ × 200 × 8 байт = 3.2 терабайта ✅

Очевидно, что матрица не поместится ни в какую память!

🎮 Практика

Базовый уровень 🟢

Задание 1: Для графа с рёбрами {(A,B), (B,C), (C,A)} построй матрицу и список смежности

Задание 2: Сколько памяти нужно для матрицы смежности графа из 1000 вершин?

Задание 3: В списке смежности вершина 5 имеет соседей [1,3,7,9]. Чему равна степень вершины 5?

Продвинутый уровень 🟡

Задание 4: YouTube имеет граф “видео рекомендует видео”. Оцени, какое представление лучше, если у каждого видео ~10 рекомендаций из 2 млрд видео

Задание 5: Реализуй функцию has_edge(u, v) для обоих представлений:

# Матрица
def has_edge_matrix(matrix, u, v):
    # твой код

# Список  
def has_edge_list(adj_list, u, v):
    # твой код

Задание 6: LinkedIn хочет найти всех друзей 2-го уровня пользователя. Какой алгоритм и представление выберешь?

Челлендж 🔴

Задание 7: Придумай гибридное представление для графа, где 90% вершин имеют степень ≤ 10, а 10% вершин имеют степень > 1000

Задание 8: TikTok хранит граф лайков: “пользователь лайкнул видео”. 1 млрд пользователей, 100 млн видео, в среднем 50 лайков на пользователя. Предложи оптимальную структуру данных

⚠️ Частые ошибки

❌ Ошибка: “Список смежности всегда лучше матрицы” ✅ Правильно: Выбор зависит от плотности графа и операций 💡 Почему: Для плотных графов (много рёбер) матрица может быть эффективнее

❌ Ошибка: “Матрица занимает O(n²) памяти - это всегда плохо”
✅ Правильно: Для небольших графов (n < 1000) это нормально 💡 Почему: Простота реализации и O(1) доступ компенсируют затраты памяти

❌ Ошибка: Путаю направленные и неориентированные графы при построении матрицы ✅ Правильно: В неориентированном графе A[i][j] = A[j][i] 💡 Почему: Если есть ребро (i,j), то есть и ребро (j,i)

🎓 Главное запомнить

✅ Матрица смежности: O(n²) памяти, O(1) проверка ребра - для плотных графов ✅ Список смежности: O(n+m) памяти, быстрый обход соседей - для разрежённых графов
✅ Выбор зависит от: размера графа, плотности рёбер, типа операций

🔗 Связь с другими темами

Представление графов - основа для всех алгоритмов на графах. Дальше изучим:

• BFS/DFS: обход графа для поиска путей
• Dijkstra: кратчайшие пути в графе с весами
• Graph Neural Networks: как нейросети работают с графами в ML