מהו גרף?

גרף הוא מבנה נתונים שמייצג קבוצה של דברים ואת הקשרים ביניהם. הדברים נקראים קודקודים (או צמתים), והקשרים נקראים קשתות.

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

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

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

הפעולות שנבנה במחלקה Graph שלנו הן:

1. addVertex: הוספת קודקוד חדש שעדיין אין לו קשתות.
2. addEdge: חיבור בין שני קודקודים.
3. hasEdge: בדיקה אם שני קודקודים מחוברים.
4. getNeighbors: קבלת רשימת השכנים של קודקוד.
5. removeEdge: ניתוק בין שני קודקודים.
6. size: ספירת מספר הקודקודים בגרף.

בואו נבנה מחלקה Graph!