מיון טופולוגי

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

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

הניסוח המתמטי המדויק של בעיית מיון טופולוגי נעזר בתורת הגרפים: בהינתן גרף מכוון חסר מעגלים (DAG), מיון טופולוגי שלו הוא מתן מספרים לצמתי הגרף בצורה כזו שאם יש קשת מצומת a אל צומת b, המספר שניתן ל-a קטן מהמספר שניתן ל-b. ניתן להוכיח כי לכל גרף מכוון חסר מעגלים קיים מיון טופולוגי אחד לפחות, וייתכן שקיימים מיונים טופולוגים רבים. לעומת זאת, אם הגרף מכיל מעגל, אז אין לו מיון טופולוגי.

אלגוריתם לביצוע מיון טופולוגי

ניתן לבצע מיון טופולוגי בזמן ריצה לינארי במספר הצמתים והקשתות שבגרף - $\ O(|V|+|E|)$. מבחינה רעיונית, האלגוריתם מהווה הרחבה של אלגוריתם חיפוש לעומק, עם תוספת בודדת: כאשר אלגוריתם החיפוש לעומק מסיים את הרקורסיה עבור צומת מסוים, הוא מכניס אותו לתחילת המיון הטופולוגי. דבר זה מבטיח שאיבר ייכנס לתחילת המיון רק לאחר שכל האיברים המחוברים אליו כבר הוכנסו, ולכן הוא יוכנס למקום מוקדם יותר במיון.

אלגוריתם נוסף בסיבוכיות זהה:

קטע הקוד הבא הוא פסאודו קוד.

TopSort(G)
    k=0
    while $\exists s\in V$ s.t. s's indegree = 0
        Sorted[k]=s
        k++
        remove s and all its outgoing edges
    if k=n then successful
    else failed

לקריאה נוספת

• תומאס ה. קורמן, צ'ארלס א. לייזרסון, רונאלד ל. ריבסט, מבוא לאלגוריתמים, הוצאת MIT, תורגם לעברית על ידי האוניברסיטה הפתוחה.