Часть 5. Алгоритмы на графах. Последовательность графов на данном рисунке показывает, как формируется транзитивное замыкание (внизу) орграфа

РИСУНОК 19.16. АЛГОРИТМ УОРШАЛЛА

Последовательность графов на данном рисунке показывает, как формируется транзитивное замыкание (внизу) орграфа, выбранного в качестве примера (вверху) путем применения алгоритма Уоршалла. Первая итерация цикла (левая колонка, вверху) добавляет ребра 1-2 и 1-5 в силу существо­вания путей 1-0-2 и 1-0-5, которые содержат вершину 0 (но не содержат вершины с более высокими номерами); вторая итерация цикла (левая колонка, вторая сверху) добавляет ребра 2-0 и 2-5 в силу существования путей 2-1-0 и 2-1-0-5, которые содержат вершину 1 (но ни одной вершины с более высоким номером); третья итерация цикла (левая колонка, внизу) добавляет ребра 0-1, 3-0, 3-1 и 3-5 в силу существования путей 0-2-1, 3-2-1-0, 3-2-1 и 3-2-1-0-5, которые содержат вершину 2 (но ни одной вершины с более высоким номером). В правой колонке показаны ребра, добавленные в результате просмотра вершин 3, 4 и 5. Последняя итерация цикла (правая колонка, внизу) добавляет ребра, ведущие из вершин 0, 1 и 2 в вершину 4, поскольку единственные ориентированные пути из этих вершин в вершину 4, включают 5, т.е. вершину с наивысшим номером.

Глава 19. Орграфы и ориентированные ациклические графы

Программа 19.3 Алгоритм Уоршалла_________________________________________

Конструктор класса ТС вычисляет транзитивное замыкание графа G в приватном элементе данных Т, так что клиентские программы могут использовать объекты ТС для проверки, достижима ли заданная вершина орграфа из любой другой вершины. Конструктор инициализирует Т копией графа G, добавляет петли, затем в завершение вычислений использует алгоритм Уоршалла. Класс tcGraph должен включать реализацию проверки edge на предмет существования ребра.

template < class tcGraph, class Graph> class TC

{ tcGraph T;

public:

TC (const Graph & G): T(G) { for (int s = 0; s < T.V(); s++)

T.insert(Edge(s, s)); for (int i = 0; i < T.V(); i++) for (int s = 0; s < T.V(); s++) if (T.edge(s, i))

for (int t = 0; t < T.V(); t++) if (T.edge(i, t))

T.insert(Edge(s, t)); } bool reachable (int s, int t) const

{ return T.edge(s, t); } };

Мы используем термин абстрактное транзитивное замыкание (abstract transitive closure) для обозначения АТД, который предоставляет клиентам возможность проверки после предварительной обработки графа, аналогичной применяемой в программе 19.3. В этом контексте у нас возникает потребность оценки алгоритма не только в аспекте стоимос­ти вычисления транзитивного замыкания (стоимость предварительной обработки), но и в аспектах требуемого пространства памяти и достижимого времени ответа на запросы. То есть, мы предлагаем следующую формулировку свойства 19.7:

Свойство 19.8. Мы можем поддерживать выполнение проверки заданного орграфа на до­стижимость (абстрактное транзитивное замыкание) за постоянное время ценой затрат пространства памяти, пропорционального V², и времени, пропорционального V³, затрачи­ваемого на предварительную обработку.

Доказательство: Это свойство непосредственно следует из базовых рабочих характе­ристик алгоритма Уоршалла. ■

Для большинства приложений нашей целью остается не только быстрое вычисление транзитивного замыкания орграфа, но и обеспечение постоянного времени обслужива­ния запросов относительно абстрактного транзитивного замыкания с гораздо меньшими затратами пространства памяти и намного меньшими затратами времени на предваритель­ную обработку, чем указано в определении 19.8. Можем ли мы найти такую реализацию, которая позволила бы строить клиентские программы, способные выполнять обработку таких графов? Мы вернемся к обсуждению этого вопроса в разделе 19.8.

Существует неформальная внутренняя связь между задачей вычисления транзитивно­го замыкания орграфа и некоторым числом других фундаментальных вычислительных задач, и эта связь может оказаться полезной для нашего понимания трудностей решения