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