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



        татуаж бровей   

Выделение сильно связных подграфов (2)



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

Для выделения сильно связных подграфов, таким образом, достаточно научиться выделять области. Заметим, однако, что, несмотря на то, что области при нумерации Post сильно связны, это не означает, что произвольные сильно связные подграфы будут областями при нумерации Post .

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

Примеры подграфов, выделенных с помощью алгоритма, приведены на иллюстрации. Стрелочками отмечены вершины, области которых выделены.




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