Как сделать топологическую сортировку

Обновлено: 24.01.2025

Нерекурсивный алгоритм топологической сортировки ориентированного графа без циклов.

Предположим, что граф имеет вершины с номерами 1..n, для каждой вершины i известно число num[i] выходящих из нее ребер и номера вершин dest[i][1]. dest[i][num[i]], в которые эти ребра ведут. Будем условно считать, что ребра перечислены 'слева направо': левее то ребро, у которого номер меньше. Нам надо напечатать все вершины в таком порядке, чтобы конец любого ребра был напечатан перед его началом. Мы предполагаем, что в графе нет ориентированных циклов - иначе такое невозможно.

Для начала добавим к графу вершину 0, из которой ребра ведут в вершины 1. n. Если ее удастся напечатать с соблюдением правил, то тем самым все вершины будут напечатаны.

Алгоритм хранит путь, выходящий из нулевой вершины и идущий по ребрам графа. Переменная l отводится для длины этого пути. Путь образован вершинами vert[1]. vert[l] и ребрами, имеющими номера edge[1]. edge[l]. Номер edge[s] относится к нумерации ребер, выходящих из вершины vert[s]. Тем самым для всех s должны выполняться неравенство

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

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

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

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

using namespace std;

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

int V; // Количество вершин

// Указатель на массив, содержащий списки смежности

// Функция, используемая topologicalSort

void topologicalSortUtil( int v, bool visited[], stack int > &Stack);

Graph( int V); // Конструктор

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

void addEdge( int v, int w);

// выводит топологическую сортировку полного графа

Graph::Graph( int 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)

// Пометить текущий узел как посещенный.

// Повторение для всех вершин, смежных с этой вершиной

list int >::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

topologicalSortUtil(*i, visited, Stack);

// Вставляем текущую вершину в стек, в котором хранится результат

// Функция для топологической сортировки. Он использует рекурсивный
// topologicalSortUtil ()

stack int > Stack;

// Пометить все вершины как не посещенные

bool *visited = new bool [V];

for ( int i = 0; i

// Вызываем рекурсивную вспомогательную функцию для хранения топологии

// Сортировка, начиная со всех вершин по одной

for ( int i = 0; i

if (visited[i] == false )

topologicalSortUtil(i, visited, Stack);

// Распечатать содержимое стека

while (Stack.empty() == false )

// Программа драйвера для проверки вышеуказанных функций

// Создать график, приведенный на диаграмме выше

cout "Following is a Topological Sort of the given graph \n" ;

// Java-программа для печати топологической сортировки DAG

// Этот класс представляет ориентированный граф с использованием смежности
// представление списка

private int V; // Количество вершин

private LinkedList adj[]; // Список смежности

adj = new LinkedList[v];

for ( int i= 0 ; i

adj[i] = new LinkedList();

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

void addEdge( int v, int w)

// Рекурсивная функция, используемая topologicalSort

void topologicalSortUtil( int v, boolean visited[],

// Пометить текущий узел как посещенный.

// Повторять для всех смежных вершин

Iterator it = adj[v].iterator();

topologicalSortUtil(i, visited, stack);

// Вставляем текущую вершину в стек, в котором хранится результат

stack.push( new Integer(v));

// Функция для топологической сортировки. Оно использует

Stack stack = new Stack();

// Пометить все вершины как не посещенные

boolean visited[] = new boolean [V];

for ( int i = 0 ; i

// Вызов рекурсивной вспомогательной функции для сохранения

// Топологическая сортировка, начиная со всех вершин

for ( int i = 0 ; i

if (visited[i] == false )

topologicalSortUtil(i, visited, stack);

// Распечатать содержимое стека

while (stack.empty()== false )

public static void main(String args[])

// Создать график, приведенный на диаграмме выше

Graph g = new Graph( 6 );

System.out.println( "Following is a Topological " +

"sort of the given graph" );

>
// Этот код предоставлен Aakash Hasija

from collections import defaultdict

def __init__( self ,vertices):

def addEdge( self ,u,v):

def topologicalSortUtil( self ,v,visited,stack):

for i in self .graph[v]:

if visited[i] = = False :

stack.insert( 0 ,v)

def topologicalSort( self ):

visited = [ False ] * self .V

for i in range ( self .V):

if visited[i] = = False :

print "Following is a Topological Sort of the given graph"

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

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

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

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

Если в ориентированном графе нет контуров (путей у которых начальная и конечная вершины совпадают), то можно перенумеровать вершины данного графа таким образом, что для каждой дуги (i,j) будет выполняться условие i

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

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

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.

Содержание

Пример

$G=\Bigl ( \bigl \<2, 3, 5, 7, 8, 9, 10, 11 \bigr \></p> <p>Для графа , \bigl \<(3, 8), (3, 10), (5, 11), (7, 11), (7, 8), (8, 9), (11, 2), (11, 9), (11, 10)\bigr \>\Bigr )$

существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, например:

Видно, что в последовательности могут быть переставлены любые две стоящие рядом вершины, которые не входят в отношение частичного порядка .

Алгоритм

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

Наличие хотя бы одного контура в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину .

Пример работы алгоритма

шаг
0	$\varnothing$					$\varnothing$
1	$\varnothing$	$\varnothing$	$\varnothing$
2	$\varnothing$	$\varnothing$	$\varnothing$
3	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$
4	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$
5	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$

На втором шаге вместо может быть выбрана вершина , поскольку порядок между и не задан.

Применение

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

Можно построить список отображения объектов в изометрической проекции зная парные порядковые отношения между объектами (какой из двух объектов должен быть прорисован раньше).

Читайте также: