דילוג לתוכן המרכזי

סיכום נושא בחירה: אלגוריתמים (גרפים)

מדעי המחשב לבגרות · 8 נושאים

כל מה שצריך לדעת בנושא בחירה: אלגוריתמים (גרפים): המושגים, הכללים, דרכי פתרון וקוד ב-Java וב-C# עם דוגמאות פתורות משאלוני הבגרות. לחזרה מהירה לפני הבחינה - הסיכום המקוצר או דף כללים.

גרף

גרף הוא דרך לתאר קשרים: נקודות (קודקודים, או צמתים) וקווים שמחברים ביניהן (קשתות). מפה של ערים וכבישים, מטעים ודרכים, מטלות שתלויות זו בזו - כולם גרפים. לכן אלגוריתם אחד על גרפים פותר הרבה בעיות שנראות שונות.
במדויק: גרף G = (V, E) הוא קבוצת קודקודים V וקבוצת קשתות E. בגרף לא מכוון הקשת u–v מחברת בשני הכיוונים; בגרף מכוון הקשת u→v הולכת מ-u ל-v בלבד; בגרף ממושקל לכל קשת יש משקל (אורך, מחיר). בסיכום, כמו בשאלונים, V ו-E הם גם מספר הקודקודים ומספר הקשתות: O(V + E). לפעמים השאלה קוראת למספר הקודקודים n.

אלגוריתם בנושא הבחירה

בנושא הבחירה אלגוריתמים לא כותבים תוכנית שלמה. מתארים אלגוריתם: מה עושים, באיזה סדר, למה זה נכון וכמה זה עולה.
במדויק: המיקוד של הפרק הוא "בתכנון אלגוריתמים ואינו כולל יישום (תכנות)". בבחינה: כותבים אלגוריתם בצעדים (רשימה ממוספרת או פסאודו-קוד), מריצים אלגוריתם על גרף נתון בטבלת מעקב, מנמקים סיבוכיות זמן ריצה כפונקציה של V ו-E, וקובעים אם טענה על גרפים נכונה (נימוק לכל גרף) או לא נכונה (דוגמה נגדית).

1. היכרות עם גרפים: מושגים, דרגות, קשירות וגרף דו-צדדי

דרגה, מסלול וקשירות

לפני כל אלגוריתם צריך לדבר באותה שפה: כמה קשתות נוגעות בקודקוד, איך הולכים מקודקוד לקודקוד, ואילו קודקודים "מחוברים" זה לזה. רוב הטענות בשאלות נכון / לא נכון בנויות מהמושגים האלה.
במדויק: דרגה של קודקוד = מספר הקשתות שנוגעות בו. בגרף מכוון: דרגת כניסה (קשתות שנכנסות) ודרגת יציאה (קשתות שיוצאות). מסלול = סדרת קודקודים שכל שניים עוקבים בה מחוברים בקשת; מסלול פשוט = בלי קודקוד שחוזר; מעגל = מסלול שחוזר לקודקוד שהתחיל בו. רכיב קשיר (רכיב קשירות) = קבוצה מקסימלית של קודקודים שיש מסלול בין כל שניים מהם; גרף קשיר = גרף עם רכיב קשיר אחד.

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

מושגים שחוזרים בשאלות

מושגמה זהדוגמה מהבגרות
גרף מלא (שלם)כל שני קודקודים מחוברים בקשת. ב-n קודקודים יש n(n−1)/2 קשתותG₇ בקיץ 2026: ארבעה קודקודים ו-6 קשתות
תת-גרףחלק מהקודקודים וחלק מהקשתות של הגרףעץ פורש הוא תת-גרף
גרף דו-צדדיאפשר לחלק את הקודקודים לשתי קבוצות כך שכל קשת מחברת קודקודים משתי קבוצות שונותבקיץ 2026: הצד A = {A1, A2, A3}, הצד B = {B1, B2, B3}
עץגרף קשיר בלי מעגלים"גרף-כמעט-עץ" בקיץ 2025: עץ ועוד קשת אחת
קשיר היטב (מכוון)לכל u ו-w יש מסלול מכוון מ-u ל-w וגם מ-w ל-uקיץ 2024: אם v מגיע לכולם וכולם מגיעים ל-v, הגרף קשיר היטב
רק"חרכיב קשירות חזקה: קבוצה מקסימלית של קודקודים שקשירה היטבקשת x→y וקשת y→x: x ו-y באותו רק"ח

סכום הדרגות, עצים וגרף דו-צדדי

•סכום הדרגות = 2·E: כל קשת נספרת פעמיים, פעם בכל קצה. בגרף מכוון: סכום דרגות הכניסה = סכום דרגות היציאה = E.
•עץ: גרף עם n קודקודים הוא עץ אם הוא קשיר ואין בו מעגלים. בעץ יש בדיוק n−1 קשתות. גרף קשיר עם n−1 קשתות הוא עץ.
•דו-צדדי ⇔ אין מעגל באורך אי-זוגי. משולש (מעגל באורך 3) אינו דו-צדדי. מעגל באורך 4, a–b–c–d–a, כן: {a, c} ו-{b, d}.

בדיקה בכוכב הסגור G₆ של קיץ 2026: 6 קודקודי מעגל בדרגה 3 ומרכז בדרגה 6. הסכום 18 + 6 = 24 = 2·12, ואכן יש 12 קשתות.

דרך הפתרון

טענה על גרפים: נכונה או לא נכונה

1.מסמנים כל מילה מודגשת: מכוון / לא מכוון, ממושקל, מלא, קשיר, "כל", "בהכרח", "ייתכן".
2."ייתכן" / "קיים": מספיקה דוגמה אחת שמקיימת את הטענה, והטענה נכונה.
3."כל" / "בהכרח": מנסים קודם להפריך בגרף קטן: משולש, מעגל באורך 4, כוכב, מסלול, גרף מלא, קודקוד מבודד.
4.דוגמה נגדית: במספר הקודקודים שהשאלה דורשת ("4 קודקודים לפחות"), עם רשימת קשתות (ומשקלות), ומראים במפורש איפה הטענה נכשלת.
5.נימוק לטענה נכונה: לכל גרף ולא על דוגמה: "יהיו u ו-w שני קודקודים כלשהם...".
שים לב

גרף עם n קודקודים ו-n−1 קשתות אינו בהכרח עץ: משולש a–b–c וקודקוד מבודד d - 4 קודקודים, 3 קשתות, ויש מעגל. המשפט הנכון: גרף קשיר עם n−1 קשתות הוא עץ.

שים לב

כשהשאלה דורשת דוגמה נגדית "מגרף שיש בו ארבעה קודקודים לפחות", משולש לבד לא מתקבל. מוסיפים קודקוד (מבודד, או מחובר בקשת אחת), ובודקים שהדוגמה עדיין מפריכה את הטענה.

דוגמה א - דרגות, קשתות ודו-צדדיות בכוכב סגור

גרף "כוכב סגור" Gₙ הוא גרף לא מכוון שמורכב ממעגל של n קודקודים (מ-1 עד n), "קודקודי המעגל", ומקודקוד נוסף 0, "קודקוד מרכז", שמחובר לכל אחד מקודקודי המעגל. בסך הכול יש n + 1 קודקודים, ו-n > 2.
לדוגמה, ב-G₆ הקשתות הן 1–2, 2–3, 3–4, 4–5, 5–6, 6–1 ("קשתות המעגל") ו-0–1, 0–2, 0–3, 0–4, 0–5, 0–6 ("קשתות מרכזיות").
(1) מה הן דרגות "קודקודי המעגל" בגרף, ומהי דרגת "קודקוד מרכז"? נמקו.
(2) כמה "קשתות מעגל" יש בגרף, וכמה "קשתות מרכזיות"? נמקו.
(3) האם הגרף הוא דו-צדדי? נמקו.

פתרון
1.דרגות: כל קודקוד מעגל i נוגע בשתי קשתות מעגל (אל הקודקוד שלפניו ואל הקודקוד שאחריו) ובקשת מרכזית אחת (אל 0): דרגה 3. קודקוד המרכז מחובר לכל אחד מ-n קודקודי המעגל: דרגה n.
2.קשתות: מעגל של n קודקודים מכיל n קשתות. המרכז מחובר ל-n קודקודים, ולכן יש n קשתות מרכזיות.
3.בדיקה בסכום הדרגות: n·3 + n = 4n = 2·(מספר הקשתות), ולכן יש 2n = n + n קשתות. ב-G₆: 12 קשתות.
4.דו-צדדי? הקודקודים 0, 1, 2 יוצרים מעגל באורך 3: 0–1, 1–2, 2–0. אם 0 בצד אחד, 1 ו-2 חייבים להיות שניהם בצד השני - אבל יש ביניהם קשת. מעגל באורך אי-זוגי, ולכן הגרף אינו דו-צדדי.
תשובה

