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