|
|
עמוד:292
2 . 3 בגרף החדש , שהתקבל בצעד , 2 . 2 יש לצרף כל קדקוד שאין לו קדקודים מקדימים לתור . ( Q ) . 3 בשלב הזה , התור ריק והאלגוריתם מסתיים . לפנינו שלוש שאלות עיקריות . . 1 איך מבטאים את סדר הקדימות בין הפעילויות השונות בקלט י . 2 כיצד נייצג את הגרף ? . 3 כיצד אפשר לקבוע לאיזה קדקוד אין קדקוד מקדים ל נענה על השאלות האלו להלן איד מבטאים את סדר הקדימויות ! סדר הקדימות מתבטא בקלט באמצעות זוגות סדורים . כל שורה בקלט מכילה שמות של שתי פעילויות המופיעות זו אחר זו , כאשר הראשונה צריכה להתבצע לפני השנייה . כיצד נייצג את הגרף ן אם מספר הקדקודים בגרף ידוע מראש , אז יש אפשרות לייצג את הגרף באמצעות מטריצת סמיכות או רשימות סמיכות - ולא , נשתמש בייצוג המקושר של גרף . בהמשך נניח שמספר הקדקודים בגרף ידוע מראש , והגרף מיוצג באמצעות רשימות סמיכות . כיצד אפשר לקבוע לאיזה קדקוד אין קדקוד מקדים ? לשם כך נחזיק מערך בשם indegree כך indegree [/] - \ y מכיל את מספר הקדקודיס הקודמים לקדקוד j אם indegree [/] שווה אפס , פירוש הדבר שלקדקוד j אין קדקודים מקדימים וניתן לצרף אותו לתור . Q זאת כיוון שבתור Q נמצאים קדקודים שאין להם מקדימים והם אמורים לצאת מהתור אחד אחרי השני ולהצטרף לרשימה המייצגת מיון טופולוגי . בכל פעם שהקדקוד ז יוצא מן התור , יש לעבור על רשימת הסמיכות של הקשתות היוצאות מן הקדקוד j ולהפחית את המערך indegree [&] של כל צומת K הסמוך rm wt לסיכום , להלן האלגוריתם למיון טופולוגי בעזרת התור ? TP _ Sort ( Graph G ) {
|
|