(1) דרגת כל קודקוד מעגל 3, ודרגת קודקוד המרכז n. (2) n קשתות מעגל ו-n קשתות מרכזיות (2n בסך הכול). (3) לא: 0, 1, 2 יוצרים משולש - מעגל באורך אי-זוגי.

דוגמה ב - שתי טענות: n−1 קשתות ומחיקת קודקוד

ציינו בנוגע לכל טענה אם היא נכונה או לא נכונה. אם הטענה נכונה - נמקו מדוע, ואם היא אינה נכונה - הביאו דוגמה נגדית מגרף שיש בו 4 קודקודים לפחות.
(1) נתון גרף לא מכוון ובו n קודקודים. אם יש בגרף n−1 קשתות, בהכרח אין בו מעגלים.
(3) נתון גרף לא מכוון ובו n קודקודים ורכיב קשירות אחד. ייתכן שלאחר מחיקת קודקוד אחד (והקשתות שמחוברות אליו), יהיו בגרף n−1 רכיבי קשירות.

פתרון
1.טענה (1) - "בהכרח": מחפשים הפרכה. n−1 קשתות בלי מעגל מחייבות גרף קשיר, אז מנסים גרף לא קשיר: משולש ועוד קודקוד מבודד.
•קודקודים a, b, c, d; קשתות a–b, b–c, c–a.
•n = 4, יש 3 = n−1 קשתות, ו-a–b–c–a הוא מעגל. הטענה לא נכונה.
2.טענה (3) - "ייתכן": מספיק גרף אחד. אחרי המחיקה נשארים n−1 קודקודים, וכדי שיהיו n−1 רכיבים כל אחד מהם צריך להיות מבודד: כל הקשתות עוברות דרך הקודקוד שנמחק.
•גרף "כוכב": x–1, x–2, x–3. הגרף קשיר.
•מוחקים את x: נשארים 1, 2, 3 בלי קשתות - 3 = n−1 רכיבים. הטענה נכונה.
תשובה

(1) לא נכונה: משולש a–b–c וקודקוד מבודד d - 4 קודקודים, 3 קשתות, ויש מעגל. (3) נכונה: בגרף כוכב (מרכז שמחובר לכל n−1 הקודקודים האחרים) מחיקת המרכז משאירה n−1 קודקודים מבודדים, כלומר n−1 רכיבי קשירות.

2. ייצוג של גרפים: מטריצת שכנויות ורשימת שכנויות

ייצוג של גרף

כדי שאלגוריתם יעבוד על גרף, צריך לשמור אותו במבנה נתונים. יש שתי דרכים מקובלות: טבלה של קודקוד מול קודקוד, או רשימה של השכנים של כל קודקוד. הבחירה קובעת כמה עולה כל פעולה.
במדויק: מטריצת שכנויות (מטריצת סמיכויות) היא מערך דו-ממדי V×V: בתא [u][v] רשום 1 (או משקל הקשת) אם יש קשת מ-u ל-v, ו-0 (או ∞) אם אין. רשימת שכנויות (רשימת סמיכויות): לכל קודקוד u רשימה של השכנים שלו (בגרף ממושקל - שכן ומשקל). בגרף לא מכוון כל קשת u–v מופיעה פעמיים: v ברשימה של u, ו-u ברשימה של v.

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

מטריצה מול רשימות: סיבוכיות הפעולות

פעולהמטריצת שכנויותרשימות שכנויות
זיכרוןO(V²)O(V + E)
בדיקה אם יש קשת u–vO(1)O(דרגת u)
הוספת קשתO(1)O(1): הוספה לרשימה
מעבר על השכנים של uO(V): כל השורהO(דרגת u)
דרגה (או דרגת יציאה) של uO(V): סכום השורהO(דרגת u): אורך הרשימה
דרגת כניסה של u (מכוון)O(V): סכום העמודהO(V + E): מעבר על כל הרשימות
מעבר על כל הקשתותO(V²)O(V + E)

לכן כל אלגוריתם שעובר על השכנים של כל הקודקודים (BFS, DFS, מיון טופולוגי) עולה O(V + E) ברשימות ו-O(V²) במטריצה.

קריאת מטריצה וגרף הפוך

•לא מכוון: המטריצה סימטרית: [u][v] = [v][u].
•מכוון: שורה u = הקשתות היוצאות מ-u (סכום השורה = דרגת היציאה). עמודה v = הקשתות הנכנסות ל-v (סכום העמודה = דרגת הכניסה).
•גרף הפוך: אותם קודקודים, וכל קשת u→v הופכת ל-v→u. במטריצה: מחליפים שורות בעמודות, O(V²). ברשימות: לכל v ברשימה של u מוסיפים את u לרשימה של v בגרף החדש, O(V + E).
דרך הפתרון

בניית רשימת שכנויות מרשימת קשתות

1.פותחים רשימה ריקה לכל קודקוד.
2.עוברים על הקשתות. קשת לא מכוונת X–Y: מוסיפים את Y לרשימה של X וגם את X לרשימה של Y. קשת מכוונת X→Y: רק את Y לרשימה של X.
3.בודקים: בגרף לא מכוון סכום אורכי הרשימות (סכום הדרגות) = 2·E. בגרף מכוון הסכום = E.
שים לב

ספירה של כל האיברים בכל רשימות השכנויות של גרף לא מכוון נותנת 2·E, לא E. בשאלה על "גרף-כמעט-עץ" (n קשתות בדיוק) בודקים לכן אם הספירה שווה ל-2n.

שים לב

סדר השכנים ברשימה קובע את סדר הסריקה ואת טבלת המעקב. אם השאלה נותנת טבלת שכנים - עוברים על השכנים בסדר שבה. אם לא - כתבו באיזה סדר בחרתם (למשל אלפביתי) והיצמדו אליו.

דוגמה - השלמת טבלת שכנים בגרף דו-צדדי

נתון גרף לא מכוון דו-צדדי G = (A, B, E):

•צמתים בצד A: {A1, A2, A3}
•צמתים בצד B: {B1, B2, B3}
•קשתות: (A1–B1), (A1–B2), (A2–B1), (A2–B2), (A2–B3), (A3–B1), (A3–B2)

הצומת M מוגדר "שכן" של הצומת U אם יש קשת ביניהם. השלימו את טבלת השכנויות:

צומת UA1A2A3B1B2B3
השכנים MB1, B2A1, A2, A3
פתרון
1.עוברים על הקשתות: כל קשת (X–Y) מוסיפה את Y לשכני X ואת X לשכני Y.
2.A2: הקשתות A2–B1, A2–B2, A2–B3. A3: A3–B1, A3–B2.
3.B2: מופיע בקשתות עם A1, A2, A3. B3: רק עם A2.
צומת UA1A2A3B1B2B3
השכנים MB1, B2B1, B2, B3B1, B2A1, A2, A3A1, A2, A3A2
4.בדיקה: סכום הדרגות 2 + 3 + 2 + 3 + 3 + 1 = 14 = 2·7, פעמיים מספר הקשתות.
תשובה

A2: B1, B2, B3 · A3: B1, B2 · B2: A1, A2, A3 · B3: A2.

3. סריקה לרוחב (BFS) ומסלולים קצרים ממקור יחיד

סריקה לרוחב (BFS)

BFS מתפשט מהמקור בגלים: קודם כל השכנים של המקור, אחר כך השכנים שלהם, וכן הלאה. לכן הוא מגיע לכל קודקוד דרך מספר הקשתות הקטן ביותר - בדיוק מה שחקלאי צריך כדי לעבור דרך כמה שפחות מטעים.
במדויק: אורך מסלול = מספר הקשתות בו. BFS ממקור s עובר על הגרף בעזרת תור: כל קודקוד מסומן כשהוא מתגלה, ונכנס לתור פעם אחת בלבד. d[v] = אורך המסלול הקצר ביותר מ-s ל-v, ו-π[v] = הקודקוד שממנו התגלה v. הקשתות (π[v], v) יוצרות עץ פורש BFS ששורשו s, ובו המסלול מ-s לכל קודקוד הוא מסלול קצר ביותר. קודקוד שלא התגלה - אין אליו מסלול מ-s.

