|
|
עמוד:295
הקדקוד 3 לא הצטרף לתור Q כיוון שעדיין יש לו קדקוד מקדים ( רואים גם ש indegree [ 3 ] שונה מאפס . ( שלב 3 מסירים את קדקוד 2 מהתור . ניגשים למערך של רשימות לאינדקס 2 ומגלים שהקדקוד 3 הוא קדקוד סמוך לקדקוד . 2 לפיכך , יש לבטל את הקשת ( 2 , 3 ) ולהפחית את indegree [ 3 ] . 1-ב עתה נקבל : indegree = [ 0 , 0 , 0 , 0 ] 2 = { 3 } קדקוד 3 הצטרף לתור , כיוון שבשלב הזה אין לו קדקוד מקדים כי indegree [ 3 ] שווה אפס . שלנ אחרון מסירים את קדקוד 3 מהתור ; ניגשים למערך של רשימות לאינדקס 3 ומגלים שאין קדקודים סמוכים לקדקוד 3 ואין במי לטפל . עתה תמונת המצב היא indegree = [ 0 , 0 , 0 , 0 ] והתור { Q } ריק . כלומר המיון הסתיים . תוצאת המיון הטופולוגי היא ו 01 2 3 טענה ? סיבוביות זמן הריצה של האלגוריתם למיון טופולוגי היא ? 0 {\ V \ + \ E \)
|
|