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