התור של BFS הוא אותו תור (Queue) מפרק מבני הנתונים, וסדר הביקור דומה לסריקה של עץ בינרי לפי רמות. בגרף מכוון הולכים רק בכיוון הקשתות.

BFS בצעדים וסיבוכיות

1.לכל קודקוד v: d[v] = ∞ (לא התגלה), π[v] = NIL.
2.d[s] = 0, ומכניסים את s לתור.
3.כל עוד התור לא ריק: מוציאים את u מראש התור. לכל שכן v של u שעוד לא התגלה: d[v] = d[u] + 1, π[v] = u, ומכניסים את v לתור.
4.בסוף d[v] הוא המרחק מ-s, והמסלול נקרא מהסוף: v, π[v], π[π[v]], ... עד s.

סיבוכיות ברשימות שכנויות: O(V + E). כל קודקוד נכנס לתור ויוצא ממנו פעם אחת (O(V)), ורשימת השכנים של כל קודקוד נסרקת פעם אחת (O(E) בסך הכול). במטריצת שכנויות: O(V²), כי המעבר על השכנים של כל קודקוד עולה O(V).

BFS כקוד, עם התור של מבני הנתונים

הגרף ברשימות שכנויות: adj[u] הוא מערך השכנים של u (הקודקודים 0 עד n-1). הפעולה מחזירה את מערך המרחקים, ו--1 לקודקוד שאין אליו מסלול.

public static int[] bfs(int[][] adj, int s)
{
    int n = adj.length;
    int[] dist = new int[n];
    for (int i = 0; i < n; i++)
    {
        dist[i] = -1;          // עוד לא התגלה
    }
    Queue<Integer> q = new Queue<Integer>();
    dist[s] = 0;
    q.insert(s);
    while (!q.isEmpty())
    {
        int u = q.remove();
        for (int i = 0; i < adj[u].length; i++)
        {
            int v = adj[u][i];
            if (dist[v] == -1)  // מסמנים כשהקודקוד נכנס לתור
            {
                dist[v] = dist[u] + 1;
                q.insert(v);
            }
        }
    }
    return dist;
}

על הגרף של קיץ 2024 (קשתות 1–5, 2–4, 2–8, 4–8, 3–7, 7–9, 7–0, 9–6, 6–0), מקודקוד 3, הפעולה מחזירה {2, -1, -1, 0, -1, -1, 3, 1, -1, 2}: הקודקודים 7 (מרחק 1), 0 ו-9 (מרחק 2) ו-6 (מרחק 3) ישיגים מ-3, וכל השאר לא.

דרך הפתרון

הרצת BFS בטבלת מעקב

1.עמודות: צעד, הקודקוד שהוצא מהתור, השכנים החדשים שסומנו, התור אחרי הצעד (מראשו לסופו), ו-d / π אם נדרש.
2.שורת אתחול: רק המקור מסומן, והתור [s].
3.בכל שורה מוציאים קודקוד אחד ובודקים את שכניו בסדר הקבוע. רק שכן שעוד לא סומן נכנס לתור.
4.סיום: כשהתור ריק, או כשמתקיים תנאי העצירה שבשאלה.

הגרף של קיץ 2024, מקודקוד 3 (שכנים בסדר עולה):

צעדהוצא מהתורשכנים חדשיםהתור אחרי הצעדמרחקים חדשים
אתחול-3[3]d[3] = 0
137[7]d[7] = 1
270, 9[0, 9]d[0] = d[9] = 2
306[9, 6]d[6] = 3
49- (6 ו-7 כבר סומנו)[6]-
56-[ ]-

BFS כקופסה שחורה

בעיהאיך פותריםסיבוכיות
כל הקודקודים שיש אליהם מסלול מ-sBFS מ-s, ומחזירים את כל מה שהתגלהO(V + E)
האם גרף לא מכוון קשירBFS מקודקוד כלשהו: קשיר אם ורק אם התגלו כל V הקודקודיםO(V + E)
רכיבי קשירותעוברים על הקודקודים; מכל קודקוד שעוד לא סומן מריצים BFS, עם אותו מערך סימון. כל BFS כזה מגלה רכיב אחדO(V + E)
האם גרף דו-צדדיBFS שצובע (מכל קודקוד שעוד לא סומן): שכן חדש מקבל את הצבע ההפוך לצבע של u. קשת בין שני קודקודים באותו צבע - הגרף אינו דו-צדדיO(V + E)
האם יש מעגל בגרף לא מכווןBFS (מכל קודקוד שעוד לא סומן) שמגיע לשכן שכבר סומן ואינו π[u] - יש מעגלO(V + E)
שים לב

מסמנים קודקוד כשהוא נכנס לתור, לא כשהוא יוצא ממנו. מי שמסמן ביציאה מכניס את אותו קודקוד לתור כמה פעמים.

שים לב

ברכיבי קשירות לא מאפסים את מערך הסימון בין הסריקות. איפוס גורם לסריקה חוזרת של אותו רכיב מכל אחד מהקודקודים שלו, והזמן גדל ל-O(V·(V + E)).

שים לב

BFS מוצא את המסלול עם מספר הקשתות הקטן ביותר. כשלקשתות יש משקלות שונים זה כבר לא המסלול הקל ביותר, וצריך את האלגוריתם של דייקסטרה.

דוגמה א - רכיב הקשירות הקטן ביותר

נתון גרף לא קשיר ולא מכוון G(V, E) שבו n קודקודים, מ-v₀ עד vₙ₋₁. "רכיב קשירות" הוא קבוצת קודקודים שבה בין כל שני קודקודים יש מסלול, ואין קשת שיוצאת מקודקוד בקבוצה לקודקוד שאינו בקבוצה. קודקוד בלי קשתות הוא רכיב משלו.
כתבו אלגוריתם המוצא ומחזיר את רכיב הקשירות הקטן ביותר (שבו מספר הקודקודים המינימלי). הניחו שיש רק רכיב אחד כזה. יש לכתוב אלגוריתם יעיל שאינו עובר על כל המסלולים האפשריים.
דוגמה: בגרף עם הקודקודים 0 עד 9 והקשתות 1–5, 2–4, 2–8, 4–8, 3–7, 7–9, 7–0, 9–6, 6–0, האלגוריתם יחזיר את הקודקודים 1, 5.

פתרון
1.רעיון: BFS מקודקוד s מגלה בדיוק את רכיב הקשירות של s. כל קודקוד שעוד לא סומן פותח רכיב חדש. מערך הסימון משותף לכל הסריקות, ולכן אף רכיב לא נסרק פעמיים.
2.האלגוריתם:
•מסמנים את כל הקודקודים "לא ביקרנו"; minSize ← ∞.
•לכל קודקוד s מ-v₀ עד vₙ₋₁: אם s לא סומן - מריצים ממנו BFS שמסמן ואוסף את הקודקודים שמתגלים לרשימה comp (כולל s).
•אם הגודל של comp קטן מ-minSize: שומרים את comp ואת גודלו.
•מחזירים את הרכיב ששמרנו.
3.סיבוכיות: הלולאה החיצונית עוברת n פעמים. בכל הסריקות יחד כל קודקוד נכנס לתור פעם אחת וכל רשימת שכנים נסרקת פעם אחת: O(V + E).
4.בדיקה על הדוגמה:
קודקוד שפותח רכיבהרכיב שנמצאגודלminSize אחרי
0{0, 6, 7, 9, 3}55
1{1, 5}22
2{2, 4, 8}32

שאר הקודקודים כבר סומנו. מוחזר {1, 5}.

תשובה

עוברים על הקודקודים v₀ עד vₙ₋₁; מכל קודקוד שעוד לא סומן מריצים BFS שאוסף את רכיב הקשירות שלו (מערך סימון משותף); שומרים את הרכיב עם מספר הקודקודים הקטן ביותר. זמן ריצה O(V + E). בדוגמה הרכיבים בגדלים 5, 2, 3, ומוחזר {1, 5}.

דוגמה ב - מעקב אחר האלגוריתם Path בגרף דו-צדדי

