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



         

Построение отношения обязательного предшествования


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

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




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