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

    Топологическая сортировка (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 поменялись местами

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