הגרף הדו-צדדי של קיץ 2026: הצד A = {A1, A2, A3}, הצד B = {B1, B2, B3}, והשכנים (בסדר הזה): A1: B1, B2 · A2: B1, B2, B3 · A3: B1, B2 · B1: A1, A2, A3 · B2: A1, A2, A3 · B3: A2.
נתונה רשימת קשתות L = {(A1–B1), (A2–B2)}. "צומת תפוס" מופיע ב-L (A1, A2, B1, B2), ו"צומת חופשי" לא מופיע ב-L (A3, B3).
האלגוריתם Path(G, L): מכניסים את A3 לתור q ומסמנים אותו ב-visited; המערך parent ריק. כל עוד q אינו ריק:

•מוציאים את הצומת שבראש התור, U.
•אם U בצד B והוא צומת חופשי: מחזירים את U, ההורה שלו, ההורה של ההורה וכן הלאה עד צומת בלי הורה, ומסיימים.
•אחרת, לכל שכן M של U שעוד לא ביקרנו בו: אם U בצד A והקשת (U–M) אינה ב-L, או U בצד B והקשת (U–M) נמצאת ב-L - מכניסים את M לתור, מסמנים את M ב-visited, ו-parent[M] = U.

אם התור ריק מחזירים null.
עקבו בטבלת מעקב אחרי ריצת Path (מצב התור, U, visited, parent), וכתבו את רשימת הצמתים שהאלגוריתם מחזיר.

פתרון
1.מה זה: BFS מ-A3 עם הגבלה: מצד A הולכים רק בקשת שאינה ב-L, ומצד B רק בקשת שב-L.
2.האיטרציות:
•U = A3 (צד A): B1 ו-B2 - הקשתות אינן ב-L, נכנסים. parent[B1] = parent[B2] = A3.
•U = B1 (תפוס): A1 - הקשת A1–B1 ב-L, נכנס, parent[A1] = B1. A2 - הקשת A2–B1 אינה ב-L. A3 - ביקרנו.
•U = B2 (תפוס): A2 - הקשת A2–B2 ב-L, נכנס, parent[A2] = B2.
•U = A1: B1, B2 כבר ביקרנו.
•U = A2: B3 - הקשת A2–B3 אינה ב-L, נכנס, parent[B3] = A2.
•U = B3: בצד B וחופשי - עוצרים.
התור אחרי האיטרציהUvisited (צמתים שסומנו)parent
[A3] (אתחול)-A3-
[B1, B2]A3A3, B1, B2B1←A3, B2←A3
[B2, A1]B1A3, B1, B2, A1B1←A3, B2←A3, A1←B1
[A1, A2]B2A3, B1, B2, A1, A2ועוד A2←B2
[A2]A1ללא שינויללא שינוי
[B3]A2כל השישהועוד B3←A2
[ ]B3כל השישהעצירה: B3 בצד B וחופשי
3.הרשימה: B3 ← parent[B3] = A2 ← parent[A2] = B2 ← parent[B2] = A3, ול-A3 אין הורה.
תשובה

הצמתים יוצאים מהתור בסדר A3, B1, B2, A1, A2, B3, וב-B3 (צד B, חופשי) האלגוריתם עוצר. parent בסוף: A1←B1, A2←B2, B1←A3, B2←A3, B3←A2. הרשימה שמוחזרת: B3, A2, B2, A3.

4. מסלולים קצרים במשקלות אי-שליליים: האלגוריתם של דייקסטרה

האלגוריתם של דייקסטרה

כשלכבישים יש אורכים שונים, מסלול עם מעט קשתות יכול להיות ארוך יותר ממסלול עם הרבה קשתות, ו-BFS כבר לא מתאים. דייקסטרה מוצא את המסלולים הקלים ביותר מהמקור לכל הקודקודים - בתנאי שאין משקלות שליליים.
במדויק: משקל מסלול = סכום משקלות הקשתות שבו; מסלול קצר (קל) ביותר = מסלול שמשקלו מינימלי. דייקסטרה מחזיק לכל קודקוד אומדן d[v] והורה π[v], וקבוצות P (קודקודים קבועים) ו-T (זמניים). בכל איטרציה הוא בוחר מ-T את הקודקוד עם d הקטן ביותר, קובע אותו, ומרפה את הקשתות שיוצאות ממנו. מתאים לגרף מכוון או לא מכוון, עם מעגלים או בלי, כשכל המשקלות אי-שליליים.

שתי אסטרטגיות: חמדנית - בכל שלב נבחר הצומת שקרוב יותר לצומת המקור; תכנות דינמי - המסלול הקצר לכל קודקוד נבנה מתתי-מסלולים קצרים שכבר חושבו. את T שומרים בתור עדיפויות, שמוציא את הקודקוד עם d המינימלי. תור רגיל לא מתאים: הוא מוציא לפי סדר הכניסה, לא לפי המרחק.

דייקסטרה בצעדים

1.d[s] = 0; לכל קודקוד אחר d[v] = ∞ ו-π[v] = NIL. P ריקה, T = כל הקודקודים.
2.כל עוד T לא ריקה: בוחרים מ-T את u עם d[u] מינימלי ומעבירים אותו ל-P. מעכשיו d[u] סופי.
3.הרפיה: לכל שכן v של u שנמצא ב-T: אם d[u] + w(u, v) < d[v], אז d[v] = d[u] + w(u, v) ו-π[v] = u.
4.בסוף d[v] הוא משקל המסלול הקל ביותר מ-s, והמסלול נקרא מהסוף לפי π. אם d[v] = ∞ - אין מסלול.

למה d[u] סופי כשבוחרים אותו: כל דרך אחרת ל-u עוברת דרך קודקוד זמני, ש-d שלו לפחות d[u], וקשתות אי-שליליות לא יכולות להוזיל אותה.

סיבוכיות דייקסטרה

מימושחיפוש המינימוםסך הכול
מערך d (כמו במטריצת שכנויות)O(V) בכל אחת מ-V האיטרציותO(V²)
תור עדיפויות יעיל, כקופסה שחורהO(log V) להוצאה ולעדכוןO((V + E)·log V)

הנימוק ל-O(V²): יש V איטרציות, ובכל אחת מחפשים מינימום במעבר על עד V קודקודים: V·O(V). כל קשת מורפית פעם אחת, כשהקודקוד שהיא יוצאת ממנו נבחר: O(E), ו-E ≤ V². סך הכול O(V²).

דרך הפתרון

הרצת דייקסטרה בטבלה

1.עמודות: הקודקוד שנבחר, ועמודה לכל קודקוד. בכל תא d ו-π, למשל 12 (A). אם השאלה מבקשת - גם P ו-T.
2.שורת אתחול: 0 במקור, ∞ בכל השאר.
3.בכל שורה: בוחרים מבין הזמניים את d המינימלי ומדגישים אותו. מרפים את השכנים הזמניים שלו: מעדכנים רק אם המשקל החדש קטן ממש.
4.מעתיקים לשורה את כל הערכים שלא השתנו.
5.בסוף: המסלול לפי π, מהיעד אחורה עד המקור, ואורכו = d של היעד.
6.עץ המסלולים הקצרים: הקשתות (π[v], v) לכל v ≠ s. בעץ V − 1 קשתות, ושורשו המקור.
שים לב

מעדכנים רק כשהמשקל החדש קטן ממש. בגרף של קיץ 2025, כשקובעים את C (13), הדרך ל-T דרך C היא 13 + 26 = 39 - לא קטנה מ-39 שכבר יש דרך A, ולכן π[T] נשאר A.

שים לב

הקשת הישירה אינה בהכרח הדרך הקלה. בגרף של קיץ 2024 הקשת S–F שוקלת 30, אבל S → G → F שוקל 2 + 20 = 22. לא קובעים d של קודקוד לפני שהוא נבחר כמינימום.

שים לב

דייקסטרה נכשל כשיש משקל שלילי, כי הוא קובע קודקוד ולא חוזר אליו. למשל S→A (4), S→B (2), A→B (-3): דייקסטרה קובע B עם 2, אבל S → A → B שוקל 1.

שים לב

כשכל המשקלות שווים, דייקסטרה ו-BFS מוצאים מסלולים באותו אורך. לכן הטענה "לא קיים גרף שבו דייקסטרה ו-BFS נותנים אותו מסלול" אינה נכונה: למשל y→A→B→x, כל קשת במשקל 1.

דוגמה א - דייקסטרה מ-S ל-T בגרף מכוון

