5.8. А
ЛГОРИТМЫ О СВЯЗНОСТИ ГРАФА
Понятие связности графа было введено в п. 5.1 настоящей главы. На-
помним, что в связном графе для любой пары вершин существует соединяю-
7 / 23
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: |
