ראשי > אלגוריתמים בסיסיים בתורת הגרפים > מיון טופולוגי > מיון טפולוגי

מיון טפולוגי

מבוא לאלגוריתם

אלגוריתם מיון טופולוגי מסתמך על סריקה לעומק ולכן מומלץ לעבור על אלגוריתם זה שוב לפני שניגשים למיון טפולוגי. האלגוריתם שנציג הוא פשוט ביותר וכולל בדיוק שני שלבים.

האלגוריתם

1. DFS(G)
2. Use descending finishing-order of DFS to order the vertices

הסבר:
בשלב הראשון נריץ DFS על הגרף, בזמן הסריקה נסמן את זמן הסיום - f של כל קודקוד. נחזיר את הקודקודים ממוינים לפי זמן הסיום.

הדגמת האלגוריתם