לפניכם גרף ממושקל מכוון G₁. הקשתות והמשקלות: S→A (7), S→B (14), S→C (13), A→B (5), A→T (32), B→C (2), C→T (26), C→D (15), D→T (6).
איזה אלגוריתם מחזיר את המסלול הקצר (הקל) בין שני קודקודים בגרף ממושקל (אי-שלילי) כלשהו? מהי סיבוכיות זמן הריצה של האלגוריתם? נמקו.
הריצו את האלגוריתם על G₁ מצומת S לצומת T. בצעו מעקב שלב אחר שלב ורשמו את המסלול ואת אורכו (סכום משקליו).

פתרון
1.האלגוריתם: דייקסטרה - מתאים לכל גרף שמשקליו אי-שליליים.
2.סיבוכיות: V שליפות; במימוש עם מערך כל שליפה היא חיפוש מינימום ב-O(V), ובסך הכול O(V²). כל קשת מורפית פעם אחת: O(E) ≤ O(V²). סך הכול O(V²) (עם תור עדיפויות O((V + E)·log V)).
3.המעקב (בכל תא d (π); הקודקוד שנבחר מודגש):
שלבנבחרSABCDT
אתחול-0∞∞∞∞∞
1S07 (S)14 (S)13 (S)∞∞
2A712 (A)13 (S)∞39 (A)
3B1213 (S)∞39 (A)
4C1328 (C)39 (A)
5D2834 (D)
6T34
•שלב 2: B = 7 + 5 = 12 < 14 - עדכון; T = 7 + 32 = 39.
•שלב 3: C = 12 + 2 = 14, לא קטן מ-13 - אין עדכון.
•שלב 4: D = 13 + 15 = 28; T = 13 + 26 = 39, לא קטן ממש מ-39 - אין עדכון.
•שלב 5: T = 28 + 6 = 34 < 39 - עדכון.
4.המסלול לפי π מהסוף: T ← D ← C ← S.
תשובה

האלגוריתם של דייקסטרה, O(V²) (עם תור עדיפויות O((V + E)·log V)). המסלול S → C → D → T, ואורכו 13 + 15 + 6 = 34.

דוגמה ב - הכפלת כל המשקלות מול הוספה לכל משקל

עבור גרף G ממושקל כלשהו הרצנו את האלגוריתם שמוצא את המסלול הקל ביותר בין שני קודקודים, וקיבלנו מסלול.

•האם המסלול הקצר בין שני הקודקודים יישאר בהכרח זהה אם משקל כל אחת מהקשתות בגרף יוכפל ב-x (x > 1)? נמקו.
•האם הוא יישאר בהכרח זהה אם משקל כל אחת מהקשתות יגדל ב-x (x > 1)? נמקו.
פתרון
1.בודקים מה קורה למשקל של מסלול שלם, לא לקשת אחת.
2.הכפלה: מסלול עם קשתות w₁, ..., wₖ שוקל אחרי ההכפלה x·w₁ + ... + x·wₖ = x·(המשקל הקודם). כל המסלולים מוכפלים באותו מספר חיובי, והסדר ביניהם לא משתנה. המסלול נשאר הקל ביותר.
3.הוספה: מסלול עם k קשתות גדל ב-k·x. מסלול עם הרבה קשתות "נענש" יותר. דוגמה נגדית בגרף G₁ של קיץ 2025, x = 6:
•S → C → D → T (3 קשתות): 34 + 3·6 = 52.
•S → A → T (2 קשתות): 39 + 2·6 = 51.

עכשיו המסלול הקל הוא S → A → T.

תשובה

הכפלה ב-x: כן, המסלול נשאר הקל ביותר, כי משקל כל מסלול מוכפל ב-x. הוספה של x: לא בהכרח, כי מסלול עם k קשתות גדל ב-k·x. למשל ב-G₁ עם x = 6: S → C → D → T שוקל 52, ו-S → A → T שוקל 51.

5. מסלולים קצרים בגרף מכוון עם משקלות חיוביים ושליליים

משקלות שליליים והאלגוריתם של בלמן-פורד

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

למה דווקא גרף מכוון: בגרף לא מכוון, קשת שלילית u–v כבר יוצרת מעגל שלילי (הולכים u → v → u). בלמן-פורד הוא דוגמה לתכנות דינמי: אחרי k סבבים, d[v] אינו גדול מהמשקל של המסלול הקל ביותר מ-s ל-v שיש בו לכל היותר k קשתות.

בלמן-פורד בצעדים וסיבוכיות

1.d[s] = 0; לכל קודקוד אחר d[v] = ∞.
2.V − 1 סבבים. בכל סבב עוברים על כל הקשתות, בסדר קבוע, ומרפים כל קשת u→v: אם d[u] + w(u, v) < d[v], מעדכנים את d[v] ואת π[v] = u.
3.סבב בדיקה: עוברים עוד פעם על כל הקשתות. אם קשת כלשהי עוד מקטינה d - יש מעגל שלילי שישיג מ-s, ואין פתרון. אחרת d הם המרחקים.

למה V − 1 סבבים: מסלול קל ביותר בלי מעגלים עובר דרך לכל היותר V − 1 קשתות.
סיבוכיות ברשימות שכנויות: O(V·E) - V − 1 סבבים, ובכל סבב מעבר על E קשתות.

דרך הפתרון

הרצת בלמן-פורד בטבלה

1.כותבים את סדר הקשתות שבו עוברים בכל סבב, ולא משנים אותו.
2.עמודות: סבב, עמודה לכל קודקוד (d ו-π), ומה השתנה.
3.בתוך סבב מעדכנים מיד: קשת שבאה מאוחר יותר באותו סבב כבר משתמשת בערך החדש.
4.אחרי V − 1 סבבים עושים סבב בדיקה וכותבים את המסקנה.

גרף מכוון: S→A (4), S→B (2), A→B (-3), B→C (2). סדר הקשתות בכל סבב: B→C, A→B, S→A, S→B. V = 4, ולכן 3 סבבים.

סבבSABCמה השתנה
אתחול0∞∞∞-
104 (S)2 (S)∞S→A, S→B (ב-B→C ו-A→B עוד היה ∞)
204 (S)1 (A)4 (B)B→C: 2 + 2 = 4; אחריה A→B: 4 + (-3) = 1 < 2
304 (S)1 (A)3 (B)B→C: 1 + 2 = 3
בדיקה04 (S)1 (A)3 (B)אין שינוי - אין מעגל שלילי

דייקסטרה על אותו גרף היה קובע B = 2 ו-C = 4, ומפספס את S → A → B → C במשקל 3.

איזה אלגוריתם למסלולים קצרים ממקור יחיד

