Этот вопрос проверяет понимание графов как структуры данных и их применений.
Граф — это набор вершин (узлов) и рёбер (связей между ними). Графы используются для моделирования отношений между объектами. Пример: социальные сети (вершины — пользователи, рёбра — дружба), карты (вершины — города, рёбра — дороги).
Графы являются универсальной структурой для представления сетей.
Типы графов:
Направленные: Рёбра имеют направление (например, Twitter подписки).
Ненаправленные: Рёбра без направления (например, Facebook дружба).
Взвешенные: Рёбра имеют вес (например, расстояние между городами).
Примеры использования:
Социальные сети: Анализ связей между пользователями.
Маршрутизация: Поиск кратчайшего пути в навигаторах.
Рекомендательные системы: Анализ взаимодействий пользователей.
Алгоритмы для графов:
Поиск в ширину (BFS) и глубину (DFS).
Алгоритм Дейкстры для кратчайшего пути.
Поиск циклов и компонент связности.
