אלגוריתם למציאת רכיבי קשירות
חזקה משתמש בגרף ההופכי וכן באלגוריתם סריקה לעומק. אנו
מקווים שבשלב זה ידוע לך היטב על שני נושאים אלו.
אלגוריתם זה אינו מסובך במיוחד והוא בעל 4 שלבים בלבד. נציג
את הפסאדו-קוד, ננתח אותו וכמובן נראה דוגמת הרצה מעניינת.
פסאדו-קוד
1. DFS(G)
2. Create G-Transpose
3. DFS(G-Transpose) pick vertices in order of decreasing
finish time of DFS in stage 1
4. Output each tree from DFS in stage 3.
הסבר:
תחילה נבצע DFS
לגרף המקורי (שורה 1), נחשב את הגרף ההופכי (שורה 2).
נחשב DFS לגרף ההופכי, אם שינוי קטן מהאלגורתם המוכר, בזמן
בחירת הקודקודים, נבחר לפי סדר הסיום היורד שלהם שהתגלה
ב DFS על גרף המקור. (שורה 3).
כל עץ ביער העומק אחרי ה DFS על הגרף ההופכי הוא למעשה רכיב
קשירות חזקה.
