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



         

Построение глубинного остовного дерева


На слайде приведен алгоритм построения остовного дерева, определения типов дуг графа по отношению к нему и построения нумераций 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), то эта дуга - прямая




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