Разработка компиляторов
Построение глубинного остовного дерева
На слайде приведен алгоритм построения остовного дерева, определения типов дуг графа по отношению к нему и построения нумераций Pre и Post .
Алгоритм обходит вершины графа, начиная со start . При входе в очередную вершину ей присваивается очередной номер нумерации Pre , при этом номера Pre присваиваются в порядке возрастания. Далее рассматриваются все потомки этой вершины, которые еще не рассматривались. К каждому потомку применяется этот же самый шаг алгоритма - таким образом, обеспечивается обход в глубину. Наконец, после рассмотрения всех потомков текущей вершины ей присваивается очередной номер нумерации Post . При этом номера Post присваиваются в порядке убывания.
По ходу работы алгоритма поддерживается три состояния вершин:
- Init - вершина еще не рассматривалась алгоритмом
- InProcess - вершина еще рассматривается алгоритмом (т.е. алгоритм находится в процессе обработки вершин, достижимых из данной)
- Done - вершина уже исключена из рассмотрения (т.е. все достижимые из нее вершины уже обработаны).
Для определения типа дуги используется состояние конечной вершины и нумерация Pre . Если вершина, в которую можно попасть из данной, еще не рассматривалась, то ребро, по которому в нее можно попасть, объявляется деревянным. Для определения остальных типов дуг используются следующие очевидные утверждения:
- если в дуге (v, w) w находится в состоянии InProcess, то эта дуга - обратная
- если в дуге (v, w) w находится в состоянии Done, и Pre(w)<Pre(v), то эта дуга - поперечная
- если в дуге (v, w) w находится в состоянии Done, и Pre(w)>Pre(v), то эта дуга - прямая
