Разработка компиляторов
Выделение максимального альта
Приведем алгоритм выделения максимального альта, для которого данная вершина p является начальной.
Алгоритм состоит из трех шагов:
- вначале все вершины графа помечаются как "черные"
- затем все вершины, достижимые из p, помечаются как "серые"
- если среди серых вершин найдется вершина v , которая отлична от p и имеет хотя бы одно входящее ребро, ведущее из "черной" вершины, то эта вершина красится в "черный" цвет.
Можно показать, что в конце работы алгоритма множество "серых" вершин и будет максимальным альтом, начинающимся в вершине p .
Пример работы алгоритма показан на слайде. Крайний левый граф - это граф после первого шага. Средний рисунок изображает граф после того, как все вершины, достижимые из p , покрашены в "серый" цвет. Здесь же стрелочкой обозначена вершина, имеющая своим предком "черную" вершину. Окончательный альт показан на крайнем правом рисунке.
