На протяжении всей этой серии статей я довольно много писал о том, чтобы заново открыть для себя те вещи в информатике, о которых я слышал или читал раньше, но на самом деле не имел достаточного контекста для понимания.
Сначала я подумал, что этот странный циклический процесс снова и снова наталкиваться на одни и те же концепции был уникальным для компьютерных наук. Но в наши дни я придерживаюсь другого мнения: процесс изучения и повторного изучения идеи имеет фундаментальное значение для ее понимания на более глубоком уровне. У этой идеи есть название: герменевтический круг. По своей сути, герменевтический круг основан на идее, что мы должны возвращаться к идеям снова и снова и понимать их части одновременно, чтобы полностью постичь целое (и наоборот).
Это циклический процесс - именно то, что я испытал, когда изучал различные типы графов, включая ориентированные графы, циклические графы и все, что между ними. Я слышал об этих типах графиков раньше и был немного знаком со всеми из них, но принципиально не понимал, когда они будут использоваться или почему они появляются снова и снова во всем, что я читал.
Как оказалось, учиться сложно! И это требует времени, а также большого количества повторений. Итак, давайте вернемся к графикам и узнаем об их определенном подмножестве, которое имеет фундаментальное значение для многих решений в области компьютерных наук.
Края, края, везде
Изучая графики, мы в основном фокусировались на представлении графиков и способах поиска по ним. На прошлой неделе мы рассмотрели поиск в глубину (DFS), алгоритм обхода графа, который рекурсивно определяет, существует ли путь между двумя заданными узлами. Однако стоит снова вернуться к поиску в глубину по нескольким причинам.
Поиск в глубину полезен, чтобы помочь нам узнать больше о данном графе, и может быть особенно полезен при упорядочивании и сортировке узлов в графе. Мы можем использовать алгоритм DFS, чтобы идентифицировать циклы внутри графа, определять, какие ребра имеет граф, и упорядочивать вершины внутри линейным образом.
Сегодня мы рассмотрим каждый из этих трех приемов и посмотрим, как использование поиска в глубину может помочь нам лучше понять, с каким графом мы имеем дело в процессе поиска по в нем. !
В начале этой серии мы узнали о ребрах, элементах, которые соединяют узлы в графе. Мы также узнали, что ребра могут быть направленными с потоком от одного узла к другому или неориентированными с двунаправленным потоком между обеими вершинами. Но, придерживаясь темы этого сообщения, давайте вернемся к тому, что, как мы думаем, мы уже знаем.
Если мы вернемся к ребрам, мы увидим, что в контексте графа ребра могут быть не просто «направленными» или «неориентированными». Два направленных ребра могут сильно отличаться друг от друга, в зависимости от того, где в графе они встречаются! Давайте посмотрим на некоторые другие способы классификации ребер в графе.
В структуре данных графа есть две основные категории ребер: ребро дерева и ребро, не являющееся деревом. Напомним, что как в алгоритме BFS, так и в алгоритме DFS родительские указатели, которые ведут обратно к начальному узлу, можно переставить, чтобы сформировать дерево.
Любое ребро, которое является частью пути, взятого в алгоритме обхода графа, известно как ребро дерева, поскольку оно позволяет нам каждый раз посещать новую вершину. когда мы проходим через граф, и могут быть реструктурированы, чтобы сформировать «дерево».
Итак, что насчет ребер, не являющихся деревьями? Что ж, существует три различных их варианта, и мы на самом деле уже сталкивались со всеми из них, даже если мы не обязательно знали, как они назывались в то время.
Первый из трех называется передним ребром, поскольку он позволяет нам двигаться «вперед» по графу и потенциально может быть частью другого пути вниз по дереву. Напротив, существует также обратная грань, которая соединяет узел в графе «резервным копированием» с одним из его предков (например, с его родительским или прародительским узлом, или даже обратно к себе!). Наконец, есть поперечное ребро, которое «пересекает» и соединяет одно поддерево в графе с другим. Другими словами, перекрестное ребро соединяется с одноуровневыми узлами, которые не обязательно имеют общего предка в пути дерева, но все равно соединяют их.
Эти определения приобретают гораздо больший смысл, когда мы можем увидеть, как они применяются к фактическим узлам на графике, поэтому давайте рассмотрим пример.
На показанной здесь иллюстрации мы видим, что ребра дерева, выделенные синим цветом, - это те ребра, которые мы проходим как часть нашего обхода по нашему пути в графе; в данном случае наша прогулка u-v-y-x. Ребра, соединяющие эти вершины на нашем пути, являются нашими ребрами дерева. Однако мы могли бы также пойти «вперед» другим путем и пройти от u к x; таким образом, край (u, x) является передним краем.
Мы заметим, что когда мы дойдем до узла x, единственной вершиной, к которой нужно перейти, будет v. Ребро, соединяющее эти два узла в дереве, (x, v), является обратным ребром, поскольку оно соединяет узел x обратно с одним из его предков на пути: узлом v. Мы также заметим, что в другой части графика - точнее, в другом поддереве - узел z имеет обратную кромку, которая фактически соединяется с самим собой. Это также известно как петля, или обратное ребро, которое соединяет узел обратно с самим собой, или ребро, которое «ссылается» на узел, из которого он произошел: (z, z). (Мы вернемся к петлям позже, но это наш первый их вкус!)
Ребро, соединяющее узел w и y, которое мы также можем назвать (w, y), является перекрестным ребром, поскольку оно соединяет поддерево. Перекрестные ребра немного легче увидеть, когда мы переставляем ребра нашего дерева, чтобы на самом деле сформировать дерево, поэтому давайте перерисуем тот же самый граф, чтобы сделать перекрестное ребро более очевидным. На изображении ниже мы увидим два потенциальных «дерева», которые можно сформировать, начав с двух разных узлов графа: узла u или узла w соответственно.
Ребро (w, y) соединяет два поддерева всего графа вместе, даже несмотря на то, что нет единого корневого узла или предка, который фактически разделяет поддеревья. Помните, что граф - это очень свободная версия дерева и не подчиняется тем же правилам, что и дерево.
Поскольку у графа нет единственного корневого узла, он не образует единого дерева. Скорее, граф может содержать в себе множество небольших поддеревьев, каждое из которых станет очевидным, когда мы пройдемся по путям графа. Граф - это не столько отдельная древовидная структура данных, сколько взаимосвязанный лес с небольшими поддеревьями внутри него.
Следует отметить одну важную вещь обо всех этих различных типах кромок: они не всегда существуют! Все зависит от того, с каким типом графа мы имеем дело. В ориентированном графе возможны все ребра дерева, перекрестные, обратные и передние ребра. Однако для неориентированного графика это совсем другая история.
В неориентированном графе нет прямых или поперечных ребер. Каждое ребро должно быть либо краем дерева, либо задним краем.
Простой способ запомнить правила классификации ребер заключается в следующем: неориентированный граф может иметь только ребра дерева и задние ребра, но ориентированный граф может содержать все четыре типа ребер.
Хорошо, но какова история этого правила? Что ж, гораздо легче увидеть, действительно ли мы попробуем это на примере, поэтому мы и сделаем именно это.
В представленном здесь графе четыре вершины и четыре ребра. Скажем, кромка (a, d) - это «передняя» кромка; другими словами, это ребро, которое позволяет нам переходить от узла a к узлу d.
Представьте, что мы проходим по этому графику от узла a к b, а затем от b к c. Когда мы добираемся до узла c, нам больше некуда идти, поэтому мы должны вернуться к узлу b.
Теперь, чтобы мы могли правильно запустить алгоритм поиска в глубину, нам нужно проверить, есть ли другие вершины, которые мы можем «посетить» из узла b. Оказывается, он есть! Мы посетим узел d. Мы снова в похожей ситуации, и нам нужно проверить, есть ли еще один узел, который мы можем посетить с d. Как оказалось, поскольку это неориентированный граф, мы можем посетить одно место: узел a. В этот момент становится невозможным, чтобы край (a, d) был «передним» краем. Поскольку правила DFS диктуют, что мы должны посетить узел a из d, поскольку мы должны исследовать граф на самом глубоком уровне, мы должны посетить его; мы не можем вернуться вверх к узлу a, а затем перейти на d оттуда!
Ненаправленный граф никогда не может допускать наличия переднего ребра, такого как (a, d), поскольку для существования переднего ребра нам необходимо полностью завершить посещение всех узлов, доступных из нашего начального узла a, прежде чем проходить через край. В неориентированном графе это сделать буквально невозможно! Итак, ребро между этими двумя узлами действительно должно быть записано так: {a, d}, поскольку мы можем перемещаться по этому ребру в любом направлении, в зависимости от того, с какого узла мы начинаем.
Несмотря на то, что мы не будем рассматривать здесь пример, мы могли бы опровергнуть перекрестные ребра, подобные прямым ребрам, поскольку они также не могут существовать в неориентированном графе.
Снова и снова
Еще одна сильная сторона алгоритма поиска в глубину - это его способность идентифицировать циклы на графе. Прежде чем мы углубимся в то, как это сделать, давайте познакомимся с некоторыми важными терминами, которые мы будем использовать по ходу дела.
Цикл в контексте графа возникает, когда некоторое количество вершин соединяются друг с другом в замкнутую цепочку ребер. Граф, содержащий хотя бы один цикл, известен как циклический граф. И наоборот, граф, содержащий нулевые циклы, известен как ациклический граф.
В предыдущем разделе мы видели наш первый экземпляр петли, типа обратной кромки. Самостоятельные петли могут возникать только в ориентированном графе, поскольку петля - это тип направленного ребра.
И в ориентированном, и в неориентированном графах могут быть циклы, но стоит отметить, что петля может возникать только в ориентированном циклическом графе, который является ориентированным графом, который содержит хотя бы один цикл.
Как выясняется, причина того, что алгоритм поиска в глубину особенно хорош при обнаружении циклов, заключается в том, что он эффективен при обнаружении обратных краев.
По определению, любой граф с обратным ребром будет содержать цикл. На приведенном ниже графике мы видим, что узел e соединяется обратно с предком на пути, узлом a. Поскольку в этом ориентированном графе существует обратное ребро, мы знаем, что этот граф также содержит цикл - это ориентированный циклический граф.
Хорошо, но как DFS на самом деле определяет циклы? И почему этот алгоритм особенно эффективен при определении того, существует ли цикл внутри графа? Что ж, все это восходит к рекурсивной природе алгоритма поиска в глубину. Напомним, что DFS использует структуру данных стека под капотом. Это немного упрощает определение наличия обратного ребра на пути при прохождении по графу.
Например, в приведенном ранее примере графа, когда мы перемещаемся от u к v, от y к x, мы добавляем каждый из этих элементов в стек узлов, которые мы посетили. Мы можем сделать еще один шаг, чтобы упростить классификацию ребер: мы можем пометить узел u как текущий beingProcessed с помощью простого логического флага, когда мы начнем поиск по его «самому глубокому» пути. Как только мы помечаем узел u как узел, который мы ищем, если какой-либо узел, который мы добавляем в стек, ссылается на резервное копирование на u, мы знаем, что нашли цикл. Действительно, та же самая логика применима к другим внутренним циклам в графе, а не только к циклам, подключающимся к начальному узлу.
Если какой-либо узел, добавленный в стек, имеет ссылку на узел, который уже внутри стека, мы можем быть уверены, что у нас есть цикл в этом графе.
Но подождите - это еще не все! Ладно, осталось всего еще на один. Последний тип графа, который нам нужно определить, - это ориентированный граф без циклов.
Большинство реализаций поиска в глубину проверяют, существуют ли какие-либо циклы, и большая часть этого основана на алгоритме DFS, проверяющем, является ли граф направленным ациклическим графом , также известный как DAG. Направленный ациклический граф, как следует из названия, является направленным, но без каких-либо циклов. Золотое правило групп DAG состоит в том, что если мы начнем с любого узла графа, никакая последовательность ребер не позволит нам вернуться к начальному узлу. Таким образом, по определению ориентированный ациклический граф никогда не может содержать петлю.
Группы DAG довольно печально известны в информатике, потому что они почти повсюду в программном обеспечении. Например, направленный ациклический граф является основой приложений, которые обрабатывают планирование для систем задач или обрабатывают задания, особенно те, которые необходимо обрабатывать в определенном порядке. На более высоком уровне группы DAG используются для представления конечных автоматов, которые часто используются для отслеживания объектов с изменяемым состоянием в веб-приложениях и мобильных приложениях.
Однако мой личный любимый пример - использование групп DAG для представления графов зависимостей. Если вам когда-либо приходилось устранять зависимости в Gemfile, или обрабатывать обновления пакетов, или решать проблемы с зависимостями с помощью менеджеров пакетов, таких как npm или yarn, то вы взаимодействовали с DAG на очень абстрактном уровне! Граф зависимостей также является отличным примером того, как группы DAG могут быть сложными, массивными и крупными, и почему может быть полезно отсортировать и упорядочить узлы в таком графе.
Итак, давайте узнаем, как это сделать!
Топологическая сортировка
Поскольку теперь мы знаем, насколько обширным и сложным может быть направленный ациклический граф, возможность сортировать и упорядочивать вершины и разбираться в данных внутри группы DAG может быть очень полезной. К счастью, есть алгоритм, который делает именно это!
Алгоритм топологической сортировки позволяет нам сортировать вершины графа в определенном порядке, основанном на взаимосвязанности ребер, соединяющих вершины. Если в графе существуют две вершины, x и y, и между ними существует ориентированное ребро (x, y), то топологическая сортировка упорядочит вершины так, как мы могли бы встретить их на пути: x, за которым следует y.
Если мы рассмотрим порядок топологической сортировки, мы заметим, что сама сортировка нечисловая. Другими словами, порядок вершин основан на соединяющих их ребрах, а не на числовом значении.
Когда дело доходит до топологической сортировки, наиболее важно помнить о том, что мы можем посетить вершину только после того, как все вершины, ведущие к ней, были уже посещены.
Например, на показанном здесь графике у нас есть пять узлов: v, w, x, y и z. Чтобы запустить топологическую сортировку на этом ориентированном графе, мы должны быть уверены, что, когда мы упорядочиваем и посещаем наши вершины, узел y не может быть посещен до тех пор, пока не будут посещены и x, и w.
Просто взглянув на этот график, мы можем увидеть, что есть два возможных маршрута, которые мы могли бы выбрать: v-w-x-y-z или v-x-w-y-z. В обоих этих двух путях мы все равно будем посещать узел y после x и w. Таким образом, оба они действительны, и каждый из них возвращает допустимые топологические порядки, который представляет собой упорядоченный набор вершин, который является возвращенным результатом выполнения топологической сортировки.
На этом графике цикла нет. Но что, если бы мы это сделали? Самый простой вариант такого графа будет иметь два узла, каждый из которых ссылается друг на друга, образуя цикл. Вот пример того, как может выглядеть этот график:
В этом примере вершина a зависит от b, который, в свою очередь, зависит от a. Проблема здесь в том, что мы не можем применить правило посещения вершин, которые «ведут» к той, с которой мы начинаем, потому что обе они ведут друг к другу.
Топологическая сортировка может применяться только к ориентированным ациклическим графам или группам DAG. Выполнить топологическую сортировку на ориентированном графе с циклом невозможно, так как неясно, с чего должна начинаться сама сортировка.
Есть несколько разных способов реализовать топологическую сортировку. Однако на сегодняшний день нам даже не нужно изучать какие-либо новые, потому что мы уже знаем одну интуитивно! Я, конечно же, говорю о поиске в глубину.
Итак, давайте посмотрим на топологическую сортировку в действии - в этом нам поможет DFS!
Будем работать с тем же графиком, что и раньше; при запуске DFS для определения топологического порядка важно использовать обратный порядок завершения DFS для сборки наших вершин.
Мы начнем с запуска DFS на нашем начальном «родительском» узле, который должен быть v, так как это единственный узел без ведущего к нему ребра. Мы можем выбрать w или x для перемещения вниз - неважно, какой именно. В этом примере мы выберем w и продолжим до y, затем до z.
Когда мы достигаем z, мы заходим в тупик! Итак, нам нужно вернуться к y. Но, прежде чем мы вернемся назад, мы присвоим номер (который мы будем использовать, чтобы упорядочить наши вершины через мгновение) узлу z. В этом случае мы присвоим ему значение 4, поскольку он будет заказываться последним - помните, нам нужен обратный порядок обработки DFS.
Затем мы вернемся к y; поскольку идти дальше некуда, мы повторим тот же шаг с присвоением номера 3, а затем снова вернемся к w. Мы будем продолжать это делать, пока не дойдем до узла с непосещенным ребром. Каждый раз, когда мы это делаем, мы будем упорядочивать вершины по мере необходимости.
Наконец, мы вернулись к нашему начальному узлу v. Когда мы вернемся к «родительскому» узлу, мы увидим, что есть одно ребро, которое мы не посетили: осталось только x. Итак, мы посетим его, присвоим ему номер (в данном случае 1) и завершим наш поиск через узел v. Наконец, если мы последуем за номером 0-1-2-3-4, мы получим заказ v-x-w-y-z.
И вот оно! Все наши вершины отсортированы так, что любой узел, зависящий от узла, который предшествует, будет посещен только в том случае, если его родительский (-ые) на пути (его зависимости) будут посещены в первую очередь. Теперь наш примерный график был довольно маленьким, но мы можем представить, как npm или yarn могут сделать это для гораздо большего графа зависимостей.
Итак, в следующий раз, когда вы почувствуете страх, обновляя свои зависимости, просто помните: это всего лишь ориентированный ациклический граф! Ты получил это.
Ресурсы
Существует несколько различных подходов к топологической сортировке, но я считаю, что понимание ее из контекста поиска в глубину и циклов в графе является самым простым. К счастью, есть несколько хороших ресурсов, раскрывающих принцип работы топологической сортировки в других контекстах, не говоря уже обо всех обширных ресурсах по направленным ациклическим графам! Вот некоторые из моих любимых, если вы хотите продолжать учиться.
- Топологическая сортировка графов с использованием поиска в глубину, Сеш Венугопал
- Поиск в глубину (DFS), топологическая сортировка, MIT OpenCourseWare
- Топологическая сортировка - теория графов, NerdFirstTV
- Обходы графа, Эндрю Майерс, факультет компьютерных наук Корнельского университета
- Поиск в глубину, профессор Стивен Скиена
- Топологическая сортировка, профессор Тревор Браун
