גרפים בתכנות מוסברים בפשטות - Graphs¶
אם עץ הוא משפחתון מסודר עם הורה אחד לכל צומת, גרף הוא הרבה יותר דומה לרשת חברים אמיתית - מבולגנת, עם קשרים בכל הכיוונים, בלי סדר היררכי ברור. וזה בדיוק מה שהופך אותו לאחד המבנים השימושיים ביותר בתכנות.
מה זה בעצם גרף¶
גרף בנוי משני מרכיבים פשוטים: צמתים - vertices, שהם הפריטים עצמם, וקשתות - edges, שהם הקשרים ביניהם. זהו, זה כל ההגדרה. אין כללים על כמה קשרים מותר לכל צומת, אין הורה אחד יחיד, ואפשר שיהיו מעגלים - מצב שבו הולכים מקשר לקשר וחוזרים בסוף לאותה נקודה שהתחלתם ממנה.
תחשבו על פייסבוק. אתם צומת, החברים שלכם הם צמתים, וכל חברות היא קשת ביניכם. אין שום היררכיה - אתם לא "ההורה" של החברים שלכם, וחבר של חבר שלכם יכול בקלות להיות גם חבר שלכם ישירות, מה שיוצר מעגל. זה בדיוק הבדל אמיתי מעץ, שבו כזה מעגל פשוט לא יכול לקרות.
שני סוגים שכדאי להכיר¶
- גרף לא מכוון - Undirected Graph. הקשר סימטרי. אם אתם חברים בפייסבוק עם מישהו, הוא חבר שלכם באותה מידה.
- גרף מכוון - Directed Graph. הקשר חד-כיווני. באינסטגרם אתם יכולים לעקוב אחרי מישהו בלי שהוא עוקב אחריכם בחזרה - זה קשת שהולכת רק בכיוון אחד.
בנוסף, לפעמים לקשתות יש משקל - weight, מספר שמייצג "עלות" של המעבר. במפת כבישים, המשקל יכול להיות המרחק בין שתי צמתים, או זמן הנסיעה.
איפה גרפים נמצאים בעולם האמיתי - כמעט בכל מקום¶
זו בדיוק הסיבה שכדאי להכיר אותם, כי ברגע שרואים את הרעיון, מזהים אותו בכל מוצר טכנולוגי שמשתמשים בו:
- וויז וגוגל מפות - כבישים הם קשתות, צמתים הם צמתי דרכים, והמשקלים הם מרחק או זמן נסיעה. חיפוש המסלול המהיר ביותר הוא בעצם בעיית מציאת מסלול קצר בגרף.
- רשתות חברתיות - חברים, עוקבים, המלצות "אולי אתם מכירים" - כולם מבוססים על ניתוח מבנה הגרף.
- מנועי המלצה - נטפליקס ואמזון בונים גרף בין משתמשים ומוצרים כדי להמליץ לכם על דברים שמשתמשים דומים לכם אהבו.
- האינטרנט עצמו - כל אתר הוא צומת, כל קישור לאתר אחר הוא קשת. בעצם ככה גוגל בונה חלק מהדירוג שלו.
- מערכת ניתוב רשתות - איך חבילות מידע מוצאות את הדרך שלהן מהמחשב שלכם לשרת בצד השני של העולם.
שני אלגוריתמים שכדאי להכיר בשם, לפחות¶
לא צריך לדעת לממש את אלה בעל פה מהיום הראשון, אבל שווה להכיר את השמות והרעיון:
- BFS - Breadth First Search, חיפוש לרוחב. בודקים את כל השכנים הקרובים ביותר קודם, ורק אחר כך מתרחקים שכבה שכבה. מצוין למצוא את המסלול הקצר ביותר במספר קשרים, כמו "כמה לחיצות עוקב מפרידות ביני לבין מפורסם מסוים".
- DFS - Depth First Search, חיפוש לעומק. הולכים כמה שיותר רחוק בכיוון אחד לפני שחוזרים אחורה ומנסים כיוון אחר. מצוין לבדוק אם יש בכלל מסלול בין שתי נקודות, או לפתור מבוכים.
שניהם למעשה בנויים על מבנים שכבר הכרתם - BFS משתמש בתור, DFS משתמש במחסנית או ברקורסיה.
איך מתחילים ללמוד גרפים בלי להיבהל¶
גרפים נחשבים אחד הנושאים ה"מפחידים" יותר במבני נתונים, אבל רוב הפחד נובע מלנסות ללמוד את כל האלגוריתמים בבת אחת. תתחילו רק בלייצג גרף פשוט בקוד - למשל עם מילון שממפה כל צומת לרשימת השכנים שלו - ואז תממשו BFS פשוט על גרף קטן שאתם מציירים ביד. משם, הכל נבנה בהדרגה.
בקורס התכנות הבסיסי שלנו בונים את הבסיס הזה צעד אחר צעד, כדי שכשתגיעו לגרפים, כבר יהיו לכם כל הכלים כדי להבין אותם באמת.
תתחילו את קורס התכנות הבסיסי כאן
לסיכום¶
גרף הוא פשוט צמתים וקשרים ביניהם, בלי כללים נוקשים של היררכיה. הוא נמצא מאחורי כל מפה, כל רשת חברתית וכל מנוע המלצות שאתם משתמשים בו כל יום. ברגע שהרעיון הבסיסי נכנס לראש, קל הרבה יותר לזהות מתי בעיה בעצם מבקשת ממכם לחשוב עליה כגרף.
יש לכם שאלה בדרך? קפצו לדיסקורד שלנו.