מוטיבציה

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

למה ללמוד מיון טופולוגי?

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

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