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