Как сделать топологическую сортировку
Обновлено: 06.07.2024
Нерекурсивный алгоритм топологической сортировки ориентированного графа без циклов.
Предположим, что граф имеет вершины с номерами 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‰).
Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.
Содержание
Пример
существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, например:
Видно, что в последовательности могут быть переставлены любые две стоящие рядом вершины, которые не входят в отношение частичного порядка .
Алгоритм
Пусть дан бесконтурный ориентированный простой граф . Через обозначим множество вершин таких, что . То есть, — множество всех вершин, из которых есть дуга в вершину . Пусть — искомая последовательность вершин.
Наличие хотя бы одного контура в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину .
Пример работы алгоритма
| шаг | |  |  |  |  |  |  |
|---|---|---|---|---|---|---|---|
| 0 |  |  |  | |  |  | |
| 1 | | | | |  |  | |
| 2 |  | | | |  |  |  |
| 3 | | | | | | |  |
| 4 | | | | | | |  |
| 5 |  | | | | | |  |
На втором шаге вместо может быть выбрана вершина , поскольку порядок между и не задан.
Применение
При помощи топологической сортировки строится корректная последовательность выполнения действий, всякое из которых может зависеть от другого: последовательность прохождения учебных курсов студентами, установки программ при помощи пакетного менеджера, сборки исходных текстов программ при помощи Makefile'ов.
Можно построить список отображения объектов в изометрической проекции зная парные порядковые отношения между объектами (какой из двух объектов должен быть прорисован раньше).
Читайте также: