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

       

Выделение линейных компонент в сводимом графе



увеличить изображение

Идея алгоритм выделения линейных компонент в сводимом графе опирается на использование свойств, сформулированных выше.

Алгоритм обходит граф в порядке возрастания T-номеров и добавляет вершины в текущую линейную компоненту. Признаком завершения линейной компоненты является то, что вершина со следующим номером является, во-первых, бивершиной, а во-вторых, ее номер - максимальный среди номеров всех потомков вершин текущей линейной компоненты.

Разбиение графа на линейные компоненты изображено на рисунке на слайде.



Содержание раздела