Топологическая сортировка

    Топологическая сортировка (Topological sort) — один из основных алгоритмов на графах, который применяется для решения множества более сложных задач.
    Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует.
    Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф. В задачах подобного плана рассматриваются только конечные сети.
    image
    ↑ Пример ориентированного неотсортированного графа, к которому применима топологическая сортировка

    Из рисунка видно, что граф не отсортирован, так как ребро из вершины с номером 4 ведет в вершину с меньшим номером (2).
    Существует несколько способов топологической сортировки — из наиболее известных:
    Я остановлюсь на рассмотрении последнего, поскольку он наиболее популярен, нагляден и прост в реализации.

    Суть алгоритма


    Поиск в глубину или обход в глубину (англ. Depth-first search, сокращенно DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.
    Подробнее о поиске в глубину можно почитать в статье на Хабре.
    Запускаем обход в глубину, и когда вершина обработана, заносим ее в стек. По окончании обхода в глубину вершины достаются из стека. Новые номера присваиваются в порядке вытаскивания из стека.
    Цвет: во время обхода в глубину используется 3 цвета. Изначально все вершины белые. Когда вершина обнаружена, красим ее в серый цвет. Когда просмотрен список всех смежных с ней вершин, красим ее в черный цвет.
    Думаю будет проще рассмотреть данный алгоритм на примере:

    image
    ↑ Имеем бесконтурный ориентированный граф. Изначально все вершины белые, а стек пуст. Начнем обход в глубину с вершины номер 1.
    image
    ↑ Переходим к вершине номер 1. Красим ее в серый цвет.
    image
    ↑ Существует ребро из вершины номер 1 в вершину номер 4. Переходим к вершине номер 4 и красим ее в серый цвет.
    image
    ↑ Существует ребро из вершины номер 4 в вершину номер 2. Переходим к вершине номер 2 и красим ее в серый цвет.
    image
    ↑ Из вершины номер 2 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 2 в черный цвет и кладем ее в стек.
    image
    ↑ Существует ребро из вершины номер 4 в вершину номер 3. Переходим к вершине номер 3 и красим ее в серый цвет.
    image
    ↑ Из вершины номер 3 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 3 в черный цвет и кладем ее в стек.
    image
    ↑ Из вершины номер 4 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 1. Красим вершину номер 4 в черный цвет и кладем ее в стек.
    image
    ↑ Из вершины номер 1 нет рёбер, идущих не в черные вершины. Красим её в черный цвет и кладем в стек. Обход точек закончен.
    image
    ↑ По очереди достаем все вершины из стека и присваиваем им номера 1, 2, 3, 4 соответсвенно. Алгоритм топологической сортировки завершен. Граф отсортирован.

    Применение


    Топологическая сортировка применяется в самых разных ситуациях, например при распараллеливании алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно). Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов. (если интересно — to google)

    Что касается реализации — здесь Вы можете найти 22 строчки кода, реализующих данный алгоритм (все тщательно закомментировано)
    Поделиться публикацией
    Похожие публикации
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 26
    • +5
      Даешь неделю сортировок на хабре!
      • +35
        Да уж лучше сортировки, чем по неделям мусолить антены у айфонов.
        • –9
          А потом неделю hello world'ов?
      • +1
        А мне понравилось, хоть я и гуманитарий.
        Даешь еще!
        • 0
          Сразу задачка на этот алгоритм: acm.timus.ru/problem.aspx?space=1&num=1022
          На первом курсе написал такой страшный велосипед, чтобы её решить, что даже потом, решая уже топологической сортировкой, не смог его повторить.
          • НЛО прилетело и опубликовало эту надпись здесь
            • +1
              Как пример — зависимости в linux :)
              • 0
                и еще глядя на этот алгоритм можно понять в какой ситуации зависимости не устраняются=)
                • 0
                  Да и так, по-моему, понятно: зависимости не устраняются если в графе присутствуют циклы.
              • 0
                это сортировка понравилась мне в свое время тем, что я понял по какой схеме работают некоторые пакетные менеджеры и компиляторы.
                ну и на олимпиадах была куча элегантных решений связанных с этим алгоритмом.
                спасибо. интересно. познавательно. полезно.
                • 0
                  Хорошо дать мозгам покушать алгоритмы. Я считаю это не напрягом, а наоборот облегчением. Так как не зная алгоритма тратится много времени на придумывание колес, велосипедов, мопедов и прочей техники.
                  • 0
                    ↑ Из вершины номер 3 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 3 в черный цвет и кладем ее в стек.

                    Опечатка: красим вершину номер 4 в чёрный цвет.
                    • +1
                      Перепроверил — все правильно вроде…
                      • +1
                        А, да. Прошу прощения.
                    • +2
                      При описании алгоритмов было бы хорошо писать их асимптотическую сложность
                      ИМХО, самый простой для написания метод топологической сортировки — поддерживаем для каждой вершины число входящих ребер (deg). На каждом шаге берем ту вершину, у которой число входящих ребер равно 0 (любую из них), присваиваем ей следующий незанятый номер и вычитаем 1 их всех элементов массива deg, куда входит ребро из данной вершины. Наивная имплементация дает O(v^2), если вершины хранить в хипе, отсортированные по deg — O(e)
                      • +2
                        Никак понять не могу, почему если в стеке они лежат как 2,3,4,1, то достаем мы их и называем как 1,2,3,4?
                        И почему из вершины номер 4 мы пошли именно в номер 2?
                        • –1
                          • 0
                            Другой подход к решению схожей задачи — тут.
                            • +1
                              получается что по ссылке в результате мы получаем граф «расплостанный» по уровням, а в реализации через dfs только список вершин(по которому определить что две вершины находятся на одном уровне и их порядок не важен — невозможно).

                              я прав?

                              если да то стоит заметить что эти варианты различны по памяти — для варианта dfs нужен список смежности а для того что по ссылке матрица смежности (она больше).
                              • 0
                                Да, Вы правы. И что касается результата, и что касается памяти.
                            • 0
                              Красотишша! А слегка расширив алгоритм до сложности O(v*deg(v)), можно определить, будет ли наш граф циклическим.
                              • 0
                                Для закрепления такого рода статей, хорошо практически реализовывать алгоритм, скажем, на Тимусе или других сайтах.
                                • 0
                                  Не знаю как не заметили но на последней картинке цифры 2 и 4 поменялись местами

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