הגרףהאלגוריתםסיבוכיות
בלי משקלות (או כל המשקלות שווים)BFSO(V + E)
משקלות אי-שלילייםדייקסטרהO(V²), או O((V + E)·log V) עם תור עדיפויות
מכוון, משקלות חיוביים ושלילייםבלמן-פורדO(V·E)
מכוון חסר מעגלים (גמ"ל), כל משקלמיון טופולוגי והרפיה לפי הסדרO(V + E)
שים לב

מעגל שלילי מכשיל גם את בלמן-פורד: אין מסלול קל ביותר. אם לגרף S→A (4), S→B (2), A→B (-3), B→C (2) מוסיפים את C→A (-4), המעגל A → B → C → A שוקל -3 + 2 + (-4) = -5, ובסבב הבדיקה d עדיין יורדים. זה הסימן שאין פתרון.

שים לב

בלמן-פורד נכון גם בלי משקלות שליליים, אבל איטי מדייקסטרה. בשאלה על גרף "כלשהו" עם משקלות אי-שליליים התשובה המצופה היא דייקסטרה; מיון טופולוגי לא מתאים לגרף "כלשהו", כי ייתכן שיש בו מעגלים.

דוגמה - תת-מסלול של מסלול קצר ביותר

קבעו אם הטענה נכונה או לא נכונה. אם היא נכונה - נמקו מדוע, ואם היא לא נכונה - הביאו דוגמה נגדית.
אם בגרף G שאינו מכוון המסלול הקצר ביותר מהצומת sⱼ אל הצומת sₙ הוא S[sⱼ...sₘ...sₖ...sₙ], בהכרח התת-מסלול מ-sₘ ועד sₖ הוא המסלול הקצר ביותר מהצומת sₘ אל הצומת sₖ.

פתרון
1.רעיון - הוכחה בדרך השלילה ("גזור והדבק"): מחלקים את S לשלושה קטעים: P₁ מ-sⱼ ל-sₘ, P₂ מ-sₘ ל-sₖ, P₃ מ-sₖ ל-sₙ. אורך S הוא סכום שלושת האורכים.
2.נניח שיש מסלול P₂′ מ-sₘ ל-sₖ קצר מ-P₂.
3.מחליפים את P₂ ב-P₂′ ומקבלים דרך מ-sⱼ ל-sₙ שאורכה קטן מאורך S. אם קודקוד חוזר בה, משמיטים את המעגל שנוצר - בלי משקלות שליליים זה רק מקצר.
4.סתירה לכך ש-S הוא המסלול הקצר ביותר. לכן P₂ הוא מסלול קצר ביותר מ-sₘ ל-sₖ.
5.ובגרף מכוון עם משקלות שליליים? אותו נימוק עובד כל עוד אין מעגל שלילי: המעגל שמשמיטים בצעד 3 אינו שלילי, ולכן ההשמטה לא מאריכה את הדרך. אם יש מעגל שלילי, אין בכלל מסלול קל ביותר.

התכונה הזאת - מסלול קצר בנוי מתתי-מסלולים קצרים - היא הבסיס של התכנות הדינמי בדייקסטרה ובבלמן-פורד.

תשובה

נכונה. אילו היה מסלול קצר יותר מ-sₘ ל-sₖ, היינו מחליפים בו את הקטע sₘ...sₖ ומקבלים מסלול מ-sⱼ ל-sₙ קצר מ-S - בסתירה לכך ש-S הוא הקצר ביותר.

6. סריקה לעומק (DFS)

סריקה לעומק (DFS)

DFS הוא הדרך לצאת ממבוך: הולכים כמה שיותר עמוק, ומכל הצטלבות ממשיכים בשביל שעוד לא היינו בו. כשנתקעים, חוזרים צעד אחורה להצטלבות האחרונה ומנסים שביל אחר.
במדויק: DFS מקודקוד u מסמן את u, ולכל שכן v שעוד לא סומן קורא רקורסיבית ל-DFS מ-v (ו-π[v] = u). קודקוד הסתיים כשכל שכניו טופלו. הקשתות (π[v], v) יוצרות עץ פורש DFS. כדי לעבור על גרף לא קשיר מפעילים DFS מכל קודקוד שעוד לא סומן, ומתקבל יער. העץ תלוי בקודקוד ההתחלה ובסדר שבו בוחרים שכנים.

רקורסיה טבעית ל-DFS: "לחזור צעד אחורה" זה בדיוק לחזור מקריאה רקורסיבית. BFS עובד עם תור, ו-DFS עם רקורסיה.

DFS בצעדים וסיבוכיות

DFS-Visit(u):

1.מסמנים את u (התגלה).
2.לכל שכן v של u: אם v לא סומן - π[v] = u, וקוראים ל-DFS-Visit(v).
3.כשכל השכנים טופלו - u הסתיים, וחוזרים לקודקוד שקרא לו.

DFS(G): לכל קודקוד שעוד לא סומן קוראים ל-DFS-Visit.

סיבוכיות: O(V + E) ברשימות שכנויות - כל קודקוד מבוקר פעם אחת וכל רשימה נסרקת פעם אחת. במטריצת שכנויות O(V²), כי מעבר על השכנים של קודקוד עולה O(V).

DFS רקורסיבי כקוד

אותו ייצוג כמו ב-BFS: adj[u] הוא מערך השכנים של u. הפעולה מדפיסה את הקודקודים לפי סדר הגילוי.

public static void dfs(int[][] adj, int u, boolean[] visited)
{
    visited[u] = true;
    System.out.print(u + " ");   // u התגלה
    for (int i = 0; i < adj[u].length; i++)
    {
        int v = adj[u][i];
        if (!visited[v])
        {
            dfs(adj, v, visited);    // הולכים לעומק
        }
    }
    // כאן u הסתיים: חוזרים לקודקוד שקרא לו
}

על הגרף של קיץ 2024 (1–5, 2–4, 2–8, 4–8, 3–7, 7–9, 7–0, 9–6, 6–0), הקריאה מ-3 עם מערך סימון ריק מדפיסה 3 7 0 6 9. BFS מ-3 על אותו גרף מבקר בסדר 3, 7, 0, 9, 6.

BFS מול DFS

מה משוויםBFSDFS
מבנה עזרתוררקורסיה
סדר הביקורבשכבות, לפי המרחק מהמקורלעומק, וחזרה אחורה כשנתקעים
מסלולים קצרים (במספר קשתות)כןלא בהכרח
סיבוכיות ברשימותO(V + E)O(V + E)
העץ בגרף של קיץ 2024 מ-33–7, 7–0, 7–9, 0–63–7, 7–0, 0–6, 6–9 (שרשרת)
העץ בגרף מלא"כוכב": השורש מחובר לכל השאר"שרשרת": לכל צומת בן אחד לכל היותר

קשתות הגרף ביחס לעץ ה-DFS

•גרף לא מכוון: כל קשת היא קשת עץ או קשת אחורה - קשת מקודקוד לאב קדמון שלו בעץ. אין קשתות בין שני ענפים שונים: אילו הייתה קשת כזאת, ה-DFS היה עובר בה לפני שהוא חוזר מהענף הראשון.
•גרף מכוון: קשתות עץ, קשתות אחורה (לאב קדמון שעוד לא הסתיים), קשתות קדימה (לצאצא שכבר הסתיים) וקשתות חוצות (בין ענפים).
•מעגל: יש מעגל ⇔ יש קשת אחורה. בגרף לא מכוון: שכן שכבר סומן ואינו ההורה. בגרף מכוון: שכן שהתגלה ועוד לא הסתיים.

קשירות חזקה ורק"חים בעזרת DFS

•האם גרף מכוון קשיר היטב: סורקים (DFS או BFS) מקודקוד v בגרף G, ושוב מ-v בגרף ההפוך. אם בשתי הסריקות התגלו כל הקודקודים, אז כל קודקוד ישיג מ-v ו-v ישיג מכל קודקוד, ולכן בין כל שני קודקודים יש מסלול דרך v. O(V + E).
•רק"חים: (1) DFS על כל G, ורושמים את סדר הסיום. (2) בונים את הגרף ההפוך. (3) DFS על הגרף ההפוך, וכל פעם מתחילים מהקודקוד שסיים אחרון מבין אלה שעוד לא סומנו. כל עץ בסריקה השנייה הוא רק"ח. O(V + E).
•גרף על: מכווצים כל רק"ח לקודקוד אחד. הקשתות בין הרק"חים יוצרות גרף מכוון חסר מעגלים.
דרך הפתרון

האם עץ נתון יכול להתקבל מ-DFS

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

בגרף מלא כל עץ DFS הוא שרשרת: כל עוד יש קודקוד שלא התגלה, יש אליו קשת מהקודקוד הנוכחי, ולכן ה-DFS אף פעם לא חוזר אחורה לפני שביקר בכולם.

שים לב

DFS לא מוצא מרחקים קצרים, גם בגרף מכוון בלי מעגלים: בגרף s→a, a→b, b→c, s→c, סריקה שהולכת קודם ל-a מגיעה ל-c במסלול באורך 3, והמרחק הוא 1. רק בגרף לא מכוון בלי מעגלים (יער) יש בין שני קודקודים מסלול אחד, ואז העץ נותן אותו.

שים לב

אותו גרף נותן עצי DFS שונים לפי סדר השכנים. בגרף a→b, a→c, a→d, d→c: אם מ-a בוחרים b, c, d - העץ בגובה 1; אם בוחרים קודם את d - מתקבל a → d → c, והעץ בגובה 2.

דוגמה א - אילו עצים יכולים להתקבל מ-DFS מ-a

נתון גרף לא מכוון G ובו 5 קודקודים: a, b, c, d, s. לאחר הרצת DFS מקודקוד ההתחלה s התקבל העץ: s הוא השורש, ילדיו a ו-b, וילדיו של b הם d ו-c.
בנוגע לכל אחד משלושת העצים שלפניכם, קבעו אם ייתכן שהוא התקבל מהרצת DFS על אותו הגרף G מקודקוד ההתחלה a. נמקו.

•(i) קשתות העץ: a–b, b–d, b–c, c–s (השורש a, הבן שלו b).
•(ii) קשתות העץ: a–s, s–b, b–d, d–c.
•(iii) קשתות העץ: a–s, s–b, b–d, b–c.
פתרון
1.הקשתות שבוודאי בגרף (קשתות העץ הנתון): s–a, s–b, b–d, b–c.
2.קשתות אפשריות נוספות: רק בין קודקוד לאב קדמון שלו - s–d, s–c.
3.קשתות שאינן בגרף: a–b, a–c, a–d (a ו-b בענפים שונים של s), ו-c–d (אחים). לכן השכן היחיד של a הוא s.
עץקביעהנימוק
(i)לא ייתכןהבן של a הוא b, כלומר נדרשת קשת a–b, והיא לא בגרף
(ii)לא ייתכןנדרשת קשת d–c, אבל d ו-c אחים בעץ הנתון, ולכן אין ביניהם קשת
(iii)ייתכןכל הקשתות בגרף, ויש סדר סריקה שנותן אותו
4.הסריקה שנותנת את (iii): a → s (השכן היחיד) → b (בוחרים את b קודם) → d, חוזרים ל-b → c, חוזרים. כל הקודקודים התגלו.
תשובה

(i) לא ייתכן - אין קשת a–b ב-G. (ii) לא ייתכן - אין קשת d–c ב-G. (iii) ייתכן - a → s → b, ומ-b אל d ואל c.

דוגמה ב - גרף שבו כל סריקת DFS היא שרשרת

עץ פורש "שרשרת" הוא עץ שבו לכל צומת יש בן אחד לכל היותר. גרף קשיר לא מכוון מכונה "DFS שרשרתי" אם בכל סריקת DFS מכל צומת בגרף מתקבל עץ פורש "שרשרת".
קבעו בנוגע לכל גרף אם הוא "DFS שרשרתי". אם לא - הציגו סריקת DFS שבה מתקבל עץ שאינו "שרשרת".

•G₂: A–B, B–C, C–D, D–E
•G₃: A–B, B–C, C–D, D–E, E–F, F–A
•G₅: A–B, B–C, A–D, B–D
•G₇: כל 6 הקשתות בין A, B, C, D
פתרון
1.רעיון: העץ אינו שרשרת אם ה-DFS חוזר אחורה לצומת שכבר יש לו בן, ויוצא ממנו לבן נוסף. מחפשים צומת שאפשר "להיתקע" אחרי אחד מכיווניו.
2.G₂ (מסלול): מתחילים מצומת אמצעי. מ-B: B → A, נתקעים, חוזרים ל-B → C → D → E. ל-B שני בנים (A ו-C) - לא שרשרתי.
3.G₅: מ-A: A → B → C, נתקעים ב-C, חוזרים ל-B → D. ל-B שני בנים - לא שרשרתי.
4.G₃ (מעגל של 6): לכל צומת שני שכנים. אחרי הצעד הראשון, לכל צומת חדש יש בדיוק שכן אחד שלא ביקרנו בו - הבא במעגל - עד הצומת האחרון. הסריקה לא חוזרת אחורה: שרשרת מכל צומת ובכל בחירה.
5.G₇ (גרף מלא): לצומת הנוכחי יש קשת לכל צומת שלא ביקרנו בו, ולכן הסריקה לא חוזרת אחורה עד שכל הצמתים התגלו: שרשרת.
תשובה

G₃ (מעגל) ו-G₇ (גרף מלא) הם "DFS שרשרתיים". G₂ אינו: מ-B, B → A ואז B → C → D → E, ול-B שני בנים. G₅ אינו: מ-A, A → B → C ואז B → D, ול-B שני בנים.

7. מיון טופולוגי ומסלולים קצרים בגמ"ל

מיון טופולוגי וגמ"ל

יש מטלות שהסדר ביניהן חשוב: אוספים את הבגדים לפני שמכבסים, ומכבסים לפני שמקפלים. מיון טופולוגי הוא סדר ביצוע שמכבד את כל האילוצים האלה.
במדויק: גמ"ל (DAG) הוא גרף מכוון חסר מעגלים. מיון טופולוגי של גרף מכוון הוא סידור של כל הקודקודים בשורה, כך שלכל קשת u→v הקודקוד u מופיע לפני v. מיון כזה קיים רק בגמ"ל, ולאותו גרף יכולים להיות כמה מיונים טופולוגיים שונים. בגמ"ל אפשר גם למצוא מסלולים קלים ביותר ב-O(V + E), גם עם משקלות שליליים.

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

מיון טופולוגי בעזרת DFS

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

סיבוכיות: O(V + E) ברשימות שכנויות, O(V²) במטריצת שכנויות.

בגרף G₁ של קיץ 2025 (S→A (7), S→B (14), S→C (13), A→B (5), A→T (32), B→C (2), C→T (26), C→D (15), D→T (6)), DFS מ-S לפי סדר הקשתות: S → A → B → C → T, ואחר כך מ-C ל-D. הסדר שבו הקודקודים מסתיימים: T, D, C, B, A, S. המיון הטופולוגי: S, A, B, C, D, T.

מסלולים קצרים בגמ"ל

1.ממיינים את הגרף מיון טופולוגי.
2.d[s] = 0; לכל השאר d[v] = ∞.
3.עוברים על הקודקודים לפי סדר המיון, ומרפים את כל הקשתות שיוצאות מכל קודקוד.

למה זה נכון: כשמגיעים לקודקוד u, כל הקשתות שנכנסות אליו כבר הורפו, כי הן יוצאות מקודקודים שלפניו במיון. לכן d[u] כבר סופי. סיבוכיות: O(V + E). מתאים גם למשקלות שליליים: בגמ"ל אין מעגלים, ולכן אין מעגל שלילי.

על G₁ מ-S, לפי הסדר S, A, B, C, D, T (בכל תא d (π)):

מרפים אתSABCDT
אתחול0∞∞∞∞∞
S07 (S)14 (S)13 (S)∞∞
A07 (S)12 (A)13 (S)∞39 (A)
B07 (S)12 (A)13 (S)∞39 (A)
C07 (S)12 (A)13 (S)28 (C)39 (A)
D07 (S)12 (A)13 (S)28 (C)34 (D)
T07 (S)12 (A)13 (S)28 (C)34 (D)

אותה תוצאה כמו בדייקסטרה: S → C → D → T, במשקל 34.

דרך הפתרון

שאלה על גרף מכוון: האם אפשר למיין טופולוגית

1.מחפשים מעגל מכוון (ב-DFS: קשת אחורה).
2.יש מעגל - אין מיון טופולוגי. מראים את המעגל ומסבירים: כל קודקוד במעגל חייב להופיע אחרי הקודקוד שלפניו במעגל, ואף אחד מהם לא יכול להיות ראשון.
3.אין מעגל - מריצים את האלגוריתם וכותבים את הסדר.
4.בודקים: כל קשת u→v הולכת "קדימה" ברשימה.
שים לב

"מכוון וחסר מעגלים" לא אומר "מסלול יחיד": בגרף s→a, a→b, b→c, s→c יש שני מסלולים מ-s ל-c. לכן בגמ"ל לא מחפשים מסלול קצר ב-DFS, אלא במיון טופולוגי והרפיה.

שים לב

בגרף מכוון שיש בו מעגל (בלי לולאה עצמית) יש לפחות שני קודקודים שדרגת הכניסה שלהם גדולה מ-0: כל קודקוד על המעגל מקבל קשת מהקודקוד שלפניו. במעגל A→B→C→D→A לכל קודקוד דרגת כניסה 1, ואין קודקוד שיכול לפתוח את המיון. אם מתירים לולאה עצמית (קשת A→A), הטענה כבר לא נכונה: יש מעגל, ורק ל-A דרגת כניסה גדולה מ-0. לכן בבחינה עדיף לבחור טענות חד-משמעיות.

דוגמה - האם אפשר למיין טופולוגית כל גרף מכוון

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

פתרון
1."כל" - מנסים להפריך: מיון טופולוגי דורש שלכל קשת u→v, u יופיע לפני v. מעגל מכוון סותר את זה.
2.דוגמה נגדית עם 4 קודקודים: A→B, B→C, C→D, D→A.
3.למה אין מיון: A לפני B, B לפני C, C לפני D, ו-D לפני A - כלומר A לפני עצמו. בגרף לכל קודקוד דרגת כניסה 1, ואף קודקוד לא יכול להיות ראשון.
תשובה

לא נכונה. מיון טופולוגי אפשרי רק בגרף מכוון חסר מעגלים. דוגמה נגדית: A→B→C→D→A - כל קודקוד חייב להופיע אחרי הקודקוד שלפניו במעגל, וזו סתירה.

8. עץ פורש מינימלי

עץ פורש מינימלי (עפ"מ)

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

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

האלגוריתם של קרוסקל

1.ממיינים את הקשתות לפי משקל, מהקלה לכבדה.
2.מתחילים מ-V קודקודים בלי קשתות: כל קודקוד הוא רכיב לבד.
3.עוברים על הקשתות לפי הסדר. קשת שמחברת שני רכיבים שונים - מוסיפים לעץ ומאחדים את הרכיבים. קשת ששני הקצוות שלה כבר באותו רכיב סוגרת מעגל - מדלגים עליה.
4.עוצרים כשיש V − 1 קשתות.

חמדני: בכל שלב - הקשת הקלה ביותר שלא סוגרת מעגל.
סיבוכיות: המיון עולה O(E·log E). את הבדיקה "האם שני הקצוות באותו רכיב" ואת האיחוד עושים במבנה נתונים יעיל, כקופסה שחורה, ולכן הסך הכול O(E·log E).

דרך הפתרון

הרצת קרוסקל בטבלה

1.כותבים את הקשתות ממוינות לפי משקל.
2.שורה לכל קשת: נלקחת או לא, ולמה. קשת שנדחית - כותבים את המסלול שכבר מחבר את הקצוות שלה.
3.סופרים קשתות שנלקחו, ועוצרים ב-V − 1.
4.כותבים את קשתות העץ ואת המשקל הכולל.

הגרף של קיץ 2024 (8 קודקודים): S–B (15), S–G (2), S–F (30), B–C (4), B–G (10), C–D (10), C–G (7), C–H (13), D–H (6), D–I (15), F–G (20), F–H (13), G–H (8), H–I (8).

קשתמשקלנלקחת?למה
S–G2כן
B–C4כן
D–H6כן
C–G7כןמחברת את {B, C} עם {S, G}
G–H8כןמחברת את {D, H}
H–I8כן
C–D10לאכבר יש C–G–H–D
B–G10לאכבר יש B–C–G
C–H13לאכבר יש C–G–H
F–H13כןF עוד לא מחובר. זו הקשת השביעית = V − 1

העפ"מ: S–G, B–C, D–H, C–G, G–H, H–I, F–H. משקלו 2 + 4 + 6 + 7 + 8 + 8 + 13 = 48. סדר בין קשתות שוות משקל לא משנה את המשקל.

עפ"מ מול עץ מסלולים קצרים

מה משוויםעפ"מ (קרוסקל)עץ מסלולים קצרים (BFS / דייקסטרה)
מה ממוזערסכום המשקלות של כל העץהמרחק מהמקור לכל קודקוד, לכל אחד בנפרד
תלוי במקורלאכן
גרף מכווןלא מוגדרמוגדר
בגרף של קיץ 2024משקל 48. ב-F מגיעים מ-S דרך S–G–H–F, במשקל 23מ-S: S–G, G–B, G–C, G–F, G–H, H–D, H–I, משקל 61. d[F] = 22

תכונות של עפ"מ שנשאלות

טענהנכונה?למה / דוגמה
כל המשקלות שונים ⇒ עפ"מ יחיד (גרף לא מכוון וקשיר)כןשני עפ"מים שונים מאפשרים להחליף קשת ולקבל עץ קל יותר
לכל גרף ממושקל יש עפ"מ יחידלאמשולש a, b, c שכל קשתותיו במשקל 1: שלושה עפ"מים במשקל 2
הקשת הכבדה ביותר בגרף אינה בעפ"מלאa–b (1), b–c (1), c–a (1), c–d (10): c–d היא הדרך היחידה ל-d, וכל עץ פורש מכיל אותה
כשכל המשקלות שווים, כל עץ פורש (גם עץ BFS) הוא עפ"מכןלכל עץ פורש V − 1 קשתות, ולכן לכולם אותו משקל
משקלות שונים ⇒ מסלול קל יחידלאA–B (1), B–C (2), A–C (3): בין A ל-C שני מסלולים במשקל 3
שים לב

עפ"מ מוגדר לגרף לא מכוון וקשיר. בגרף מכוון, או בגרף לא קשיר, ייתכן שאין עץ פורש בכלל: למשל A→B (1), C→D (2) - המשקלות שונים ואין עפ"מ. לכן הטענה "בגרף מכוון שבו כל המשקלות שונים יש עפ"מ יחיד" לא נכונה כפי שנוסחה. בגרף לא מכוון וקשיר שבו כל המשקלות שונים יש עפ"מ יחיד.

שים לב

כשקשת כבדה נדחית בקרוסקל, הסיבה היא תמיד "שני הקצוות כבר מחוברים". לכן כדי להכריע אם קשת בעפ"מ, שואלים: האם אפשר לחבר את הקצוות שלה בקשתות קלות יותר?

דוגמה א - כמה עפ"מים יש בכוכב סגור

גרף "כוכב סגור" Gₙ: מעגל של n קודקודים (1 עד n, n > 2) וקודקוד מרכז 0 שמחובר לכל אחד מהם. לכל "קשתות המעגל" משקל 2, ולכל "הקשתות המרכזיות" (0–1, 0–2, ..., 0–n) משקל 1.
כמה עפ"מים (עצים פורשים מינימליים) שונים יש בגרף? נמקו.

פתרון
1.חסם תחתון: בגרף יש n + 1 קודקודים, ולכן לכל עץ פורש יש בדיוק n קשתות. כל קשת שוקלת לפחות 1, ולכן כל עץ פורש שוקל לפחות n.
2.עץ שמשיג את החסם: n הקשתות המרכזיות מחברות את 0 לכל הקודקודים ואין ביניהן מעגל - זה עץ פורש במשקל n. לכן הוא עפ"מ.
3.יחידות: כל עץ פורש אחר מכיל לפחות קשת מעגל אחת (משקל 2), ולכן משקלו לפחות n + 1.
4.בדיקה בקרוסקל: קודם נבחרות כל n הקשתות במשקל 1. הן כבר מחברות את כל הקודקודים, וכל קשת מעגל סוגרת מעגל.
תשובה

עפ"מ אחד בלבד: העץ שמורכב מכל n הקשתות המרכזיות, ומשקלו n. כל עץ פורש אחר מכיל קשת מעגל במשקל 2, ולכן משקלו לפחות n + 1.

דוגמה ב - האם הקשת הכבדה ביותר נכנסת לעפ"מ

ציינו אם הטענה נכונה או לא נכונה. אם הטענה נכונה - נמקו מדוע, ואם היא אינה נכונה - הביאו דוגמה נגדית מגרף שיש בו 4 קודקודים לפחות.
נתון גרף ממושקל (אי-שלילי) ובו מעגל אחד לפחות. העץ הפורש המינימלי של הגרף בהכרח אינו מכיל את הקשת עם המשקל הגבוה ביותר בגרף.

פתרון
1.מה נכון: על הקשת הכבדה ביותר על מעגל אפשר לוותר. אבל הקשת הכבדה ביותר בגרף לא חייבת להיות על מעגל.
2.רעיון להפרכה: הקשת הכבדה היא הדרך היחידה לקודקוד מסוים, ואז כל עץ פורש חייב להכיל אותה.
3.דוגמה נגדית:
קשתa–bb–cc–ac–d
משקל11110
4.בדיקה בקרוסקל: a–b נלקחת, b–c נלקחת, c–a נדחית (סוגרת את המעגל a–b–c), c–d נלקחת. העפ"מ a–b, b–c, c–d במשקל 12 - והוא מכיל את הקשת הכבדה ביותר.
תשובה

לא נכונה. דוגמה נגדית: משולש a, b, c עם משקלות 1, 1, 1 וקשת c–d במשקל 10. יש בגרף מעגל, אבל c–d היא הקשת היחידה שמגיעה ל-d, ולכן כל עץ פורש - ובפרט העפ"מ (a–b, b–c, c–d, משקל 12) - מכיל אותה.

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

GuyAI הוא המורה הפרטי המתקדם בישראל, המבוסס על מודלי הבינה המלאכותית החזקים בעולם בשילוב הידע הפדגוגי של GOOL. המערכת מספקת פתרונות לכל המקצועות ולכל הרמות - מיסודי ועד אקדמיה, וממתמטיקה ועד היסטוריה.