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

       

Выделение лучей



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

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

Результатом работы алгоритма является два списка Starts и Ends , первый из которых содержит начальные вершины максимальных лучей, а второй - выходные.

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



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