|
|
עמוד:284
5 . 6 . 3 אלגוריתם למציאת רכיבי קשירות חזקה בגרפים מכוונים ( Strong Connected Component — SCC ) צעד : 1 מריצים אלגוריתם , DFS ( G ) ויוצרים רשימת קדקודים ( L ) אשר ממוינת בסדר יורד לפי הזמן של סיום הטיפול בהם . T T צעד . 2 הופכים את הגרף 0 = 0 '' , £ ) ומקבלים G - ( V , E ) כאשר , E = {( £ / , V )\( V , U ) eE ] כלומר הופכים את קשתות הגרף . צעד : 3 מריצים אלגוריתם , DFS ( G ) כך שהלולאה המרכזית של DFS עוברת על קדקודי הגרף לפי הסדר , כפי שנקבע בצעד 1 ברשימה . L העצים הפורשים DFS שמתקבלים בסוף צעד 3 הם רכיבי הקשירות החזקה של הגרף t יעילות האלגוריתם צעד 1 דורש זמן 0 {\ E \) + | v' |) צעד 2 דורש זמן /|) ז 0 (| £ |) + | צעד 3 דורש זמן 0 (\ E \) + \ v \) וביחד : סיבוביות זמן הריצה של האלגוריתם הנידון היא ! ? O (\ E \) + \ V \) נדגים את אופן הפעולה של האלגוריתם ( SCQ שתואר לעיל על הגרף שלהלן י צעד 1 נריץ את האלגוריתם DFS ( G ) כאשר קדקוד המקור הוא . a תמונת המצב בסיום השלב הזה מוצגת באיור שלהלן
|
|