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

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

---

Топологическая сортировка для ориентированного ациклического графа (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].

Статьи по теме

Алгоритм Кана для топологической сортировки: еще один O(V+E) алгоритм.
Все топологические сортировки ориентированного ациклического графа

Ссылки

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm
http://en.wikipedia.org/wiki/Topological_sorting

Пожалуйста, оставьте комментарий, если обнаружите ошибку, или если захотите поделиться дополнительной информацией по обсуждаемой теме.

---

Узнать подробнее о курсе.

---