Топологическая сортировка
Топологическая сортировка — это расположение вершин ориентированного графа в таком порядке, чтобы каждая вершина шла после всех вершин, от которых она зависит. Такой порядок используют, например, для планирования работ или выполнения заданий с предварительными условиями.
Граф рассматривают как ориентированный граф: направление дуги показывает зависимость. Если дуга \(u \to v\), сначала должна быть выполнена работа \(u\), а затем работа \(v\). В задачах сетевого графа такая последовательность помогает определить допустимый порядок событий.
Как строят порядок
Один из способов — алгоритм удаления вершин с нулевой входящей степенью. Сначала выбирают вершину, в которую не входит ни одной дуги, добавляют её в результат и удаляют вместе с исходящими дугами. Затем повторяют действие для новых вершин с нулевой входящей степенью.
Если удаётся удалить все вершины, получена топологическая сортировка. Если на некотором шаге подходящих вершин нет, но вершины ещё остались, в графе есть цикл, поэтому топологическая сортировка невозможна.
Пусть зависимости заданы дугами \(A \to B\), \(A \to C\), \(B \to D\), \(C \to D\). Вершина \(A\) должна быть первой. После неё можно выбрать \(B\) и \(C\) в любом порядке, а \(D\) — только последней. Один из вариантов: \(A, B, C, D\). Вариант \(A, C, B, D\) тоже верен.
Топологическая сортировка не обязана быть единственной: если между двумя вершинами нет зависимости, их порядок может различаться. Кроме того, она применяется именно к ориентированному графу без циклов. Например, при цикле \(A \to B \to C \to A\) невозможно поставить каждую вершину после предшественника.
Для какого графа топологическая сортировка невозможна?
Главное
- Топологическая сортировка задаёт порядок вершин с учётом направленных зависимостей.
- Она существует только для ориентированного графа без циклов.
- При обнаружении цикла подходящий порядок построить нельзя.