מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/גרפים וייצוגיהם

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

כדאי לדעת: בספר הקורס, הפרק "Elementary Graph Algorithms" עוסק בנושאים אלה.

מהו גרף?

הגדרה: גרף $\displaystyle G=(V,E)$ הוא זוג של שתי קבוצות: $\displaystyle V$ ו-$\displaystyle E$. $\displaystyle V$ היא קבוצת הצמתים (vertexes), ו-$\displaystyle E$ היא קבוצת קשתות (edges), שכ"א ממנה היא מצומת כלשהו ב-$\displaystyle V$ לצומת כלשהו ב-$\displaystyle V$.

דוגמה: נניח שיש שש ערים: 1–6. קיימים כבישים מ-1 ל-3 ומ-1 ל-4, מ-3 ל-4, מ-4 ל-5, ומ-2 ל-6. התרשים הבא מראה גרף מתאים לכך: גרף (מכוון). בדוגמה זו, $\displaystyle V=\{1,...,6\}$, ו$\displaystyle E=\{(1,3),(1,4),(3,4),(4,5),(2,6)\}$.

שימו לב: אנו נתמקד במקרה שבו $\displaystyle V$, קבוצת הצמתים, היא קבוצת המספרים השלמים $\displaystyle \{1,...,n\}$, עבור $\displaystyle n$ כלשהו.

ממשק

הנה הממשק של גרף:

# Returns an array of the vertexes of a graph (G).
V(G)

# Returns an array of the edges of a graph (G).
E(G)

# Returns an array of the adjacent vertexes of a vertex (v) in a graph (G).
A(G, v)

דוגמה: נניח שG מתאר את הגרף בתרשים לעיל. אז: V(G) תחזיר את המערך [1, ..., 6]. E(G) תחזיר את המערך [(1, 3), (1, 4), (3, 4), (4, 5), (2, 6)], או איזשהו מערך שהוא פרמוטציה של המערך הנ"ל. A(G, 4) תחזיר את המערך [5]. A(G, 2) תחזיר את המערך [6]. A(G, 1) תחזיר את המערך [3, 4], או איזשהו מערך שהוא פרמוטציה של המערך הנ"ל.

מימושים

רשימה מקושרת

מימוש C++ boost::adjacency_list

במימוש זה מחזיקים מערך ראשי Vertexes של רשימות-מקושרות משניות:

1. במערך הראשי Vertexes יש איבר לכל צומת (איבר זה הוא כאמור רשימה מקושרת).
2. כל רשימה מקושרת מחזיקה את הצמתים שיש קשת מצומת המוצא אליהם.

דוגמה: להלן מבנה הנתונים במימוש זה המתאים לגרף שראינו לעיל: הגרף בייצוג רשימה מקושרת.

במימוש זה, כך נממש את שלוש הפעולות שראינו לעיל:

1. V(G) - נחזיר את המערך [1, ..., Length(Vertexes)]. סיבוכיות הפעולה היא $\displaystyle \Theta (|V|)$.
2. E(G) - נעבור בלולאה כפולה על כל חוליות הרשימות המקושרות. בלולאה החיצונית נעבור על המערך הראשי Vertexes, ובלולאה הפנימית נעבור על חוליות הרשימה המשנית. סיבוכיות הפעולה היא $\displaystyle \Theta (|V|+|E|)$.
3. A(G, v) - נמצא את הרשימה המשנית בתוך המערך הראשי Vertexes בזמן $\displaystyle O(1)$, ונעבור על חוליות הרשימה בלולאה. הסיבוכיות היא $\displaystyle \Theta (|A(v)|)$, כאשר $\displaystyle A(v)$ היא קבוצת השכנים של $\displaystyle v$.

שימו לב: אפשר לממש את הפעולה E(G) כך שזמנה יהיה רק $\displaystyle \Theta (|E|)$. בשיעורי הבית תתבקש לעשות זאת. מכאן ואילך נניח שבמימוש זה, סיבוכיות הפעולה היא $\displaystyle \Theta (|E|)$.

כדאי לדעת: בפועל כדאי להשתמש בייצוג זה עבור גרפים דלילים, כלומר גרפים בהם $\displaystyle |E|\ll |V|^{2}$.

מטריצה

מימוש C++ boost::adjacency_matrix

במימוש זה מחזיקים מערך ראשי של מערכים בוליאניים משניים:

1. במערך הראשי יש איבר לכל צומת (איבר זה הוא כאמור מערך בוליאני).
2. במערך המשני יש איבר בוליאני לכל צומת. איבר זה הוא True אמ"ם יש קשת מצומת המוצא לאיבר המתאים.

דוגמה: להלן מבנה הנתונים במימוש זה המתאים לגרף שראינו לעיל: הגרף בייצוג מטריצת שכנויות.

במימוש זה, כך נממש את שלוש הפעולות שראינו לעיל:

1. V(G) - בדיוק כמימוש רשימה מקושרת, נחזיר את המערך [1, ..., Length(Vertexes)]. סיבוכיות הפעולה היא $\displaystyle \Theta (|V|)$.
2. E(G) - נעבור בלולאה כפולה על כל האיברים הבוליאניים. בלולאה החיצונית נעבור על המערך הראשי Vertexs, ובלולאה הפנימית נעבור על איברי המערך המשני. נחזיר זוגות המתאימים רק לאיברים שערכם True. סיבוכיות הפעולה היא $\displaystyle \Theta (|V|^{2})$.
3. A(G, v) - נמצא את המערך המשני בתוך המערך הראשי Vertexs בזמן $\displaystyle O(1)$, ונעבור על איבריו בלולאה. הסיבוכיות היא $\displaystyle \Theta (|V|)$.

כדאי לדעת: בפועל כדאי להשתמש בייצוג זה עבור גרפים דחוסים, כלומר גרפים בהם $\displaystyle |E|\sim |V|^{2}$.

תכונות

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

1	n = Length(V(G))

2	Checked = Make-Array(n)

3	Checked[1] = True

4	for i in [2, ..., n]
5		Checked[i] = False

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

1	Distances = Make-Hash()

2	Distances[(1, 4)] = 13
3	Distances[(1, 3)] = 100
4	Distances[(2, 6)] = 2.3
5	Distances[(4, 5)] = 2.3
6	Distances[(3, 4)] = 888

שימו לב: בתחום הגרפים, נניח שייחוס תכונה לקשת כלשהי (כמו ב2-6 בדוגמה לעיל) היא בדיוק $\displaystyle O(1)$.

גרפים מכוונים ולא מכוונים

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

דוגמה: בגרף שראינו $\displaystyle (1,3)\in E$ אבל $\displaystyle (3,1)\notin E$.

לפעמים אין משמעות לכוון הקשתות, ונניח שלקשתות אין כוון.

הגדרה: נגיד שגרף הוא לא מכוון אמ"ם אין משמעות לכוון הקשתות.

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

כיצד נתייחס לגרף לא-מכוון?

1. בציור הגרף, לא נטרח לצייר לקשתות חיצים.
2. בשני הייצוגים השונים, נניח $\displaystyle (u,v)\in E\Rightarrow (v,u)\in E$ (כלומר, שהקשת מופיעה פעמיים).
3. אם לקשתות יש תכונות, נניח של$\displaystyle (u,v)$ ול$\displaystyle (v,u)$ יש אותן תכונות.

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

הפרק הקודם: גרפים

גרפים וייצוגיהם תרגילים

הפרק הבא: עצים