Раздел «Алгоритмы».TopologicalSort:

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

Формулировка задачи

У рассеяного профессора есть несколько элементов одежды. Для каждого из них есть список элементов одежды, которые должны быть надеты до него. Задача — выстроить елементы одежды в том порядке, в котором их можно надеть.

Другая итерпретация задачи — задания, зависящия друг от друга. Для каждого задания A дан список заданий, которые должны быть выполнены перед тем, как можно будет приступить к выполнению задания A. Необходимо упорядочить задания в том порядке, в котором они могут быть выполнены.

Множество зависимых заданий естественно представлять как ориентированный граф, в котором вершины — задания, а ребро из A в B означает, что задание B должно идти раньше A.

Заметим, что нужного порядка может не быть (ориентированный граф с циклами) или может существовать несколько подходящийх порядков.

Алгоритм

Алгоритм представляет собой простейшую модификацию алгоритма обхода графа в глубину (DFS = Depth First Search): при 'выходе' из вершины выводим соответвующий элемент одежды (кладём его в конец создаваемого массива).

function  DFS(v):
    v.color = GREY;
    foreach w in ADJ(v):
        next if w.color == BLACK
        if(w.color == GRAY):
            exit ( "Graph contains cycles. Topological sort inaplicable.");
        DFS(w)
    v.color = BLACK
    print v 

По сути в код DFS были добавлены две строчки

1) Вывод вершины

    print v 

2) Когда в графе есть циклы и топологическая сортировка не возможна. В серый цвет у нас покрашены вершины в которые мы нвошли, но еще не вышли. Циклы в графе есть тогда и только тогда, когда при обходе в глубину мы 'уткнемся' в свой 'серый хвост':

        if(w.color == GRAY):
            exit ( "Graph contains cycles. Topological sort inaplicable.");

Примеры реализации

AlgorithmClasifyForm
Type: Теория
Scope: Графы
Strategy:  
Complexity: Medium