Topological sorting

Translation of the article prepared in advance of the start of the course “Algorithms for developers”.


Topological sorting for a directed acyclic graph (Directed Acyclic Graphs, hereinafter referred to as DAG) is a linear ordering of vertices for which the following condition holds: for each directed edge uv vertex u precedes vertex v in ordering. If the graph is not a DAG, then topological sorting is not possible for it.

For example, the topological sorting of the graph below is “5 4 2 3 1 0”. A graph may have several topological sortings. For example, another topological sorting for the same graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always the vertex without incoming edges.

Topological sorting vs depth traversal:

At walk in depth (Depth First Traversal, hereinafter Dfs) we output the vertex and then recursively call DFS for adjacent vertices. In topological sorting, we need to display the vertex in front of its adjacent vertices. For example, in this graph, the vertex “5” should be displayed in front of the vertex “0”, and, unlike Dfs, vertex “4” should also be displayed in front of vertex “0”. This distinguishes topological sorting from DFS. For example, the DFS of the column above is “5 2 3 1 0 4”, but this is not a topological sort.

Recommendation: before moving on to the implementation of the algorithm, first try to understand practice task.

Topological Sort Search Algorithm.

To get started, we recommend that you familiarize yourself with this DFS implementation. We can modify Dfs so that the result is a topological sorting of the graph. AT Dfs we start with a suitable vertex, which we first output, and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. A vertex is not output immediately – first, topological sorting is called for all adjacent vertices, then the vertex is pushed onto the stack. Only after traversing all the vertices is the contents of the stack displayed. Note that a vertex is pushed onto the stack only when all adjacent vertices (and their adjacent vertices, etc.) are already on the stack.

The image below is an illustration of the above approach:

Text on image:
Adjacency Sheet (G)

0 →
1 →
2 → 3
3 → 1
4 → 0, 1
5 → 2, 0
Stack is empty
Step 1:
Topological Sort (0), visited[0] = true
The list is empty. No more recursive calls.
Stack 0
Step 2:
Topological Sort (1), visited[1] = true
The list is empty. No more recursive calls.
Stack 0 1
Step 3:
Topological Sort (2) ,, visited[2] = true
Topological Sort (3) ,, visited[3] = true
Top 1 has already been visited. No more recursive calls
Stack 0 1 3 2
Step 4:
Topological Sort (4) ,, visited[4] = true
Vertices 0 and 1 are already visited. No more recursive calls
Stack 0 1 3 2 4
Step 5:
Topological Sort (5), visited[5] = true
Peaks 2 and 0 are already visited. No more recursive calls
Stack 0 1 3 2 4 5
Step 6:
The output of all elements of the stack from top to bottom

The following are topological sort implementations. Please check out the implementation DFT for a disconnected graph and note the differences between the second code given there and the code below.

C ++

// Программа на C++ для вывода топологической сортировки DAG
 
#include
#include 
#include 
using namespace std;
  
// Класс для представления графа
class Graph
{
    int V;	// Количество вершин
  
    //  Указатель на массив, содержащий список смежности
    list *adj;
  
    // Функция, используемая topologicalSort
    void topologicalSortUtil(int v, bool visited[], stack &Stack);
public:
    Graph(int V);   // Конструктор
  
     // Функция для добавления ребра в граф
    void addEdge(int v, int w);
  
    // Выводит топологическую сортировку графа
    void topologicalSort();
};
  
Graph::Graph(int V)
{
    this->V = V;
    adj = new list[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 &Stack)
{
    // Помечаем текущий узел как посещенный
    visited[v] = true;
  
    // Рекурсивно вызываем функцию для всех смежных вершин
    list::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 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 adj[]; // Список смежности
  
    // Конструктор
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i 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)
Вывод:
Following is a Topological Sort of the given graph
5 4 2 3 1 0

Difficulty in time: the above algorithm is DFS with an extra stack. Thus, the time complexity is the same as that of DFS, which is equal to O (V + E).

Note: You can also use a vector instead of a stack. If you use a vector to get topological sorting, you need to output the elements in the reverse order.

Application:

Topological sorting is mainly used for scheduling work from given dependencies between them. In computer science, it is used to plan commands, organize cells for calculating formulas when recalculating formula values ​​in spreadsheets, logical synthesis, determining the order of compilation tasks to be performed in makefiles, data serialization, and resolving symbolic dependencies in linkers[[2].

Related Articles:

Kahn algorithm for topological sorting: another O (V + E) algorithm.
All topological sortings of an oriented acyclic graph

References:

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

Please leave a comment if you find an error, or if you want to share additional information on the topic under discussion.


Learn more about the course.


Similar Posts

Leave a Reply