【输入】控制流图<N, E> G，回边m—>n
【输出】循环子图<N, E> loop
【流程】
1. 将m、n加入loop的结点集合，及m—>n加入loop的边集合，若m不等于n即不为自环，则加入m到queue（先进先出队列）
2. 若queue非空，则其从头出队得结点q；否则结束
3. 在G中遍历q的每一个前驱结点p，将p加入queue尾，若p不在loop结点集合中，则加入到loop结点集合，及边p—>q加入loop的边集合。转到步骤2继续
【分析】
正确性：检验最终loop中的结点集合是否满足自然循环的定义，注意到输入指定了回边，这说明n是m的支配结点，当为自环时只有一个结点而满足支配自反性，当不为自环时，加入的结点是m的所有直接与间接前驱，所以n也是它们的支配结点（假设不是，则必有m的一个前驱p，从入口结点经过p到m但不经过n，这与n是m的支配结点矛盾），且回边已在第1步加入loop，故满足了自然循环的定义。由于m在loop中的前驱数量是有限的，因此算法必然终止
复杂度：第3步判断p是否在loop结点集合中，取决于图的具体结构，设n为循环子图的结点数，若是邻接矩阵，则只需O(1)时间检测边是否存在，因此总耗时为O(n)。若为邻接表，检测边是否存在与结点数成正比，则总耗时为O(n^2)
其它算法：从m开始，标记n为visited，在G的反向流图中深度优先搜索，将访问到的结点及边加入loop，遇到n就回溯
posted on 2023-09-06 22:59
春秋十二月 阅读(39)
评论(0) 编辑 收藏 引用 所属分类:
Compiler