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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

< מבני נתונים ואלגוריתמים - מחברת קורס | גרפים

מבני נתונים ואלגוריתמים - מחברת קורס

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

כדאי לדעת:

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

תוכן עניינים

1 מהו גרף?
2 ממשק
3 מימושים
- 3.1 רשימה מקושרת
- 3.2 מטריצה
4 תכונות
5 גרפים מכוונים ולא מכוונים

[עריכה] מהו גרף?

הגדרה:

גרף $\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 של רשימות-מקושרות משניות:

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

דוגמה:

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

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

V(G) - נחזיר את המערך [1, ..., Length(Vertexes)]. סיבוכיות הפעולה היא $\displaystyle \Theta(|V|)$ .
E(G) - נעבור בלולאה כפולה על כל חוליות הרשימות המקושרות. בלולאה החיצונית נעבור על המערך הראשי Vertexes, ובלולאה הפנימית נעבור על חוליות הרשימה המשנית. סיבוכיות הפעולה היא $\displaystyle \Theta(|V| + |E|)$ .
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

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

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

דוגמה:

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

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

V(G) - בדיוק כמימוש רשימה מקושרת, נחזיר את המערך [1, ..., Length(Vertexes)]. סיבוכיות הפעולה היא $\displaystyle \Theta(|V|)$ .
E(G) - נעבור בלולאה כפולה על כל האיברים הבוליאניים. בלולאה החיצונית נעבור על המערך הראשי Vertexs, ובלולאה הפנימית נעבור על איברי המערך המשני. נחזיר זוגות המתאימים רק לאיברים שערכם True. סיבוכיות הפעולה היא $\displaystyle \Theta(|V|^2)$ .
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 (1, 3) \notin E$ .

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

הגדרה:

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

דוגמה:

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

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

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

דוגמה:

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

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

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

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

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

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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

[עריכה] מהו גרף?

[עריכה] ממשק

[עריכה] מימושים

[עריכה] רשימה מקושרת

[עריכה] מטריצה

[עריכה] תכונות

[עריכה] גרפים מכוונים ולא מכוונים

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא