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

       

Выделение компонент сильной связности (1)


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

Для выделения компонент сильной связности построим нумерацию T , такую, что для би-вершин порядок, задаваемый T-номерами, совпадает с порядком, задаваемым Post-номерами, а все компоненты сильной связности заполнены T-номерами последовательно.



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