Разработка компиляторов



         

Выделение максимального альта


Приведем алгоритм выделения максимального альта, для которого данная вершина p является начальной.

Алгоритм состоит из трех шагов:

  • вначале все вершины графа помечаются как "черные"
  • затем все вершины, достижимые из p, помечаются как "серые"
  • если среди серых вершин найдется вершина v , которая отлична от p и имеет хотя бы одно входящее ребро, ведущее из "черной" вершины, то эта вершина красится в "черный" цвет.

Можно показать, что в конце работы алгоритма множество "серых" вершин и будет максимальным альтом, начинающимся в вершине p .

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




Содержание  Назад  Вперед