Пользователь
0,0
рейтинг
4 августа 2010 в 16:40

Разработка → Топологическая сортировка

Топологическая сортировка (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 строчки кода, реализующих данный алгоритм (все тщательно закомментировано)
Александр @Kuper
карма
37,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (26)

  • +5
    Даешь неделю сортировок на хабре!
    • +35
      Да уж лучше сортировки, чем по неделям мусолить антены у айфонов.
    • –9
      А потом неделю hello world'ов?
      • 0
        Ну ладно, не буду мешать просвящаться…
        /me в свое время штудировал algolist.manual.ru
      • 0
        • 0
          Ага, прям генератор трендов, созданных и описанных еще до моего рождения :D
  • +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 поменялись местами

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