【輸入】控制流圖<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
春秋十二月 閱讀(48)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler