Структура данных: Граф

Граф состоит из конечного набора вершин(узлов) и набора ребер, которые соединяют пару узлов.

Графы используются для решения многих реальных задач. К примеру для представления сетей: городских или телефонных или даже компьютерных сетей. Также представление графа заложено почти в каждой социальной сети.

Data Science: Алгоритмы и Структуры данных

Возвращение легенды: самый востребованный практикум Зерокодера по Claude Code снова пройдёт в августе.

CEO университета Зерокодер Кирилл Пшинник проведёт ещё один бесплатный онлайн-практикум, где в прямом эфире покажет, почему вокруг Claude Code столько шума и как использовать его на полную мощность.

На практикуме разберут:

• Как получить доступ к Claude Code из России и начать работать без ограничений;
• Как запускать сразу несколько ИИ-агентов для одного проекта;
• Как за 15 минут собрать рабочий сайт практически без ручного кода;
• Как автоматизировать аналитику и рутинные задачи без дополнительных сервисов;

Бонус: в конце практикума расскажем, как пользоваться Claude Code бесплатно и оформить виртуальную карту для оплаты других AI-сервисов

P.S. Это специальный повтор одного из самых популярных практикумов Зерокодера по Claude Code. Жмите на ссылку и успевайте зарегистрироваться!

Приложения где используется алгоритм обхода BFS графа

1. Нахождения пути или кратчайшего пути. Ибо при использовании BFS мы всегда достигаем нужной вершины из заданного источника, используя минимальное количество ребер.

2. Поисковые роботы или сканеры. Исследуется страница источник и проходится все в ширину, для оценки самих страниц.

3. Социальные сети. По факту любая ваша соц. сеть - состоит сугубо из графа. И обходы графа тут используются как раз BFS в основном.

4. Системы GPS-навигации. Опять же для построения маршрута

5. Сборка мусора во многих языках программирования, написана как раз через обход графа в BFS стиле (.NET platform)

6. Для проверки двудольности графа

Data Science: Алгоритмы и Структуры данных

Представление графа через Set и hash суммы

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

Набор отличается от вектора 2мя вещами:

1. он хранит элементы в отсортированном порядке (так как мы используем Set)

2. дублирование элементов не допускается (так как по прежнему, это свойство самого Set)

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

Поскольку множества внутренне реализованы как деревья двоичного поиска (очень важный факт), ребро между двумя вершинами можно искать за время O (log V), где V - количество вершин в графе.

На картинке представлен пример того самого сета.

Завтра рассмотрим оптимизацию данного подхода

Data Science: Алгоритмы и Структуры данных

Оптимизация представления графов по средствам Set и hash-функций

Основа этой оптимизации будет заключаться в использовании - unordered set. Его реализацию вы можете встретить в c++, однако, может и реализовать ее сами.

Unordered_set может содержать ключ любого типа - предопределенную или определяемую пользователем структуру данных, но когда мы определяем ключ типа, определяемого пользователем, нам нужно указать нашу функцию сравнения, в соответствии с которой будут сравниваться ключи. По факту это единственная сложность в реализации данной структуры данных. Завтра обсудим, как же ее реализовать всё таки!

Data Science: Алгоритмы и Структуры данных

Задача: найти материнскую вершину в графе

Итак нам дан граф, нам нужно найти материнскую вершину.

Материнской вершиной в графе G = (V, E) называется вершина v такая, что все остальные вершины в G могут быть достигнуты путем из v.

Есть несколько кейсов, которые позволяют это сделать.

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

2. Ненаправленный/Направленный исключенный граф - в этом случае нет материнских вершин, поскольку мы не можем достичь всех узлов из выбранного

3. Направленный связнфй граф - в этом случае мы должны найти вершину v в графе, что удостоена условию "маринский"

Data Science: Алгоритмы и Структуры данных

Можно ли собрать полезный рабочий инструмент с ИИ за один вечер?
Проверим на первой бесплатной лаборатории вайб-кодинга от Зерокодера

Не будем тратить эфир на теорию и бесконечные промпты. Возьмем 100 реальных отзывов клиентов и прямо на глазах соберем приложение, которое само их проанализирует.

Но главное – формат самой лаборатории.

Это не запись заранее подготовленного кейса и не лекция, где эксперт показывает идеальный результат. Задачу собираем прямо в Zoom: от постановки до готового инструмента. Во время занятия можно задавать вопросы ведущему и разбираться с процессом вместе.

В итоге получается реальный продукт, который можно использовать для конкурентного анализа, поиска идей и улучшения своих продуктов или адаптировать под задачи клиентов и продавать как готовое решение.

И это только первая задача. Каждую неделю – новый кейс и новый инструмент: приложения, дашборды, автоматизации и AI-помощники.

Забрать первое участие в лаборатории бесплатно – по ссылке

Простой алгоритм для задачи нахождения материнской вершины

Самым тривиальным способом решения данной задачи будет выполнение BFS/DFS для всех вершин и выяснить: сможем ли мы достичь всех вершин из этой вершины.

Данный подход неэффективен, если наши графы достаточно большие, ибо его время будет O(V(E + V)). Однако, это самый простой путь для решения подобных задач. К тому же, мы недавно рассмотрели BFS / DFS

Data Science: Алгоритмы и Структуры данных

Транспонирование графа

У многих графов есть еще одно условие, то что их можно транспонировать. Давайте сначала разберемся с тем, что же такое транспонирование.

Транспонированый ориентированный граф G - это другой ориентированный граф на том же множестве вершин со всеми ребрами, перевернутыми по сравнению с ориентацией соответствующих ребер в G. То есть, если G содержит ребро (u, v), то обратное (transpose / reverse) G содержит ребро (v, u) и наоборот.

Алгоритм транспонирования графа

Мы проходим по списку смежности, и когда мы находим вершину v в списке смежности вершины u, которая указывает на ребро от u до v в основном графе, мы просто добавляем ребро от v до u в транспонированный граф, т.е. добавляем u в смежность список вершины v нового графа. Таким образом, обходя списки всех вершин основного графа, мы можем получить транспонированный граф. Таким образом, общая временная сложность алгоритма составляет O (V + E), где V - количество вершин графа, а E - количество ребер графа.

Data Science: Алгоритмы и Структуры данных