גרף
גרף הוא דרך לתאר קשרים: נקודות (קודקודים, או צמתים) וקווים שמחברים ביניהן (קשתות). מפה של ערים וכבישים, מטעים ודרכים, מטלות שתלויות זו בזו - כולם גרפים. לכן אלגוריתם אחד על גרפים פותר הרבה בעיות שנראות שונות.
במדויק: גרף 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 באותו רק"ח |
סכום הדרגות, עצים וגרף דו-צדדי
בדיקה בכוכב הסגור G₆ של קיץ 2026: 6 קודקודי מעגל בדרגה 3 ומרכז בדרגה 6. הסכום 18 + 6 = 24 = 2·12, ואכן יש 12 קשתות.
טענה על גרפים: נכונה או לא נכונה
גרף עם 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) דרגת כל קודקוד מעגל 3, ודרגת קודקוד המרכז n. (2) n קשתות מעגל ו-n קשתות מרכזיות (2n בסך הכול). (3) לא: 0, 1, 2 יוצרים משולש - מעגל באורך אי-זוגי.
דוגמה ב - שתי טענות: n−1 קשתות ומחיקת קודקוד
ציינו בנוגע לכל טענה אם היא נכונה או לא נכונה. אם הטענה נכונה - נמקו מדוע, ואם היא אינה נכונה - הביאו דוגמה נגדית מגרף שיש בו 4 קודקודים לפחות.
(1) נתון גרף לא מכוון ובו n קודקודים. אם יש בגרף n−1 קשתות, בהכרח אין בו מעגלים.
(3) נתון גרף לא מכוון ובו n קודקודים ורכיב קשירות אחד. ייתכן שלאחר מחיקת קודקוד אחד (והקשתות שמחוברות אליו), יהיו בגרף 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–v | O(1) | O(דרגת u) |
| הוספת קשת | O(1) | O(1): הוספה לרשימה |
| מעבר על השכנים של u | O(V): כל השורה | O(דרגת u) |
| דרגה (או דרגת יציאה) של u | O(V): סכום השורה | O(דרגת u): אורך הרשימה |
| דרגת כניסה של u (מכוון) | O(V): סכום העמודה | O(V + E): מעבר על כל הרשימות |
| מעבר על כל הקשתות | O(V²) | O(V + E) |
לכן כל אלגוריתם שעובר על השכנים של כל הקודקודים (BFS, DFS, מיון טופולוגי) עולה O(V + E) ברשימות ו-O(V²) במטריצה.
קריאת מטריצה וגרף הפוך
בניית רשימת שכנויות מרשימת קשתות
ספירה של כל האיברים בכל רשימות השכנויות של גרף לא מכוון נותנת 2·E, לא E. בשאלה על "גרף-כמעט-עץ" (n קשתות בדיוק) בודקים לכן אם הספירה שווה ל-2n.
סדר השכנים ברשימה קובע את סדר הסריקה ואת טבלת המעקב. אם השאלה נותנת טבלת שכנים - עוברים על השכנים בסדר שבה. אם לא - כתבו באיזה סדר בחרתם (למשל אלפביתי) והיצמדו אליו.
דוגמה - השלמת טבלת שכנים בגרף דו-צדדי
נתון גרף לא מכוון דו-צדדי G = (A, B, E):
הצומת M מוגדר "שכן" של הצומת U אם יש קשת ביניהם. השלימו את טבלת השכנויות:
| צומת U | A1 | A2 | A3 | B1 | B2 | B3 |
|---|---|---|---|---|---|---|
| השכנים M | B1, B2 | A1, A2, A3 |
| צומת U | A1 | A2 | A3 | B1 | B2 | B3 |
|---|---|---|---|---|---|---|
| השכנים M | B1, B2 | B1, B2, B3 | B1, B2 | A1, A2, A3 | A1, A2, A3 | A2 |
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 בצעדים וסיבוכיות
d[v] = ∞ (לא התגלה), π[v] = NIL.d[s] = 0, ומכניסים את s לתור.d[v] = d[u] + 1, π[v] = u, ומכניסים את v לתור.סיבוכיות ברשימות שכנויות: 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 בטבלת מעקב
הגרף של קיץ 2024, מקודקוד 3 (שכנים בסדר עולה):
| צעד | הוצא מהתור | שכנים חדשים | התור אחרי הצעד | מרחקים חדשים |
|---|---|---|---|---|
| אתחול | - | 3 | [3] | d[3] = 0 |
| 1 | 3 | 7 | [7] | d[7] = 1 |
| 2 | 7 | 0, 9 | [0, 9] | d[0] = d[9] = 2 |
| 3 | 0 | 6 | [9, 6] | d[6] = 3 |
| 4 | 9 | - (6 ו-7 כבר סומנו) | [6] | - |
| 5 | 6 | - | [ ] | - |
BFS כקופסה שחורה
| בעיה | איך פותרים | סיבוכיות |
|---|---|---|
| כל הקודקודים שיש אליהם מסלול מ-s | BFS מ-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.
| קודקוד שפותח רכיב | הרכיב שנמצא | גודל | minSize אחרי |
|---|---|---|---|
| 0 | {0, 6, 7, 9, 3} | 5 | 5 |
| 1 | {1, 5} | 2 | 2 |
| 2 | {2, 4, 8} | 3 | 2 |
שאר הקודקודים כבר סומנו. מוחזר {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 אינו ריק:
אם התור ריק מחזירים null.
עקבו בטבלת מעקב אחרי ריצת Path (מצב התור, U, visited, parent), וכתבו את רשימת הצמתים שהאלגוריתם מחזיר.
| התור אחרי האיטרציה | U | visited (צמתים שסומנו) | parent |
|---|---|---|---|
| [A3] (אתחול) | - | A3 | - |
| [B1, B2] | A3 | A3, B1, B2 | B1←A3, B2←A3 |
| [B2, A1] | B1 | A3, B1, B2, A1 | B1←A3, B2←A3, A1←B1 |
| [A1, A2] | B2 | A3, B1, B2, A1, A2 | ועוד A2←B2 |
| [A2] | A1 | ללא שינוי | ללא שינוי |
| [B3] | A2 | כל השישה | ועוד B3←A2 |
| [ ] | B3 | כל השישה | עצירה: B3 בצד B וחופשי |
הצמתים יוצאים מהתור בסדר 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 המינימלי. תור רגיל לא מתאים: הוא מוציא לפי סדר הכניסה, לא לפי המרחק.
דייקסטרה בצעדים
d[s] = 0; לכל קודקוד אחר d[v] = ∞ ו-π[v] = NIL. P ריקה, T = כל הקודקודים.d[u] + w(u, v) < d[v], אז d[v] = d[u] + w(u, v) ו-π[v] = u.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²).
הרצת דייקסטרה בטבלה
12 (A). אם השאלה מבקשת - גם P ו-T.מעדכנים רק כשהמשקל החדש קטן ממש. בגרף של קיץ 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. בצעו מעקב שלב אחר שלב ורשמו את המסלול ואת אורכו (סכום משקליו).
| שלב | נבחר | S | A | B | C | D | T |
|---|---|---|---|---|---|---|---|
| אתחול | - | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | S | 0 | 7 (S) | 14 (S) | 13 (S) | ∞ | ∞ |
| 2 | A | 7 | 12 (A) | 13 (S) | ∞ | 39 (A) | |
| 3 | B | 12 | 13 (S) | ∞ | 39 (A) | ||
| 4 | C | 13 | 28 (C) | 39 (A) | |||
| 5 | D | 28 | 34 (D) | ||||
| 6 | T | 34 |
האלגוריתם של דייקסטרה, O(V²) (עם תור עדיפויות O((V + E)·log V)). המסלול S → C → D → T, ואורכו 13 + 15 + 6 = 34.
דוגמה ב - הכפלת כל המשקלות מול הוספה לכל משקל
עבור גרף G ממושקל כלשהו הרצנו את האלגוריתם שמוצא את המסלול הקל ביותר בין שני קודקודים, וקיבלנו מסלול.
עכשיו המסלול הקל הוא 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 קשתות.
בלמן-פורד בצעדים וסיבוכיות
d[s] = 0; לכל קודקוד אחר d[v] = ∞.d[u] + w(u, v) < d[v], מעדכנים את d[v] ואת π[v] = u.למה V − 1 סבבים: מסלול קל ביותר בלי מעגלים עובר דרך לכל היותר V − 1 קשתות.
סיבוכיות ברשימות שכנויות: O(V·E) - V − 1 סבבים, ובכל סבב מעבר על E קשתות.
הרצת בלמן-פורד בטבלה
גרף מכוון: S→A (4), S→B (2), A→B (-3), B→C (2). סדר הקשתות בכל סבב: B→C, A→B, S→A, S→B. V = 4, ולכן 3 סבבים.
| סבב | S | A | B | C | מה השתנה |
|---|---|---|---|---|---|
| אתחול | 0 | ∞ | ∞ | ∞ | - |
| 1 | 0 | 4 (S) | 2 (S) | ∞ | S→A, S→B (ב-B→C ו-A→B עוד היה ∞) |
| 2 | 0 | 4 (S) | 1 (A) | 4 (B) | B→C: 2 + 2 = 4; אחריה A→B: 4 + (-3) = 1 < 2 |
| 3 | 0 | 4 (S) | 1 (A) | 3 (B) | B→C: 1 + 2 = 3 |
| בדיקה | 0 | 4 (S) | 1 (A) | 3 (B) | אין שינוי - אין מעגל שלילי |
דייקסטרה על אותו גרף היה קובע B = 2 ו-C = 4, ומפספס את S → A → B → C במשקל 3.
איזה אלגוריתם למסלולים קצרים ממקור יחיד
| הגרף | האלגוריתם | סיבוכיות |
|---|---|---|
| בלי משקלות (או כל המשקלות שווים) | BFS | O(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ₖ.
התכונה הזאת - מסלול קצר בנוי מתתי-מסלולים קצרים - היא הבסיס של התכנות הדינמי בדייקסטרה ובבלמן-פורד.
נכונה. אילו היה מסלול קצר יותר מ-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):
π[v] = u, וקוראים ל-DFS-Visit(v).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
| מה משווים | BFS | DFS |
|---|---|---|
| מבנה עזר | תור | רקורסיה |
| סדר הביקור | בשכבות, לפי המרחק מהמקור | לעומק, וחזרה אחורה כשנתקעים |
| מסלולים קצרים (במספר קשתות) | כן | לא בהכרח |
| סיבוכיות ברשימות | O(V + E) | O(V + E) |
| העץ בגרף של קיץ 2024 מ-3 | 3–7, 7–0, 7–9, 0–6 | 3–7, 7–0, 0–6, 6–9 (שרשרת) |
| העץ בגרף מלא | "כוכב": השורש מחובר לכל השאר | "שרשרת": לכל צומת בן אחד לכל היותר |
קשתות הגרף ביחס לעץ ה-DFS
קשירות חזקה ורק"חים בעזרת DFS
האם עץ נתון יכול להתקבל מ-DFS
בגרף מלא כל עץ 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, כלומר נדרשת קשת a–b, והיא לא בגרף |
| (ii) | לא ייתכן | נדרשת קשת d–c, אבל d ו-c אחים בעץ הנתון, ולכן אין ביניהם קשת |
| (iii) | ייתכן | כל הקשתות בגרף, ויש סדר סריקה שנותן אותו |
(i) לא ייתכן - אין קשת a–b ב-G. (ii) לא ייתכן - אין קשת d–c ב-G. (iii) ייתכן - a → s → b, ומ-b אל d ואל c.
דוגמה ב - גרף שבו כל סריקת DFS היא שרשרת
עץ פורש "שרשרת" הוא עץ שבו לכל צומת יש בן אחד לכל היותר. גרף קשיר לא מכוון מכונה "DFS שרשרתי" אם בכל סריקת DFS מכל צומת בגרף מתקבל עץ פורש "שרשרת".
קבעו בנוגע לכל גרף אם הוא "DFS שרשרתי". אם לא - הציגו סריקת DFS שבה מתקבל עץ שאינו "שרשרת".
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
סיבוכיות: 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.
מסלולים קצרים בגמ"ל
d[s] = 0; לכל השאר d[v] = ∞.למה זה נכון: כשמגיעים לקודקוד u, כל הקשתות שנכנסות אליו כבר הורפו, כי הן יוצאות מקודקודים שלפניו במיון. לכן d[u] כבר סופי. סיבוכיות: O(V + E). מתאים גם למשקלות שליליים: בגמ"ל אין מעגלים, ולכן אין מעגל שלילי.
על G₁ מ-S, לפי הסדר S, A, B, C, D, T (בכל תא d (π)):
| מרפים את | S | A | B | C | D | T |
|---|---|---|---|---|---|---|
| אתחול | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| S | 0 | 7 (S) | 14 (S) | 13 (S) | ∞ | ∞ |
| A | 0 | 7 (S) | 12 (A) | 13 (S) | ∞ | 39 (A) |
| B | 0 | 7 (S) | 12 (A) | 13 (S) | ∞ | 39 (A) |
| C | 0 | 7 (S) | 12 (A) | 13 (S) | 28 (C) | 39 (A) |
| D | 0 | 7 (S) | 12 (A) | 13 (S) | 28 (C) | 34 (D) |
| T | 0 | 7 (S) | 12 (A) | 13 (S) | 28 (C) | 34 (D) |
אותה תוצאה כמו בדייקסטרה: S → C → D → T, במשקל 34.
שאלה על גרף מכוון: האם אפשר למיין טופולוגית
"מכוון וחסר מעגלים" לא אומר "מסלול יחיד": בגרף s→a, a→b, b→c, s→c יש שני מסלולים מ-s ל-c. לכן בגמ"ל לא מחפשים מסלול קצר ב-DFS, אלא במיון טופולוגי והרפיה.
בגרף מכוון שיש בו מעגל (בלי לולאה עצמית) יש לפחות שני קודקודים שדרגת הכניסה שלהם גדולה מ-0: כל קודקוד על המעגל מקבל קשת מהקודקוד שלפניו. במעגל A→B→C→D→A לכל קודקוד דרגת כניסה 1, ואין קודקוד שיכול לפתוח את המיון. אם מתירים לולאה עצמית (קשת A→A), הטענה כבר לא נכונה: יש מעגל, ורק ל-A דרגת כניסה גדולה מ-0. לכן בבחינה עדיף לבחור טענות חד-משמעיות.
דוגמה - האם אפשר למיין טופולוגית כל גרף מכוון
ציינו אם הטענה נכונה או לא נכונה. אם הטענה נכונה - נמקו מדוע, ואם היא לא נכונה - הביאו דוגמה נגדית מגרף שיש בו ארבעה קודקודים לפחות.
אפשר לעשות מיון טופולוגי בעבור כל גרף מכוון.
לא נכונה. מיון טופולוגי אפשרי רק בגרף מכוון חסר מעגלים. דוגמה נגדית: A→B→C→D→A - כל קודקוד חייב להופיע אחרי הקודקוד שלפניו במעגל, וזו סתירה.
8. עץ פורש מינימלי
עץ פורש מינימלי (עפ"מ)
יש ערים ודרכים ביניהן, ורוצים לסלול חלק מהדרכים כך שאפשר יהיה להגיע מכל עיר לכל עיר, בכמה שפחות קילומטרים. לא צריך מסלול קצר מעיר מסוימת - צריך רשת זולה שמחברת את כולן.
במדויק: עץ פורש של גרף לא מכוון וקשיר הוא תת-גרף שמכיל את כל הקודקודים והוא עץ: V − 1 קשתות, קשיר ובלי מעגלים. עץ פורש מינימלי (עפ"מ) הוא עץ פורש שסכום משקלות הקשתות שלו מינימלי. עפ"מ מוגדר לגרף לא מכוון וקשיר, ומוצאים אותו באלגוריתם של קרוסקל.
קרוסקל הוא עוד אלגוריתם חמדני, כמו דייקסטרה: בכל שלב הוא לוקח את הקשת הזולה ביותר שעדיין מותרת, ולא חוזר בו. כאן הבחירה החמדנית מובילה תמיד לפתרון אופטימלי.
האלגוריתם של קרוסקל
חמדני: בכל שלב - הקשת הקלה ביותר שלא סוגרת מעגל.
סיבוכיות: המיון עולה O(E·log E). את הבדיקה "האם שני הקצוות באותו רכיב" ואת האיחוד עושים במבנה נתונים יעיל, כקופסה שחורה, ולכן הסך הכול O(E·log E).
הרצת קרוסקל בטבלה
הגרף של קיץ 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–G | 2 | כן | |
| B–C | 4 | כן | |
| D–H | 6 | כן | |
| C–G | 7 | כן | מחברת את {B, C} עם {S, G} |
| G–H | 8 | כן | מחברת את {D, H} |
| H–I | 8 | כן | |
| C–D | 10 | לא | כבר יש C–G–H–D |
| B–G | 10 | לא | כבר יש B–C–G |
| C–H | 13 | לא | כבר יש C–G–H |
| F–H | 13 | כן | 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.
כמה עפ"מים (עצים פורשים מינימליים) שונים יש בגרף? נמקו.
עפ"מ אחד בלבד: העץ שמורכב מכל n הקשתות המרכזיות, ומשקלו n. כל עץ פורש אחר מכיל קשת מעגל במשקל 2, ולכן משקלו לפחות n + 1.
דוגמה ב - האם הקשת הכבדה ביותר נכנסת לעפ"מ
ציינו אם הטענה נכונה או לא נכונה. אם הטענה נכונה - נמקו מדוע, ואם היא אינה נכונה - הביאו דוגמה נגדית מגרף שיש בו 4 קודקודים לפחות.
נתון גרף ממושקל (אי-שלילי) ובו מעגל אחד לפחות. העץ הפורש המינימלי של הגרף בהכרח אינו מכיל את הקשת עם המשקל הגבוה ביותר בגרף.
| קשת | a–b | b–c | c–a | c–d |
|---|---|---|---|---|
| משקל | 1 | 1 | 1 | 10 |
לא נכונה. דוגמה נגדית: משולש a, b, c עם משקלות 1, 1, 1 וקשת c–d במשקל 10. יש בגרף מעגל, אבל c–d היא הקשת היחידה שמגיעה ל-d, ולכן כל עץ פורש - ובפרט העפ"מ (a–b, b–c, c–d, משקל 12) - מכיל אותה.