Рубрики

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

Топологическая сортировка для направленного ациклического графа (DAG) представляет собой линейное упорядочение вершин, такое, что для каждого направленного ребра uv вершина u предшествует v в упорядочении. Топологическая сортировка для графа невозможна, если граф не является DAG.

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

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

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

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

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

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); // Добавить w в список v.

}

  
// Рекурсивная функция, используемая 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-программа для печати топологической сортировки DAG

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 для печати топологической сортировки DAG

from collections import defaultdict

  
# Класс для представления графика

class Graph:

    def __init__(self,vertices):

        self.graph = defaultdict(list) #dictionary, содержащий список смежности

        self.V = vertices #No. вершин

  

    # функция для добавления ребра на график

    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()
# Этот код предоставлен Ниламом Ядавом


Выход:

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

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

Рекомендуемые посты:

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

0.00 (0%) 0 votes