Построение натуральных циклов (домашние задания)

Граф Потока Управления (ГПУ)Алгоритм начинается на слайде 13, 6-й лекцииentryL2:11 t4 < m;12 return t4;L3:14 t5 < *, 4, m15 t6 < +, a, t516 t7 < a[t6]17 ifTrue t7 > v18 goto L419 else20 goto L5L4:22 r < -, m, lL5:24 l < +, m, 1L1:02 t1 < +, l, r03 m < /, t1, 204 t2 < *, 4, m05 t3 < a[t2]06 ifTrue t3 == v07 goto L208 else09 goto L3L0L1L2L3L4L5L6:26 ifTrue r >= l27 goto L128 else29 goto L7L6L7:31 t4 < -132 return t4L7exitL8Построение натурального цикла по обратному ребруL0L1L2L3L4L5L6L7L8В этом графе всего лишь одно обратно ребро, по нему и будемстроить натуральный графПо алгоритму после выбора ребра нужно найти пути поиском вглубину из вершины L6 в L1 по обратно-ориентированномуграфу, без обратного ребра.Вершина L6 помечена как пройденнаяПостроение натурального цикла по обратному ребруL0L1L2L3L4L5L6L7L8Результат алгоритма поиска в глубину (но в полной своейверсии, т.е.

мы не бросили алгоритм, при нахождении первогопути из L6 в L1, а продолжаем рекурсивный обход графа)(мы нашли «полное» тело цикла)Построение натурального цикла по обратному ребруL0L1L2L3L4L5L6L7L8Больше обратных рёбер в нашем цикле нету, а значит этоединственный натуральный цикл.