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

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

[עריכה] אלגוריתם לביצוע מיון טופולוגי

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