|
|
صفحة: 291
בשלב הזה לשני הקדקודים C £ -ו אין קדקודים מקדימים , ולכן נבחר באופן מקרי אחד מהם ונצרף אותו לרשימה המייצגת מיון טופולוגי . נניח שבחרנו בקדקוד C מבין הקדקודים . C-1 E לאחר שהפעילות C בוצעה , תמונת הרשת היא ! בשלב הזה לקדקוד E אין קדקוד מקדים ( והוא היחיד . ( עתה נבצע את הפעילות E והרשת היא גרף ריק . בזה מסתיים התהליך שקובע את המיון הטופולוגי . סופית , המיון הטופולוגי שהתקבל הוא : ABDCE הערה 1 ייתכן שבשלב מסוים יהיו יותר מקדקוד אחד שאין לו קדקוד מקדים . ואולם מאחר שבכל שלב ניתן לבצע רק פעילות אחת בלבד , אז בוחרים באופן מקרי קדקוד אחד מבין הקדקודיס שאין להם קדקודים מקדימים ומצרפים אותו לרשימה המייצגת מיון טופולוגי . הדבר יוצר מספר סידורים טופולוגיים אפשריים . מיון טופולוגי נוסף עבור הגרף הנתון הוא : BADEC וקיימות אפשרויות נוספות . להלן אלגוריתם למיון טופולוגי . באלגוריתם הזה נשתמש במבנה הנתונים תור , ( queue ) שבו נשמור את הקדקודים שאין להם קדקודים מקדימים . אלגוריתם למיון טופולוגי : . 1 איתור קדקודי הגרף שאין להם מקדימים וצירופם לתור . ( Q ) . 2 כל עוד התור ( Q ) אינו ריק , יש לבצע את הצעדים שלהלן : 2 . 1 הוצא איבר מראש התור וצרף אותו לרשימה המייצגת סדר טופולוגי . 2 . 2 מחק בגרף את הקדקוד , שיצא זה עתה מהתור , ובנוסף , מחק את כל הקשתות היוצאות מהקדקוד הזה .
|
|