192
щая их простая цепь. Далее будут рассмотрены некоторые алгоритмы, в ко-
торых существенным образом используется это понятие.
5.8.1. Т
ОПОЛОГИЧЕСКАЯ СОРТИРОВКА
Дан ориентированный граф без циклов, т. е. имеется
N узлов, пронуме-
рованных от 0 до
N
− 1, и из каждого узла выходят несколько ребер в другие
узлы. Задача
топологической сортировки формулируется
следующим обра-
зом
. Требуется упорядочить вершины графа так, чтобы конец любого ребра
предшествовал его началу.
Такое упорядочение вершин всегда возможно. Действительно, из усло-
вия отсутствия циклов вытекает, что есть узел, из которого не выходят ребра.
Выберем его в качестве исходного. Удаляя все ребра, ведущие в него, сводим
задачу к графу с меньшим числом узлов и продолжаем
рассуждение по ин-
дукции.
Напомним, что узлы ориентированного графа без циклов хранятся в эк-
земплярах класса
TNode (листинг 5.40).
Листинг 5.40. Структура узлов ориентированного графа
public
class TNode
{
public string name; //
public TEdge[] Edge; //
ребра
public bool visit;
public int x, y;
public int numVisit;
public Color color;
public int dist, oldDist;
}
В каждом
Node[i] хранится динамический массив ребер
Edge, элемен-
ты которого указывают на другие узлы. В поле
visit мы будем, как обычно,
хранить сведения о том, какие вершины пройдены, и корректировать его од-
новременно с прохождением узла.
Построим рекурсивный алгоритм, выполняющий топологическую сор-
тировку не
более чем за O(
N +
M)
действий, где
M — число ребер графа.
Программа будет помещать номера узлов в стек (листинг 5.41). Будем гово-
рить, что последовательность вершин
корректна, если:
8 / 23
193
− ни одна из вершин не посещалась дважды;
−
для любой вершины, входящей в
эту последовательность, все
вершины, в которые ведут исходящие из нее дуги, были помеще-
ны в стек до нее.
Do'stlaringiz bilan baham: 
