【輸入】控制流圖<N, E> G，回邊m—>n
【輸出】循環(huán)子圖<N, E> loop
【流程】
1. 將m、n加入loop的結(jié)點(diǎn)集合，及m—>n加入loop的邊集合，若m不等于n即不為自環(huán)，則加入m到queue（先進(jìn)先出隊(duì)列）
2. 若queue非空，則其從頭出隊(duì)得結(jié)點(diǎn)q；否則結(jié)束
3. 在G中遍歷q的每一個(gè)前驅(qū)結(jié)點(diǎn)p，將p加入queue尾，若p不在loop結(jié)點(diǎn)集合中，則加入到loop結(jié)點(diǎn)集合，及邊p—>q加入loop的邊集合。轉(zhuǎn)到步驟2繼續(xù)
【分析】
正確性：檢驗(yàn)最終loop中的結(jié)點(diǎn)集合是否滿足自然循環(huán)的定義，注意到輸入指定了回邊，這說明n是m的支配結(jié)點(diǎn)，當(dāng)為自環(huán)時(shí)只有一個(gè)結(jié)點(diǎn)而滿足支配自反性，當(dāng)不為自環(huán)時(shí)，加入的結(jié)點(diǎn)是m的所有直接與間接前驅(qū)，所以n也是它們的支配結(jié)點(diǎn)（假設(shè)不是，則必有m的一個(gè)前驅(qū)p，從入口結(jié)點(diǎn)經(jīng)過p到m但不經(jīng)過n，這與n是m的支配結(jié)點(diǎn)矛盾），且回邊已在第1步加入loop，故滿足了自然循環(huán)的定義。由于m在loop中的前驅(qū)數(shù)量是有限的，因此算法必然終止
復(fù)雜度：第3步判斷p是否在loop結(jié)點(diǎn)集合中，取決于圖的具體結(jié)構(gòu)，設(shè)n為循環(huán)子圖的結(jié)點(diǎn)數(shù)，若是鄰接矩陣，則只需O(1)時(shí)間檢測(cè)邊是否存在，因此總耗時(shí)為O(n)。若為鄰接表，檢測(cè)邊是否存在與結(jié)點(diǎn)數(shù)成正比，則總耗時(shí)為O(n^2)
其它算法：從m開始，標(biāo)記n為visited，在G的反向流圖中深度優(yōu)先搜索，將訪問到的結(jié)點(diǎn)及邊加入loop，遇到n就回溯
posted on 2023-09-06 22:59
春秋十二月 閱讀(61)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Compiler