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

Перевод статьи подготовлен в преддверии старта курса «Алгоритмы для разработчиков».

Топологическая сортировка для ориентированного ациклического графа (Directed Acyclic Graphs, далее DAG) — это линейное упорядочение вершин, для которого выполняется следующее условие — для каждого направленного ребра uv вершина u предшествует вершине v в упорядочении. Если граф не является DAG, то топологическая сортировка для него невозможна.

Например, топологическая сортировка приведенного ниже графа — «5 4 2 3 1 0». Для графа может существовать несколько топологических сортировок. Например, другая топологическая сортировка для этого же графа — «4 5 2 3 1 0». Первая вершина в топологической сортировке — это всегда вершина без входящих ребер.

Топологическая сортировка vs обход в глубину:

При обходе в глубину (Depth First Traversal, далее DFS) мы выводим вершину и затем рекурсивно вызываем DFS для смежных вершин. При топологической сортировке нам нужно вывести вершину перед ее смежными вершинами. Например, в данном графе вершина «5» должна быть выведена перед вершиной «0», и, в отличие от DFS, вершина «4» также должна быть выведена перед вершиной «0». Этим топологическая сортировка отличается от DFS. Например, DFS графа выше — «5 2 3 1 0 4», но это не топологическая сортировка.

Рекомендация: перед тем, как переходить к реализации алгоритма, попробуйте сначала разобраться с задачей на practice.

Алгоритм поиска топологической сортировки.

Для начала, рекомендуем ознакомиться с этой реализацией DFS. Мы можем модифицировать DFS так, чтобы в результате была получена топологическая сортировку графа. В DFS мы начинаем с подходящей вершины, которую сначала выводим, а затем рекурсивно вызываем DFS для ее смежных вершин. В топологической сортировке мы используем временный стек. Вершина не выводится сразу — сначала вызывается топологическая сортировка для всех смежных вершин, затем вершина помещается в стек. Только после обхода всех вершин содержимое стека выводится. Обратите внимание, что вершина помещается в стек только тогда, когда все смежные вершины (и их смежные вершины и т. д.) уже находятся в стеке.

Изображение ниже является иллюстрацией вышеупомянутого подхода:

Текст на изображении:
Лист смежности (G)
0 →
1→
2 → 3
3 → 1
4 → 0, 1
5 → 2, 0
Стек пустой
Шаг 1:
Топологическая сортировка (0), visited[0] = true
Список пуст. Больше нет рекурсивных вызовов.
Стек 0
Шаг 2:
Топологическая сортировка (1), visited[1] = true
Список пуст. Больше нет рекурсивных вызовов.
Стек 0 1
Шаг 3:
Топологическая сортировка (2),, visited[2] = true
Топологическая сортировка (3),, visited[3] = true
Вершина 1 уже посещена. Больше нет рекурсивных вызовов
Стек 0 1 3 2
Шаг 4:
Топологическая сортировка (4),, visited[4] = true
Вершины 0 и 1 уже посещены. Больше нет рекурсивных вызовов
Стек 0 1 3 2 4
Шаг 5:
Топологическая сортировка (5), visited[5] = true
Вершины 2 и 0 уже посещены. Больше нет рекурсивных вызовов
Стек 0 1 3 2 4 5
Шаг 6:
Вывод всех элементов стека сверху вниз

Ниже приведены реализации топологической сортировки. Пожалуйста, ознакомьтесь с реализацией DFT для несвязного графа и обратите внимание на различия между вторым кодом, приведенным там, и кодом, приведенным ниже.

C++

// Программа на C++ для вывода топологической сортировки DAG   #include<iostream> #include <list> #include <stack> using namespace std;    // Класс для представления графа class Graph {     int V;	// Количество вершин        //  Указатель на массив, содержащий список смежности     list<int> *adj;        // Функция, используемая topologicalSort     void topologicalSortUtil(int v, bool visited[], stack<int> &Stack); public:     Graph(int V);   // Конструктор         // Функция для добавления ребра в граф     void addEdge(int v, int w);        // Выводит топологическую сортировку графа     void topologicalSort(); };    Graph::Graph(int V) {     this->V = V;     adj = new list<int>[V]; }    void Graph::addEdge(int v, int w) {     adj[v].push_back(w); // Add w to v’s list. }    // Рекурсивная функция, используемая topologicalSort void Graph::topologicalSortUtil(int v, bool visited[],                                  stack<int> &Stack) {     // Помечаем текущий узел как посещенный     visited[v] = true;        // Рекурсивно вызываем функцию для всех смежных вершин     list<int>::iterator i;     for (i = adj[v].begin(); i != adj[v].end(); ++i)         if (!visited[*i])             topologicalSortUtil(*i, visited, Stack);        // Добавляем текущую вершину в стек с результатом     Stack.push(v); }    // Функция для поиска топологической сортировки.  // Рекурсивно использует topologicalSortUtil() void Graph::topologicalSort() {     stack<int> Stack;        // Помечаем все вершины как непосещенные     bool *visited = new bool[V];     for (int i = 0; i < V; i++)         visited[i] = false;        // Вызываем рекурсивную вспомогательную функцию      // для поиска топологической сортировки для каждой вершины     for (int i = 0; i < V; i++)       if (visited[i] == false)         topologicalSortUtil(i, visited, Stack);        // Выводим содержимое стека     while (Stack.empty() == false)     {         cout << Stack.top() << " ";         Stack.pop();     } }    // Программа для тестирования  int main() {     // Создаем граф, приведенный на диаграмме выше     Graph g(6);     g.addEdge(5, 2);     g.addEdge(5, 0);     g.addEdge(4, 0);     g.addEdge(4, 1);     g.addEdge(2, 3);     g.addEdge(3, 1);        cout << "Following is a Topological Sort of the given graph \n";     g.topologicalSort();        return 0; }

Java

// Программа на Java для поиска топологической сортировки import java.io.*; import java.util.*;    //  Этот класс представляет ориентированный граф с использованием списка смежности class Graph {     private int V;   // Количество вершин     private LinkedList<Integer> adj[]; // Список смежности        // Конструктор     Graph(int v)     {         V = v;         adj = new LinkedList[v];         for (int i=0; i<v; ++i)             adj[i] = new LinkedList();     }        // Функция для добавления ребра в граф     void addEdge(int v,int w) { adj[v].add(w); }        // Рекурсивная функция, используемая topologicalSort     void topologicalSortUtil(int v, boolean visited[],                              Stack stack)     {         //  Помечаем текущий узел как посещенный         visited[v] = true;         Integer i;            // Рекурсивно вызываем функцию для всех смежных вершин         Iterator<Integer> it = adj[v].iterator();         while (it.hasNext())         {             i = it.next();             if (!visited[i])                 topologicalSortUtil(i, visited, stack);         }            // Добавляем текущую вершину в стек с результатом         stack.push(new Integer(v));     }        // Функция для поиска топологической сортировки.     // Рекурсивно использует topologicalSortUtil()     void topologicalSort()     {         Stack stack = new Stack();            // Помечаем все вершины как непосещенные         boolean visited[] = new boolean[V];         for (int i = 0; i < V; i++)             visited[i] = false;            // Вызываем рекурсивную вспомогательную функцию         // для поиска топологической сортировки для каждой вершины         for (int i = 0; i < V; i++)             if (visited[i] == false)                 topologicalSortUtil(i, visited, stack);            // Выводим содержимое стека         while (stack.empty()==false)             System.out.print(stack.pop() + " ");     }        // Программа для тестирования     public static void main(String args[])     {         // Создаем граф, приведенный на диаграмме выше         Graph g = new Graph(6);         g.addEdge(5, 2);         g.addEdge(5, 0);         g.addEdge(4, 0);         g.addEdge(4, 1);         g.addEdge(2, 3);         g.addEdge(3, 1);            System.out.println("Following is a Topological " +                            "sort of the given graph");         g.topologicalSort();     } } // Этот код предоставлен Аакашем Хасия (Aakash Hasija)

Python

#Программа на Python для вывода результата поиска топографической сортировки DAG из коллекции import defaultdict    #Класс для представления графа class Graph:     def __init__(self,vertices):         self.graph = defaultdict(list) #dictionary containing adjacency List         self.V = vertices #No. of vertices        # Функция для добавления ребра в граф     def addEdge(self,u,v):         self.graph[u].append(v)        # Рекурсивная функция, используемая topologicalSort     def topologicalSortUtil(self,v,visited,stack):            # Помечаем текущий узел как посещенный         visited[v] = True            # Рекурсивно вызываем функцию для всех смежных вершин         for i in self.graph[v]:             if visited[i] == False:                 self.topologicalSortUtil(i,visited,stack)            # Добавляем текущую вершину в стек с результатом         stack.insert(0,v)        # Функция для поиска топологической сортировки.      # Рекурсивно использует topologicalSortUtil()     def topologicalSort(self):         # Помечаем все вершины как непосещенные         visited = [False]*self.V         stack =[]            # Вызываем рекурсивную вспомогательную функцию         # для поиска топологической сортировки для каждой вершины         for i in range(self.V):             if visited[i] == False:                 self.topologicalSortUtil(i,visited,stack)            # Выводим содержимое стека         print stack    g= Graph(6) g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1);    print "Following is a Topological Sort of the given graph" g.topologicalSort() # Код предоставлен Ниламом Ядавом (Neelam Yadav)

<b>Вывод:</b> Following is a Topological Sort of the given graph 5 4 2 3 1 0

Сложность по времени: приведенный выше алгоритм это DFS с дополнительным стеком. Таким образом, сложность времени такая же, как и у DFS, которая равна O(V+E).

Примечание: также можно использовать вектор вместо стека. Если используется вектор, чтобы получить топологическую сортировку, необходимо выводить элементы в обратном порядке.

Применение:

Топологическая сортировка в основном используется для составления графика работ из заданных зависимостей между ними. В компьютерных науках применяется для планирования команд, упорядочения ячеек для вычисления формулы при повторном вычислении значений формул в электронных таблицах, логического синтеза, определения порядка задач компиляции для выполнения в make-файлах, сериализации данных и разрешения символьных зависимостей в компоновщиках [2].