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

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

ממשק

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

# 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)

מימושים

רשימה מקושרת

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

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

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

1. תבנית:קוד בשורה - נחזיר את המערך תבנית:קוד בשורה. סיבוכיות הפעולה היא $\mathrm{\Theta }(|V|)$.
2. תבנית:קוד בשורה - נעבור בלולאה כפולה על כל חוליות הרשימות המקושרות. בלולאה החיצונית נעבור על המערך הראשי תבנית:קוד בשורה, ובלולאה הפנימית נעבור על חוליות הרשימה המשנית. סיבוכיות הפעולה היא $\mathrm{\Theta }(|V|+|E|)$.
3. תבנית:קוד בשורה - נמצא את הרשימה המשנית בתוך המערך הראשי תבנית:קוד בשורה בזמן $O(1)$, ונעבור על חוליות הרשימה בלולאה. הסיבוכיות היא $\mathrm{\Theta }(|A(v)|)$, כאשר $A(v)$ היא קבוצת השכנים של $v$.

מטריצה

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

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

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

1. תבנית:קוד בשורה - בדיוק כמימוש רשימה מקושרת, נחזיר את המערך תבנית:קוד בשורה. סיבוכיות הפעולה היא $\mathrm{\Theta }(|V|)$.
2. תבנית:קוד בשורה - נעבור בלולאה כפולה על כל האיברים הבוליאניים. בלולאה החיצונית נעבור על המערך הראשי תבנית:קוד בשורה, ובלולאה הפנימית נעבור על איברי המערך המשני. נחזיר זוגות המתאימים רק לאיברים שערכם תבנית:קוד בשורה. סיבוכיות הפעולה היא $\mathrm{\Theta }(|V{|}^2)$.
3. תבנית:קוד בשורה - נמצא את המערך המשני בתוך המערך הראשי תבנית:קוד בשורה בזמן $O(1)$, ונעבור על איבריו בלולאה. הסיבוכיות היא $\mathrm{\Theta }(|V|)$.

תכונות

לעתים רוצים לייחס תכונות כלשהן לצמתים, לקשתות, או לשניהם. לדוגמה, ייתכן שנרצה לייחס ערך בוליאני לצומת שמשמעו "נבדק". לחלופין, ייתכן שנרצה לייחס מספר כשלהו לקשת שמשמעו אורך הקשת. כדי ליחס תכונות לצמתים, נשתמש במערכים פשוטים. לדוגמה, קטע הקוד הבא מתאר את זאת שצומת 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

תבנית:שימו לב

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

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

תבנית:מבנה תבנית

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

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

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

תבנית:מבנה תבנית