Что значит построить граф в информатике
Графы: основы теории, алгоритмы поиска
Aug 22, 2020 · 6 min read
Возможно, вы уже знакомы с понятием спортивного программирования и знаете, что оно помогает развить навыки решения проблем и прокачать технические знания о структурах данных и алгоритмах.
Одной из важнейших составляющих спортивного программирования является изучение алгоритмов. В этой статье мы охватим большое количество алгоритмов, в том числе все алгоритмы на графах, знание которых понадобится вам для успешного решения задач из теории графов на соревнованиях по программированию. Конечно, одних теоретических знаний алгоритмов недостаточно, и вам придётся набить руку в решении практических задач на таких сайтах, как Codeforces. Настоящая же статья представит вам инструменты, необходимые для освоения важных графовых алгоритмов. Итак, приступим.
Что такое граф?
Г р афы, в понимании программистов, — это не те графики, которые мы изучали в школе. Это не столбиковые диаграммы или гистограммы.
С точки зрения компьютерных наук и дискретной математики, графы — это абстрактный способ представления типов отношений, например дорог, соединяющих города, и других видов сетей. Графы состоят из рёбер и вершин. Вершина — это точка на графе, а ребро — это то, что соединяет две точки на графе.
В условиях задач из теории графов на соревнованиях по программированию обычно говорится о таких вещах, как сети и решётки.
Вот список всех терминов, относящихся к теории графов, которые вам нужно знать:
Представление графов в коде
Для того, чтобы использовать алгоритмы на графах в коде, сначала нам нужно разобраться, как осуществляется представление графов в коде. Весь следующий код будет на C++, так как для спортивного программирования я предпочитаю именно этот язык за его скорость и встроенные функции, позволяющие упростить написание решений задач.
Будут показаны два способа представления графов: матрицы смежности и списки смежности. Больше вам пригодится представление графов в виде списка смежности.
Матрицы смежности
Матрица смежности представляет собой граф в виде двумерной матрицы с размерами V x V, где V — количество вершин графа. Матрицы смежности лучше всего применять, когда V² примерно равно E (числу рёбер), то есть когда граф плотный. Запись a_ij обозначает, сколько рёбер соединяют вершину i и вершину j.
Списки смежности
Другой распространенный способ представления графов в коде — списки смежности. Суть в том, что вы создаёте списки соседей для каждой вершины, а затем помещаете все эти списки в другой список. Их лучше всего применять, когда в графе небольшое количество рёбер, то есть когда граф разрежённый. Если у вас взвешенный граф, т.е. каждое ребро графа имеет какой-то вес, то в списке будут содержаться пары для рёбер (сосед, вес).
Поиск в глубину
Теперь, когда мы научились представлять графы в коде, можем приступить к изучению некоторых алгоритмов на графах! Начнём с поиска в глубину (DFS) и завершим поиском в ширину (BFS). Чтобы не загромождать статью, алгоритмы поиска пути не будут здесь рассматриваться (интересующиеся могут ознакомиться с алгоритмом поиска кратчайшего пути Беллмана-Форда).
Поиск в глубину — это один из базовых алгоритмов на графах. Он применяется для поиска расстояния от одной вершины до других вершин в графе. Это алгоритм обхода.
Поиск в глубину помечает каждую вершину в графе одной из двух меток: посещённая или не посещённая. Алгоритм помечает каждую вершину как посещённую, если удаётся избежать циклов. Он работает следующим образом:
Поиск в ширину
Поиск в ширину — ещё один алгоритм обхода графов. Вместе с алгоритмом поиска вглубь он составит большую часть увлекательных соревнований по программированию, по крайней мере, тех из них, что относятся к графам.
Поиск в ширину тоже помещает каждую вершину в графе в одну из двух категорий: посещённых или непосещённых. И цель у обоих алгоритмов одна и та же: помечать каждую вершину в графе как посещённую, если удаётся избежать циклов. Вот как работает алгоритм поиска в ширину:
Как видите, алгоритм поиска в ширину очень похож на алгоритм поиска в глубину. Однако вместо того, чтобы спускаться вниз по ветви графа или дерева, как это делает алгоритм поиска в глубину, алгоритм поиска в ширину проходит каждый уровень.
Заключение
Освоив теоретическую часть, касающуюся двух самых важных алгоритмов обхода на графах, вам остаётся только практиковаться, чтобы использовать эти алгоритмы в соревнованиях по программированию. Я бы порекомендовал для начала Codeforces: решайте задачи, помеченные тегами bfs и dfs с рейтингом до 1400. Когда почувствуете, что справляетесь с ними, увеличьте сложность.
Отработка навыков решения алгоритмических задач, особенно алгоритмов на графах, поможет вам побеждать на соревнованиях по программированию и успешно проходить технические собеседования. Вперёд — к успехам!
Графы: основы теории, алгоритмы поиска
Возможно, вы уже знакомы с понятием спортивного программирования и знаете, что оно помогает развить навыки решения проблем и прокачать технические знания о структурах данных и алгоритмах.
Одной из важнейших составляющих спортивного программирования является изучение алгоритмов. В этой статье мы охватим большое количество алгоритмов, в том числе все алгоритмы на графах, знание которых понадобится вам для успешного решения задач из теории графов на соревнованиях по программированию. Конечно, одних теоретических знаний алгоритмов недостаточно, и вам придётся набить руку в решении практических задач на таких сайтах, как Codeforces. Настоящая же статья представит вам инструменты, необходимые для освоения важных графовых алгоритмов. Итак, приступим.
Что такое граф?
Графы, в понимании программистов, — это не те графики, которые мы изучали в школе. Это не столбиковые диаграммы или гистограммы.
С точки зрения компьютерных наук и дискретной математики, графы — это абстрактный способ представления типов отношений, например дорог, соединяющих города, и других видов сетей. Графы состоят из рёбер и вершин. Вершина — это точка на графе, а ребро — это то, что соединяет две точки на графе.
Пример графа
В условиях задач из теории графов на соревнованиях по программированию обычно говорится о таких вещах, как сети и решётки.
Вот список всех терминов, относящихся к теории графов, которые вам нужно знать:
Представление графов в коде
Для того, чтобы использовать алгоритмы на графах в коде, сначала нам нужно разобраться, как осуществляется представление графов в коде. Весь следующий код будет на C++, так как для спортивного программирования я предпочитаю именно этот язык за его скорость и встроенные функции, позволяющие упростить написание решений задач.
Будут показаны два способа представления графов: матрицы смежности и списки смежности. Больше вам пригодится представление графов в виде списка смежности.
Матрицы смежности
Матрица смежности представляет собой граф в виде двумерной матрицы с размерами V x V, где V — количество вершин графа. Матрицы смежности лучше всего применять, когда V² примерно равно E (числу рёбер), то есть когда граф плотный. Запись a_ij обозначает, сколько рёбер соединяют вершину i и вершину j.
Списки смежности
Другой распространенный способ представления графов в коде — списки смежности. Суть в том, что вы создаёте списки соседей для каждой вершины, а затем помещаете все эти списки в другой список. Их лучше всего применять, когда в графе небольшое количество рёбер, то есть когда граф разрежённый. Если у вас взвешенный граф, т.е. каждое ребро графа имеет какой-то вес, то в списке будут содержаться пары для рёбер (сосед, вес).
Поиск в глубину
Теперь, когда мы научились представлять графы в коде, можем приступить к изучению некоторых алгоритмов на графах! Начнём с поиска в глубину (DFS) и завершим поиском в ширину (BFS). Чтобы не загромождать статью, алгоритмы поиска пути не будут здесь рассматриваться (интересующиеся могут ознакомиться с алгоритмом поиска кратчайшего пути Беллмана-Форда).
Поиск в глубину — это один из базовых алгоритмов на графах. Он применяется для поиска расстояния от одной вершины до других вершин в графе. Это алгоритм обхода.
Поиск в глубину помечает каждую вершину в графе одной из двух меток: посещённая или не посещённая. Алгоритм помечает каждую вершину как посещённую, если удаётся избежать циклов. Он работает следующим образом:
Поиск в ширину
Поиск в ширину — ещё один алгоритм обхода графов. Вместе с алгоритмом поиска вглубь он составит большую часть увлекательных соревнований по программированию, по крайней мере, тех из них, что относятся к графам.
Поиск в ширину тоже помещает каждую вершину в графе в одну из двух категорий: посещённых или непосещённых. И цель у обоих алгоритмов одна и та же: помечать каждую вершину в графе как посещённую, если удаётся избежать циклов. Вот как работает алгоритм поиска в ширину:
Как видите, алгоритм поиска в ширину очень похож на алгоритм поиска в глубину. Однако вместо того, чтобы спускаться вниз по ветви графа или дерева, как это делает алгоритм поиска в глубину, алгоритм поиска в ширину проходит каждый уровень.
Заключение
Освоив теоретическую часть, касающуюся двух самых важных алгоритмов обхода на графах, вам остаётся только практиковаться, чтобы использовать эти алгоритмы в соревнованиях по программированию. Я бы порекомендовал для начала Codeforces: решайте задачи, помеченные тегами bfs и dfs с рейтингом до 1400. Когда почувствуете, что справляетесь с ними, увеличьте сложность.
Отработка навыков решения алгоритмических задач, особенно алгоритмов на графах, поможет вам побеждать на соревнованиях по программированию и успешно проходить технические собеседования. Вперёд — к успехам!
Алгоритмы на графах — Часть 0: Базовые понятия
Как оказалось тема алгоритмов интересна Хабра-сообществу. Поэтому я как и обещал, начну серию обзоров «классических» алгоритмов на графах.
Так как публика на Хабре разная, а тема интересна многим, я должен начать с нулевой части. В этой части я расскажу что такое граф, как он представлен в компьютере и зачем он используется. Заранее прошу прощения у тех кто это все уже прекрасно знает, но для того чтобы объяснять алгоритмы на графах, нужно сначала объяснить что такое граф. Без этого никак.
В математике, Граф — это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин, а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами).
Граф может быть ориентированным или неориентированным. В ориентированном графе, связи являются направленными (то есть пары в E являются упорядоченными, например пары (a, b) и (b, a) это две разные связи). В свою очередь в неориентированном графе, связи ненаправленные, и поэтому если существует связь (a, b) то значит что существует связь (b, a).
Неориентированный граф: Соседство (в жизни). Если (1) сосед (3), то (3) сосед (1). См рис. 1.а
Ориентированный граф: Ссылки. Сайт (1) может ссылаться на сайт (3), но совсем не обязательно (хотя возможно) что сайт (3) ссылается сайт (1). См рис. 1.б
Путь в графе это конечная последовательность вершин, в которой каждые две вершины идущие подряд соединены ребром. Путь может быть ориентированным или неориентированным в зависимости от графа. На рис 1.а, путем является например последовательность [(1), (4), (5)] на рис 1.б, [(1), (3), (4), (5)].
У графов есть ещё много разных свойств (например они могут быть связными, двудольными, полными), но я не буду описывать все эти свойства сейчас, а в следующих частях когда эти понятия понадобятся нам.
Представление графов
Существует два способа представления графа, в виде списков смежности и в виде матрицы смежности. Оба способа подходят для представления ориентированных и неориентированных графов.
Матрица смежности
Этот способ является удобным для представления плотных графов, в которых количество рёбер (|E|) примерно равно количеству вершин в квадрате (|V| 2 ).
В данном представлении мы заполняем матрицу размером |V| x |V| следущим образом:
A[i][j] = 1 (Если существует ребро из i в j)
A[i][j] = 0 (Иначе)
Данный способ подходит для ориентированных и неориентированных графов. Для неориентированных графов матрица A является симметричной (то есть A[i][j] == A[j][i], т.к. если существует ребро между i и j, то оно является и ребром из i в j, и ребром из j в i). Благодаря этому свойству можно сократить почти в два раза использование памяти, храня элементы только в верхней части матрицы, над главной диагональю)
Понятно что с помощью данного способа представления, можно быстро проверить есть ли ребро между вершинами v и u, просто посмотрев в ячейку A[v][u].
С другой стороны этот способ очень громоздкий, так как требует O (|V| 2 ) памяти для хранения матрицы.
На рис. 2 приведены представления графов из рис. 1 с помощью матриц смежности.
Списки смежности
Данный способ представления больше подходит для разреженных графов, то есть графов у которых количество рёбер гораздо меньше чем количество вершин в квадрате (|E| 2 ).
В данном представлении используется массив Adj содержащий |V| списков. В каждом списке Adj[v] содержатся все вершины u, так что между v и u есть ребро. Память требуемая для представления равна O (|E| + |V|) что является лучшим показателем чем матрица смежности для разреженных графов.
Главный недостаток этого способа представления в том, что нет быстрого способа проверить существует ли ребро (u, v).
На рис. 3 приведены представления графов из рис. 1 с помощью списков смежности.
Применение
Те кто дочитал до этого места, наверное задали себе вопрос, а где же собственно я смогу применить графы. Как я и обещал я буду стараться приводить примеры. Самый первый пример который приходит в голову это социальная сеть. Вершинами графа являются люди, а ребрами отношения (дружба). Граф может быть неориентированным, то есть я могу дружить только с теми кто дружит со мной. Либо ориентированным (как например в ЖЖ), где можно добавить человека в друзья, без того чтобы он добавлял вас. Если же он да добавит вас вы будете «взаимными друзьями». То есть будет существовать два ребра: (Он, Вы) и (Вы, Он)
Ещё одно из применений графа, которое я уже упоминал это ссылки с сайта на сайт. Представим Вы хотите сделать поисковую систему и хотите учесть на какие сайты есть больше ссылок (например сайт A), при этом учитывать сколько сайтов ссылается на сайт B, который ссылается на сайт A. У вас будет матрица смежности этих ссылок. Вы захотите ввести какую то систему подсчёта рейтинга, которая делает какие то подсчёты на этой матрице, ну, а дальше… это Google (точнее PageRank) =)
Заключение
Это небольшая часть теории которая понадобится нам чтобы для следующих частей. Надеюсь вам было понятно, а главное понравилось и заинтересовало читать дальнейшие части! Оставляйте свои отзывы и пожелания в комментариях.
В следующей части
BFS — Алгоритм поиска в ширину
Библиография
Кормен, Лайзерсон, Риверст, Штайн — Алгоритмы. Построение и анализ. Издательство Вильямс, 2007.
Словарь терминов теории графов
Граф — статья в английской Википедии
Статья это кросс-пост из моего блога — «Programing as is — записки программиста»
Теория Графов. Часть 1 Введение и классификация графов
«Графы являются одним из объединяющих понятий информатики – абстрактное представление, которое описывает организацию транспортных систем, взаимодействие между людьми и телекоммуникационные сети. То, что с помощью одного формального представления можно смоделировать так много различных структур, является источником огромной силы для образованного программиста». Стивен С. Скиена
Введение
Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.
Схема Московского метро
Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.
Отмечу, что число вершин обозначается буквой n:
Число рёбер обозначается буквой m:
Таким образом граф задается и обозначается парой V,E:
Также определение графа рассказывается в этой статье на Хабре (https://habr.com/ru/post/65367/)
Неформально граф является совокупностью точек и линий. Линии в котором задаются парой вершин, расположенных не важно в каком порядке.
Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.
Нулевой граф
Только вот множество V вершины пустым быть не может. Ведь множество E рёбра задается парой неупорядоченных вершин множества V. Две вершины образующие ребро, называются концами этого ребра.
Множество E задается парой неупорядоченных вершин множества V.
Пример: Пусть множество V = <1,2,3,4,5>. Тогда множество E =
Граф будет выглядеть следующим образом:
Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.
Степень записывают, как:
Максимальная степень, то есть какое количество степеней вообще присутствуют в графе обозначаются, как:
Формула суммы степеней для G = V,E выглядит так:
То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!
А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:
Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?
Классификации графов
Первым признаком классификации является отсутствие или наличие ориентации у ребер.
Ребро является неориентированным если у него нет понятия начала или конца. То есть оба его конца равноправны. Такой граф называется неориентированным, обыкновенным или неографом.
Неориентированный граф
Ориентированное ребро обозначается стрелкой. И указывает ориентацию от вершины к вершине. То есть данный граф имеет начало и конец. И называется он ориентированным или орграфом.
Ориентированный граф
Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.
Смешанный граф
Вторым признаком является отсутствие или наличие кратных ребер.
Мультиграф
Граф в котором кратных ребер нет, является простым графом. В простом графе мы просто называем пару вершин для идентификации ребра, но в мультиграфе такое уже не сработает, так как одна и та же пара вершин будет указывать на два ребра и не понятно что к чему будет относится. Поэтому если вы повстречаете мультиграф, то вы должны обозначить каждое ребро отдельно.
Заключение
В данной стать я не рассмотрел, понятия смежности и инцидентности, однако я решил их рассмотреть в следующий раз. Также хочу отметить, что более подробно виды графов, я буду рассматривать в следующих статьях. Если у вас есть вопросы, предложения или я где-то допустил ошибки, то прошу написать их в комментариях.
Иллюстративное введение в теорию графов и её применение
Не понимаете теорию графов? Эта статья для вас. Расскажем об основных элементах теории графов и рассмотрим применение теории.
Теория графов представляет собой один из наиболее важных и интересных, но в то же время один из самых сложных и непонятных разделов в информатике.
Понимание и использование графов делает нас более квалифицированными специалистами. По крайней мере, так должно быть. Граф – это множество вершин V и множество рёбер E, содержащих упорядоченную пару G=(V, E).
Пытаясь изучать теорию графов и реализовать некоторые алгоритмы, многие программисты просто прекращают этим заниматься, потому что считают данное занятие слишком скучным.
Лучший способ освоить что-то – понять, как и где оно применяется. В этой статье мы покажем различные примеры применения теории графов, проиллюстрировав каждый из них.
Пусть эта статья покажется слишком детальной для опытных программистов, но, поверьте, подробные объяснения гораздо эффективнее сжатых определений.
Содержание:
Семь мостов Кёнигсберга
Начнём с того, с чем чаще всего сталкивается программист, читающий книгу про теорию графов – история про мосты и островы Калининграда. В Калининграде было семь мостов, соединяющих два больших острова, окруженных рекой Преголя, и две части материка, разделенные той же рекой.
В 18 веке это был Кёнигсберг, город Пруссии, и на этой территории было гораздо больше мостов. Задача или просто головоломка состояла в том, что необходимо было найти такой маршрут, который проходил через каждый мост ровно один раз. Вот иллюстрированный вид семи мостов Кёнигсберга в 18 веке:
Попробуйте решить эту головоломку. Посмотрите, сможете ли вы пройти по всем мостам ровно один раз.
Если вы знакомы с этой задачей, то знаете, что это невозможно. Даже если вы очень сильно пытались, в конечном итоге вам пришлось сдаться.
Иногда разумно сдаться быстро. Именно так решил эту проблему Эйлер – он сдался довольно скоро. Вместо того, чтобы пытаться решить головоломку, он пытался объяснить, почему это невозможно.
Давайте попробуем понять, как Эйлер думал, и как он нашёл решение.
Начнем с представления невозможного
Есть четыре разных места: два острова и две части материка. И семь мостов. Интересно узнать, существует ли какая-либо закономерность в отношении количества мостов, связанных с островами или материком (мы будем использовать термин “земля” для обозначения четырех различных мест)?
На первый взгляд кажется, что это похоже на какой-то шаблон. Есть нечётное количество мостов, связанных с каждой землёй. Если нужно пересечь каждый мост один раз, то вам достаточно зайти на землю и сойти с неё, если она имеет два моста.
На рисунке выше видно, что если вы заходите на землю, проходясь по одному мосту, вы всегда можете покинуть землю, пройдя по её второму мосту. Всякий раз, когда появляется третий мост, вы не сможете покинуть землю, как только войдёте в нее.
Если вы попытаетесь обобщить это рассуждение для одного участка земли, то увидите, что в случае чётного количества мостов всегда можно покинуть землю, а в случае нечётного – нет.
Изменим условие
Давайте добавим новый мост, чтобы узнать, как изменится количество общих соединённых мостов, и решит ли он проблему:
Теперь, когда у нас есть два четных (4 и 4) и два нечетных (3 и 5) числа мостов, соединяющих четыре части земли, давайте нарисуем новый маршрут с добавлением этого нового моста.
Переходим к графам
Мы увидели, что число чётных и нечётных мостов сыграло свою роль в определении возможного решения. Возникает вопрос. Количество мостов решает проблему? И должно ли это работать во всех случаях? Оказывается, это не так. Вот что сделал Эйлер. Он нашёл способ показать, что количество мостов имеет значение. Что более интересно, также имеет значение количество участков земли с нечётным количеством соединённых мостов. Именно тогда Эйлер начал преобразовывать земли и мосты в то, что мы знаем как графы. Вот как может выглядеть граф этой задачи (обратите внимание, что временно добавленного моста нет).
Важно отметить обобщение/абстрагирование задачи. Всякий раз, когда вы решаете определённую задачу, самое главное – обобщить решение. Конкретно в этом случае задача Эйлера состояла в том, чтобы обобщить эту задачу для решения подобных в будущем. Визуализация также помогает рассматривать проблему под другим углом. Изображения ниже – различные представления одной и той же задачи Кёнигсбергского моста.
Итак, графы – хороший выбор для визуализации задачи
Но сейчас нам нужно выяснить, как проблема Кёнигсбергских мостов может быть решена с использованием графов. Обратите внимание на количество линий, выходящих из каждого круга. С этого момента то, что мы называли “кругами”, будем называть вершинами, а “линии” – рёбрами.
Следующим важным моментом является так называемая степень вершины, число рёбер, связанных с вершиной. В нашем примере выше число мостов, связанных с землёй, может быть выражено как степень вершины.
Определение
Путь Эйлера конечного неориентированного графа G(V, E) является таким путём, что каждое ребро G появляется на нём один раз. Если G имеет путь Эйлера, то он называется графом Эйлера.
Теорема
Конечный неориентированный связный граф – это граф Эйлера тогда и только тогда, когда ровно две вершины имеют нечётную степень, или все вершины имеют чётную степень.
Новые термины
Прежде всего, давайте рассмотрим новые термины, встретившиеся в теореме и определении выше:
Некоторые из этих терминов мы затронем в следующих пунктах.
Графы могут быть ориентированными и неориентированными.
Это одно из интересных свойств графов. К примеру, возьмём Facebook и Twitter. “Дружба” в Facebook может быть легко представлена как неориентированный граф. Например, если Алиса является другом Боба, то Боб тоже является другом Алисы. Нет конкретного направления, оба дружат друг с другом.
Также обратите внимание на вершину, помеченную как Patrick: она особенная (нет друзей), т. к. отсутствуют рёбра. Это всё ещё часть графа, но в таком случае мы скажем, что этот граф несвязный (то же самое относится к Джону, Ашоту и Бету, поскольку они взаимосвязаны друг с другом, но отделены от других). В связном графе не существует недостижимых вершин, должен существовать путь между каждой парой вершин.
Вопреки примеру Facebook, если Алиса фолловит Боба в Twitter, это не означает, что Боб фолловит Алису. Таким образом, “follow” должен иметь индикатор направления, показывающий, какая вершина (пользователь) имеет направленное ребро (фолловит) к другой вершине (другого пользователя).
Вернёмся к графу Эйлера
Итак, почему мы обсуждали проблему Кёнигсбергских мостов и графы Эйлера в первую очередь? Это не так скучно, и, исследуя задачу и вышеизложенное решение, мы коснулись основных элементов графов (вершина, ребро, виды графов и т. п.), избегая сухого теоретического подхода. И нет, мы ещё не закончили с графами Эйлера и проблемой выше.
Теперь мы должны перейти к представлению графов на компьютерном уровне, поскольку это в большей степени интересует нас, программистов. Представляя граф в программе, мы сможем разработать алгоритм отслеживания пути графа, и, следовательно, выяснить, является ли он графом Эйлера.
Представление графов: введение
Это довольно утомительная задача, поэтому будьте терпеливы. Помните противостояние массивов и связных списков? Используйте массивы, если вам нужен быстрый доступ к элементу, используйте списки, если вам нужна быстрая вставка/удаление элемента и т.д. Вряд ли вы когда-нибудь сталкивались с проблемой, например, “как представить списки”. В случае графов фактическое представление действительно беспокоит, потому что сначала вы должны решить, как именно вы собираетесь представить граф. И поверьте, вам это не понравится. Список смежности, матрица смежности, или, может быть, список рёбер?
Бинарное дерево
Прежде всего, начнём с дерева. Должно быть, вы видели бинарное дерево по крайней мере один раз.
Просто потому, что оно состоит из вершин и рёбер, это граф. Вы также можете вспомнить, как обычно представлено бинарное дерево.
Это может показаться слишком простым для людей, знакомых с бинарными деревьями, однако всё же стоит проиллюстрировать это, чтобы все понимали, о чём идёт речь (обратите внимание, что мы всё ещё имеем дело с псевдокодом).
Если вы только начинаете разбираться с деревьями, внимательно прочитайте псевдокод выше, а затем следуйте инструкциям на рисунке ниже.
Бинарное дерево поиска
Бинарное дерево – это просто сочетание узлов, каждый из которых имеет левый и правый дочерние узлы. Бинарное дерево поиска полезно, поскольку оно применяет одно простое правило, которое позволяет быстро искать нужные значения. Бинарные деревья поиска держат свои значения в отсортированном порядке. Наиболее важным в деревьях является то, что они удовлетворяют свойству бинарного поиска. Значение каждого узла должно быть больше любого значения в левом поддереве и меньше любого ключа в правом поддереве.
Стоит отметить интересный момент относительно фразы “больше”, который имеет решающее значение для понимания того, как работает бинарное дерево поиска. Всякий раз, когда вы изменяете свойство на “больше или равно”, ваше дерево будет иметь возможность сохранять повторяющиеся значения при вставке новых узлов, в противном случае, оно будет держать только узлы с уникальными значениями. Проиллюстрируем простое бинарное дерево поиска.
Представление графов и бинарных деревьев (пример Airbnb)
Деревья – очень полезные структуры данных. Возможно, вы не реализовывали дерево с нуля в своих проектах. Но вы, вероятно, использовали их, даже не замечая. Давайте рассмотрим искусственный, но ценный пример и попытаемся ответить на вопрос “зачем”: “зачем использовать бинарное дерево поиска?”.
Как вы могли заметить, в бинарном дереве поиска есть поиск. Таким образом, всё, что нуждается в быстром поиске, следует поместить в бинарное дерево поиска. “Следует” не значит “надо”. Важно помнить, что главное – это решить задачу с помощью правильных инструментов. Существует много ситуаций, в которых простой связный список со сложностью O(N) будет лучше бинарного дерева со сложностью O(logN).
Как правило, мы будем использовать библиотеку BST, скорее всего std::map или std::set в C++. Однако в этом уроке мы вольны изобретать собственное колесо. BST реализована практически в любом современном языке программирования. Вы можете найти их в соответствующей документации вашего любимого языка.
Переходим к Airbnb
Приближаясь к «реальному примеру», вот проблема, которую мы попытаемся решить – Airbnb Home Search.
Как мы можем быстро искать дома на основе некоторого запроса с множеством фильтров? Это сложная задача. Она становится труднее, если учитывать то, что Airbnb хранит 4 миллиона списков. 
Таким образом, когда пользователи ищут дома, есть шанс, что они могут “коснуться” 4 миллионов записей, хранящихся в базе данных. Конечно, результаты ограничены «топ-листами“, показанными на домашней странице сайта, и пользователь почти никогда не бывает слишком любопытен, чтобы просмотреть миллионы списков. Предположим, что пользователь находит хороший дом, просмотрев не более 1000 предложений.
Наиболее важным фактором здесь является количество пользователей онлайн, т.к. от этого зависят структуры данных, выбор базы данных и архитектура проекта в целом. Очевидно, что если мы имеем только 100 пользователей, то можем не беспокоиться об этом вообще.
Если количество онлайн пользователей превышает миллион, мы должны продумать каждое решение в проекте. Именно поэтому компании нанимают лучших специалистов, стремясь к совершенству в предоставлении услуг.
Google, Facebook, Airbnb, Netflix, Amazon, Twitter и многие другие имеют дело с огромным количеством данных, и правильный выбор для обслуживания миллионов байт данных каждую секунду начинается с найма хороших инженеров. Всё, что нужно таким компаниям – это инженер, способный решать проблемы самым быстрым и эффективным способом.
Итак, вот классический пример. Пользователь посещает домашнюю страницу (мы по-прежнему говорим об Airbnb) и пытается отфильтровать все предложения, чтобы найти наилучшее соответствие. Как бы мы справились с этой проблемой?
Рассчитываем объём занимаемой памяти
Давайте начнём с нескольких предположений:
Сколько памяти потребуется для хранения текущих данных? Если мы имеем дело с 4 миллионами единиц данных, и, если мы, вероятно, знаем размер каждой единицы, можно получить требуемый размер памяти: 4M * sizeof(one_unit).
Рассмотрим объект “дом” и его свойства. По крайней мере, рассмотрим те свойства, с которыми мы будем иметь дело при решении проблемы (“дом” – это наша единица). Мы будем представлять его как структуру C++ в некотором псевдокоде. Вы можете легко преобразовать его в объект схемы MobgoDB или ещё во что-нибудь. Мы просто обсуждаем имена и типы свойств (подумайте об использовании bitfields или bitsets для экономии пространства).
Очевидно, эта структура не является совершенной. Она создана на основе фильтров Airbnb с помощью списков свойств, которые должны удовлетворить поисковые запросы. Это просто пример.
Рассматриваем объект AirbnbHome подробнее
Теперь мы должны вычислить, сколько байт в памяти займёт каждый объект AirbnbHome.
Имя дома
Фотографии
Фотографии хранятся в хранилищах, таких как Amazon S3 (насколько я знаю, это предположение верно для Airbnb, но опять же, Amazon S3 – это просто предположение).
URL фотографий
Учитывая тот факт, что не существует стандартного ограничения на URL-адреса, возьмём 2000 символов. Поэтому, учитывая, что в каждом объявлении есть 5 фотографий в среднем, это займёт
ID фотографий
ID хоста
Услуги
Например, если у дома есть стиральная машина:
Или немного более профессионально:
Правила дома, тип дома
Та же идея (которую мы реализовали для поля удобств), только для типа дома и правил дома.
Код страны, название города
Как уже упоминалось в комментариях кода выше, мы не будем хранить широту и долготу, чтобы избежать геопространственных запросов. Вместо этого мы сохраняем код страны и название города, чтобы сузить поиск по местоположению. Код страны может быть представлен как 2, 3 символа или 3 цифры. Мы сохраним числовое представление и будем использовать ushort для него. К (не)счастью, существует гораздо больше городов, чем стран, поэтому мы не можем использовать код города. Вместо этого мы будем хранить фактическое название города, сохраняя в среднем 50 байт для названия города и для исключительных случаев, таких как город с 85-буквенным названием.
Мы лучше используем дополнительную логическую переменную, которая указывает, что это тот конкретный сверхдлинный город (не пытайтесь его произнести). Таким образом, учитывая дополнительные расходы памяти на строки и векторы, мы добавим дополнительные 32 байта (на всякий случай) к окончательному размеру структуры. Мы также предположим, что мы работаем в 64-битной системе, хотя мы выбрали очень компактные значения для int и short.
Итог подсчёта
Переходим к следующей подзадаче
Теперь самая сложная часть задачи. Выбор правильной структуры данных для этой проблемы –(максимально эффективная фильтрация списков) не самая сложная задача. Самая трудная задача – поиск списков с помощью множества фильтров, заданных пользователем. Если бы был только один фильтр, эту задачу можно было бы легко решить. Предположим, что всё, что волнует пользователя, это цена, поэтому всё, что нам нужно – это найти объекты AirbnbHome с ценами, подходящими под заданный диапазон. Если мы будем использовать бинарное дерево поиска, вот как это будет выглядеть.
Если представить себе все 4 миллиона объектов, то это дерево вырастет очень сильно. Между прочим, дополнительные расходы памяти также растут, т.к. мы используем дерево для хранения объектов. Поскольку каждый родительский узел указывает на левый и правый дочерние элементы, он добавляет до 8 дополнительных байт каждому дочернему элементу (при условии, что это 64-разрядная система). Для 4 миллионов объектов это примерно 62МБ, что по сравнению с текущими 2ГБ выглядит довольно скромно.
Дерево на последнем рисунке показывает, что сложность алгоритма поиска любого элемента будет O(log N).
Вычислительная сложность алгоритмов
В большинстве случаев найти сложность алгоритма довольно просто. Прежде всего, стоит отметить, что мы всегда рассматриваем наихудший случай, т.е. максимальное количество операций, которые делает алгоритм для получения положительного результата (для решения проблемы).
Предположим, что массив содержит 100 несортированных элементов. Сколько сравнений потребуется, чтобы найти элемент (также принимая во внимание, что необходимый элемент может отсутствовать)? Для этого потребуется до 100 сравнений, т.к. мы должны сравнить значение каждого элемента с заданным значением. И, несмотря на то, что искомый элемент может быть первым в массиве (что приводит к единственному сравнению), мы рассмотрим только худший случай (элемент либо отсутствует, либо находится на последней позиции).
Смысл вычисления алгоритмической сложности заключается в нахождении зависимости между количеством операций и размером входных данных.
Например, массив из примера выше имел 100 элементов, и точно такое же количество операций потребовалось для нахождения нужного элемента. Если количество элементов массива увеличится до 1423, то количество операций точно так же увеличится до 1423. Таким образом, в данном примере зависимость получается линейной. Количество операций возрастает с увеличением количества элементов. Доступ к любому элементу массива занимает константное время, т.е. О(1). Это объясняется структурой массива. Переход к конкретному элементу требует только вычисления его позиции относительно первого элемента.
Ясно одно: бинарное дерево поиска хранит свои узлы в отсортированном порядке. Итак, какова будет вычислительная сложность алгоритма поиска элемента в бинарном дереве? Нужно рассчитать количество операций, необходимых для нахождения элемента (для худшего случая).
Посмотрите на иллюстрацию выше. Когда мы начинаем поиск с корня, первое сравнение может привести к трём разным результатам.
22 сравнения в худшем случае.
Вернёмся к дереву
В этой задаче мы должны принять во внимание важное требование.
Как и хэш-таблица, мы получаем доступ к каждому набору домов по цене. Все дома с одинаковой ценой сгруппированы в отдельное бинарное дерево. Это также сэкономит нам некоторое пространство, если мы храним домашние идентификаторы вместо целого объекта, определенного выше (структура AirbnbHome). Наиболее вероятным сценарием является сохранение всех объектов, заполненных объектами, в домашнем идентификаторе хеш-таблицы для домашнего полного объекта и хранении другой хэш-таблицы, которая отображает цены с идентификаторами домов.
Балансировка имеет решающее значение для BST, потому что это единственная гарантия выполнения операций с деревом за O(logN).
Проблема несбалансированного BST очевидна при вставке элементов в сортированном порядке. В конце концов, дерево становится просто связанным списком, что, очевидно, приводит к линейным операциям времени. Забудьте об этом, предположим, что все наши деревья идеально сбалансированы. Еще раз взгляните на иллюстрацию выше. Каждый элемент массива представляет собой большое дерево.
Это уже более похоже на граф. Эта иллюстрация представляет собой наиболее замаскированные структуры данных и графы, которые приводят нас к следующему разделу.
Представление графов: заключение
Плохая новость относительно представления графов заключается в том, что не существует единственно истинного представления графа. Вот почему не существует std::graph в библиотеках. У нас уже был шанс представить “специальный” граф под названием бинарное дерево поиска. Суть в том, что всякое дерево – это граф, но не каждый граф – дерево. Последняя иллюстрация показывает нам, что у нас есть много деревьев под одной абстракцией, «цены против домов“, и некоторые из вершин отличаются по своему типу, цены – это вершины графа, имеющие значение цены и относящиеся ко всему дереву id домов, которые удовлетворяют конкретной цене. Это больше похоже на гибридную структуру данных, чем на простой граф, который мы привыкли видеть в учебниках.
Это ключевой момент в представлении графов.
Не существует фиксированной структуры данных для представления графа (в отличие от BST с их узлами и левыми/правыми дочерними элементами). Вы можете представить граф наиболее удобным для вас способом (наиболее удобным для конкретной задачи), главное, чтобы вы “видели” это как граф. Под этим мы подразумеваем применение алгоритмов на графах.
Что касается N-арного дерева, это скорее будет напоминать граф.
И первое, что приходит в голову, чтобы представить узел N-арного дерева, это что-то вроде этого:
Эта структура представляет собой единственный узел дерева. Полное дерево выглядит примерно так:
Граф и дерево
Граф очень похож на n-арное дерево, только с небольшой разницей.
Это граф? Нет. Я имею в виду да, но это то же самое N-арное дерево из предыдущей иллюстрации, просто перевёрнутое. Как правило, когда вы видите дерево (даже если это яблоня, лимонное дерево или бинарное дерево поиска), вы можете быть уверены, что это граф. Итак, разрабатывая структуру для вершины графа, мы можем создать ту же структуру:
Достаточно ли этого для создания полноценного графа?
Нет. И вот почему. Посмотрите на эти два графа из предыдущих иллюстраций и найдите разницу:
Граф на рисунке слева не имеет единой точки входа (это скорее лес, чем одно дерево). Граф на рисунке справа не имеет недостижимых вершин. Звучит знакомо.
Граф является связным, если существует путь между каждой парой вершин.
Очевидно, что не существует пути между каждой парой вершин для графа “цены vs. дома” (если это не очевидно из иллюстрации, просто предположите, что цены не связаны друг с другом). Поскольку это просто пример, чтобы показать, что мы не в состоянии построить граф с одной структурой GraphNode, есть случаи, когда нам приходится иметь дело с такими несвязанными графами. Взгляните на этот класс:
Подобно тому, как N-арное дерево строится вокруг одного узла (корневого), связный граф также может быть построен вокруг «корневой» вершины. Говорят, что деревья “укоренены”, т.е. у них есть начальная точка. Связный граф может быть представлен как корневое дерево (с несколькими дополнительными свойствами), это очевидно, но имейте в виду, что фактическое представление может отличаться от алгоритма к алгоритму, от проблемы к проблеме даже для связного графа. Однако, учитывая природу графов, несвязанный граф может быть представлен следующим образом:
Для обходов графа, таких как BFS/DFS, вполне естественно использовать древовидное представление. Однако такие случаи, как поиск кратчайшего пути требуют другого представления графа. Помните граф Эйлера? Чтобы отследить “эйлерность” графа, мы должны проследить путь Эйлера внутри него. Это означает, что сначала мы должны посетить все вершины только один раз путём обхода каждого ребра, и когда проход заканчивается, а мы имеем необработанные рёбра, то граф не имеет пути Эйлера, и поэтому не является графом Эйлера.
Существует более быстрый метод проверки.
Конечно, вы можете легко усовершенствовать этот код, чтобы он удовлетворял всем вашим потребностям.
Пример Twitter: проблема доставки твитов
Вот ещё одно представления графа, называемое матрицей смежности, которое может быть полезно в ориентированных графах (вспомните пример с фолловерами Twitter).
В этом примере есть 8 вершин. Итак, всё, что нам нужно представить, это матрица |V| x |V| (|V| количество строк и |V| количество столбцов). Если есть направленное ребро от v до u, то элемент, находящийся в [v][u] равен единице. Иначе он равен нулю.
Как вы можете видеть, эта матрица слишком скудна, ее единственный плюс – это быстрый доступ к элементу. Чтобы увидеть, фолловит ли Патрик Губку Боба, мы должны просто проверить значение матрицы [Patrick] [Sponge Bob]. Чтобы получить список подписчиков Ann, мы просто обрабатываем всю колонку Ann. Матрицы смежности можно использовать для неориентированных графов, и вместо одного значения, если существует ребро из V в U, мы должны установить оба значения, равными единице, например, если adj_matrix[v][u] = 1, то и adj_matrix[u][v] должен равняться единице. Матрица смежности неориентированного графа симметрична относительно главной диагонали.
Обратите внимание, что вместо хранения единиц и нулей в матрице смежности мы можем хранить там что-то “более полезное”, например, весовые коэффициенты.
Одним из лучших примеров может быть граф с информацией о расстоянии от вершины до вершины.
На приведённом выше графе представлены расстояния между домами Патрика, Губки Боба и других (такой граф называется взвешенным). Мы ставим знаки бесконечности, если между вершинами нет прямого маршрута. Это не означает, что маршруты вообще отсутствуют, и в то же время это не означает, что маршруты обязательно должны быть.
Использование матрицы смежности для хранения графа фолловеров кажется хорошим решением, однако не стоит забывать, что в Twitter сейчас существует порядка 300 миллионов пользователей, поэтому хранить матрицу смежности для каждого из них занимает около 300 * 300 * 1 байт. То есть
82000 терабайт, что составляет
1024 * 82000 гигабайт. Bitsets? BitBoard может нам немного помочь, уменьшив требуемый размер до
10000 терабайт. Всё ещё слишком много. Очевидно, матрица смежности – плохой выбор, т.к. заставляет использовать больше места, чем необходимо. Вот почему использование списка ребер, инцидентных вершинам, может оказаться полезным. Дело в том, что матрица смежности позволяет нам хранить информацию о том, подписан человек на другого или нет, а нам нужно знать информацию только о подписчиках, что-то вроде этого:
Иллюстрация справа называется списком смежности.
Каждый список описывает множество соседних вершин в графе. Кстати, фактическая реализация графа как списка смежности, опять же, отличается. На рисунке мы выделили использование хеш-таблицы, что разумно, так как доступ к любой вершине будет O(1), а для списка соседних вершин мы не упомянули точную структуру данных, отклоняясь от связанных списков к векторам. Выбор за вами.
Дело в том, чтобы выяснить, фолловит ли Патрик Liz, мы должны получить доступ к хеш-таблице (константное время) и просмотреть все элементы в списке, сравнивающие каждый элемент с элементом “Liz” (линейное время). Линейное время не так уж и плохо, потому что нам нужно перебрать только фиксированное количество вершин, смежных с “Патриком”. Итак, нам нужно как минимум 300 миллионов записей хеш-таблиц, каждая из которых указывает на вектор. Неизвестно сколько элементов точно должен содержать вектор, т.к. отсутствует статистика. Погуглив, можно обнаружить, что среднее количество подписчиков
12 терабайт. Нельзя сказать, что этот объём идеален, но, во всяком случае, это лучше, чем 10 000 терабайт.
Честно говоря, нельзя точно сказать, что 12 терабайт является разумным числом.
Что в Twitter главное?
Я имею в виду, технически, какова его самая большая проблема? Вы не будете одиноки, если скажете, что это быстрая доставка твитов. Допустим, что Патрик написал твит о еде. Все его последователи должны получить этот твит в разумные сроки. Сколько времени это займёт? Мы можем предполагать что угодно и использовать любые абстракции, которые мы хотим, но мы заинтересованы в реальных системах, так что давайте копать. Вот что обычно происходит, когда кто-то постит твит:
Опять же, мы не знаем о том, сколько времени требуется для доставки одного твита, чтобы он дошёл до всех фолловеров, но по общедоступной статистике мы можем увидеть, что ежедневно постится около 500 миллионов твитов.
Таким образом, процесс, изображённый выше, происходит 500 миллионов раз каждый день.
Нельзя найти какую-либо информацию по скорости передачи твитов. Можно предположить, что это время занимает около пяти секунд. Но обратите внимание на “тяжёлые случаи”: знаменитости с более, чем миллионом фолловеров. Они могут писать о своем замечательном завтраке в домике на пляже, но Twitter будет стараться изо всех сил, чтобы доставить этот супер-полезный контент миллионам фолловеров.
Предыдущий граф (с хэш-таблицей и кучей списков) позволяет нам эффективно находить всех пользователей, которых фолловит конкретный пользователь. Но это не позволяет нам эффективно найти всех пользователей, которые фолловят одного конкретного пользователя, в этом случае мы должны сканировать все ключи хеш-таблицы. Поэтому мы должны построить еще один граф, который является симметрично противоположным тому, который мы построили для подписок. Этот граф снова будет состоять из хэш-таблицы, содержащей все 300 миллионов вершин, каждая из которых указывает на список смежных вершин (структура остаётся той же), но на этот раз список смежных вершин будет представлять фолловеров (подписчиков).
Таким образом, основываясь на этой иллюстрации, когда Liz постит новый твит, Губка Боб и Ann должны заметить этот твит в своей ленте через какое-то время. Общий метод для достижения этой цели – сохранение отдельных структур для ленты каждого пользователя. В случае 300+ миллионов пользователей Twitter, мы могли бы предположить, что есть по крайней мере 300+ миллионов лент (для каждого пользователя). В принципе, всякий раз, когда пользователь постит твит, мы должны получить список подписчиков пользователя и обновить ленту каждого из них. Лента может быть представлена в качестве связного списка или АВЛ-дерева.
Это всего лишь основная идея, которую мы абстрагировали от фактического представления ленты, и, конечно, мы можем сделать доставку быстрее, если мы используем многопоточность.
Это имеет решающее значение для «тяжелых случаев», потому что среди миллионов последователей те, которые находятся ближе к концу, обрабатываются позже, чем те, которые находятся ближе к началу списка.
Поэтому, когда пользователи обновляют свою ленту, они получают новый твит.
Справедливости ради следует сказать, что мы просто коснулись верхушки айсберга реальных проблем в Airbnb или Twitter. Это занимает действительно много времени у талантливых инженеров, чтобы достичь таких больших результатов в сложных системах, таких как Twitter, Google, Facebook, Amazon, Airbnb и других. Просто имейте это в виду, читая эту статью.
Смысл демонстрации проблем доставки твитов заключается в том, чтобы показать реальное применение графов, но пока без использования алгоритмов.
Мы обсуждали дома Airbnb и эффективную фильтрацию, прежде чем заканчивать графические представления, и главной очевидной вещью была неспособность эффективно фильтровать дома с несколькими ключами фильтра. Есть ли что-нибудь, что можно было бы сделать с помощью алгоритмов на графах? Мы не можем точно сказать, но, по крайней мере, мы можем попробовать. Что, если мы представим каждый фильтр как отдельную вершину?
Мы даже можем немного усовершенствовать этот набор, сгруппировав удобства по определённым типам.
Теперь, что если мы представляем Airbnb дома как вершины, а затем соединим каждый дом с фильтрами, которые ему соответствуют?
Изменение этой иллюстрации делает её более похожей на специальный тип графа, называемый двудольным графом.
Алгоритмы на графах: введение
Двудольный граф или биграф — это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. — Википедия.
Задача
Любая обработка графа может быть классифицирована как алгоритм графа. Вы в буквальном смысле можете реализовать функцию, выводящую все вершины графа. Большинство из нас боится алгоритмов, о которых идёт речь в учебниках. Давайте попробуем применить алгоритм Хопкрофта-Карпа для сопоставления двудольных графов к нашей задаче фильтрации домов Airbnb:
Дан двудольный граф домов Airbnb (H) и фильтров (F), где каждый элемент (вершина) H может иметь более одного соседними элементами (вершины) F (с общим ребром). Найти подмножество H, состоящее из вершин, смежных с вершинами в подмножестве F.
Алгоритм Хопкрофта — Карпа — алгоритм, принимающий на вход двудольный граф и возвращающий максимальное по мощности паросочетание, то есть наибольшее множество рёбер, таких что никакие два не имеют общую вершину. — Википедия.
Читатели, знакомые с этим алгоритмом, уже знают, что это не решает нашу проблему, потому что определение требует, чтобы никакие два ребра не имели общей вершины.
Рассмотрим пример иллюстрации, где есть всего 4 фильтра и 8 домов (ради простоты).
Решение нашей задачи требует наличия рёбер с общими вершинами, ведущих к различным вершинам домов, которые попадают в одно и то же подмножество фильтров, тогда как алгоритм Хопкрофта-Карпа устраняет такие рёбра с общими конечными точками и создает рёбра, инцидентные вершинам обоих подмножеств.
Взгляните на иллюстрацию выше: всё, что нам нужно, это дома D и G, которые удовлетворяют всем четырем значениям фильтров.
Нам нужно получить все совпадающие ребра, которые имеют общую конечную точку.
Мы могли бы разработать алгоритм для этого подхода, но его время обработки, возможно, не имеет отношения к потребностям пользователей (пользователям необходим мгновенный результат). Вероятно, было бы быстрее создать сбалансированное бинарное дерево поиска с несколькими ключами сортировки, почти как файл индекса базы данных, который отображает первичные / внешние ключи с набором удовлетворяющих записей.
Алгоритм Хопкрофта-Карпа (и многие другие) основан на алгоритмах обхода графов DFS (Depth First Search – обход в глубину) и BFS (Breadth First Search – обход в ширину).
Если честно, фактическая причина использования в этом примере алгоритма Хопкрофта-Карпа заключается в скрытом переключении на обходы графов, бинарных деревьев.
Почти то же самое происходит с бинарными деревьями: вы выводите значения узла, затем переходите к двум следующим узлам. Здесь возникает три разных варианта:
Насчёт рекурсии
Очевидно, что рекурсивные функции выглядят очень элегантно. Однако каждый раз, когда мы вызываем функцию рекурсивно, это означает, что мы выделяем под неё дополнительную память. Вот почему рекурсивные вызовы являются нерациональными (дополнительное пространство под стек и многочисленные вызовы функций) и даже опасными (переполнение стека). В критически важных системах программирования (самолеты, NASA и т.д.) рекурсия полностью запрещена.
Обход графа: DFS и BFS
Самые распространённые алгоритмы для графов
Если вы не знакомы с этой проблемой, подумайте о некоторой структуре данных, которую вы могли бы использовать для хранения узлов при обходе дерева. Мы разработаем два основных алгоритма обхода графа, то есть поиск в глубину (DFS) и поиск в ширину (BFS).
Поиск в глубину исследует самые дальние вершины, поиск в ширину исследует ближайшие.
BFS – это то, что нам нужно, если мы хотим выводить вершины графов поэтапно. Для этого нам понадобится очередь (структура данных) для хранения «уровня» графа при выведении (или посещении) его “родительского уровня”. На предыдущей иллюстрации вершины, помещённые в очередь, имеют голубой цвет.
На каждом уровне вершины извлекаются из очереди, и, посещая каждую выбранную вершину, мы должны вставить её дочерние элементы в очередь (для следующего уровня). Следующий код достаточно прост, чтобы уловить основную идею BFS. Предполагается, что граф связан.
Имейте в виду, что реализация обхода изменяется в зависимости от того, как вы представляете граф.
DFS и BFS являются важными инструментами для решения проблем, касаемых графов. В то время как DFS имеет элегантную рекурсивную реализацию, имеет смысл избавить этот алгоритм от рекурсии. Для реализации BFS без рекурсии мы использовали очередь, для DFS вам понадобится стек. Однако неосвещённой остаётся ещё одна проблема: нахождение кратчайшего пути между вершинами графа. Поэтому, мы переходим к заключительному разделу статьи.
Uber и задача кратчайшего пути (алгоритм Дейкстры)
Серверная часть должна обрабатывать миллионы пользовательских запросов, отправляя каждый из запросов одному или нескольким водителям поблизости. Хоть проще и иногда даже рациональнее отправлять запрос пользователя всем водителями, находящимся поблизости, всё же потребуется предварительная обработка.
Кроме обработки входящих запросов и нахождения области местоположения на основе координат пользователя, а затем нахождения водителей с ближайшими координатами, нам также нужно найти правильного водителя для поездки. Чтобы избежать обработки геопространственных запросов (получение близлежащих автомобилей путем сравнения их текущих координат с координатами пользователя), предположим, у нас уже есть сегмент карты с пользователем и несколькими автомобилями поблизости.
Возможные пути от автомобиля к пользователю обозначены желтым. Задача заключается в том, чтобы рассчитать минимальное расстояние между автомобилем и пользователем, другими словами, найти кратчайший путь между ними.
Представим этот сегмент в виде графа:
Это неориентированный взвешенный граф. Чтобы найти кратчайший маршрут между вершинами B (автомобиль) и А (пользователь), мы должны найти маршрут между ними, состоящий из ребер с возможно минимальными значениями.
Алгоритм действий
Применяя это к нашему примеру, мы начнем с вершины B (автомобиль) в качестве начального узла. Для первых двух шагов:
В нашей структуре непосещённых вершин находятся все вершины. Также обратите внимание на таблицу, в правой части иллюстрации. Для всех вершин там будут все самые короткие расстояния от B и предыдущей (отмеченной “Prev”) вершины, которые ведут к вершине. Например, от B до F расстояние = 20, за предыдущую вершину мы считаем B.
Мы помечаем B как посещённую вершину и переходим к соседней – F.
Теперь мы помечаем F как посещённую и выбираем следующую вершину, до которой расстояние минимально. Это вершина G.
Как указано в алгоритме, если вершина назначения отмечена посещенной (при планировании маршрута между двумя определенными узлами, как в нашем случае), то мы можем остановиться. Таким образом, наш следующий шаг останавливает алгоритм со следующими значениями.
Таким образом, у нас есть как кратчайшее расстояние от B до A, так и маршрут через вершины F и G.
Заключение
В этой статье мы подробно рассмотрели основы теории графов. Как вы могли заметить, графы являются неотъемлемой частью программной инженерии, и, если вы претендуете на хорошую должность, вы обязаны разбираться во всём этом. Надеемся, что эта статья стала для вас хорошим фундаментом для дальнейшего изучения алгоритмов.