גרף קשיר – הבדלי גרסאות

ב[[תורת הגרפים]], [[גרף מכוון]] נקרא '''קשיר היטב''' אם קיים מסלול מכל צומת שבו אל כל צומת אחרתאחר. עבור גרף מכוון כללי, ניתן תמיד לפרק את הגרף ל'''רכיבים קשירים היטב''' - תת גרפים מקסימליים של הגרף המקורי, שכל אחד מהם הוא גרף קשיר היטב בפני עצמו. פירוק זה מהווה חלוקה של הגרף למחלקות זרות - שני רכיבים שונים לא יכולים להכיל צומת משותף. יתר על כן, הגרף שכל צומת בו מייצג אחד מהרכיבים הקשירים היטב, ויש קשת מכוונת בין שני צמתים אם ורק אם יש קשת בין הרכיבים בגרף המקורי, הוא גרף מכוון חסר מעגלים (DAG).

#ראשית מפעילים את אלגוריתם חיפוש לעומק על <math>\ G</math>, ועבור כל צומת זוכרים את זמן היציאה ממנהממנו.

#כעת מפעילים את אלגוריתם חיפוש לעומק שנית, הפעם על <math>\ G^T</math>. מתחילים את ריצת האלגוריתם מהצומת בעלתבעל זמן היציאה הגבוה ביותר מבין אלו שחושבו בשלב 1, וכאשר האלגוריתם מסיים את הסריקה שהחלה מהצומת הזוהזה ועליו לבחור צומת חדשהחדש, בוחרים את הצומת בעלתבעל זמן היציאה הגבוה ביותר מבין אלו שנשארו, וכן הלאה.