מדריך למבנה נתוני הגרף

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

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

מהו גרף ומה אתה צריך לדעת עליו?

מה זה גרף?

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

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

ה מדריך האקדמיה של חאן לייצוג גרפים הוא משאב מצוין ללמידה כיצד לייצג גרף.

ישנם סוגים רבים ושונים של גרפים. הבחנה נפוצה אחת היא בין מְכוּוָן ו לא מכוון גרפים; אלה מופיעים הרבה באתגרי קידוד ושימושים בחיים האמיתיים.

סוגי גרפים

1. גרף מכוון: גרף שבו לכל הקצוות יש כיוון, המכונה גם דיגרף.
2. גרף לא מכוון: גרף לא מכוון ידוע גם בתור גרף דו-כיווני. בגרפים לא מכוונים, כיוון הקצוות אינו משנה, והמעבר יכול ללכת לכל כיוון.
instagram viewer
3. גרף משוקלל: גרף משוקלל הוא גרף שלצמתים וקצוות שלו יש ערך משויך. ברוב המקרים, ערך זה מייצג את העלות של חקירת הצומת או הקצה הזה.
4. גרף סופי: גרף בעל מספר סופי של צמתים וקצוות.
5. גרף אינסופי: גרף בעל כמות אינסופית של צמתים וקצוות.
6. גרף טריוויאלי: גרף שיש לו רק צומת אחד וללא קצה.
7. גרף פשוט: כאשר רק קצה אחד מחבר כל זוג של צמתים של גרף, זה נקרא גרף פשוט.
8. גרף אפס: גרף ריק הוא גרף שאין לו קצוות המחברים את הצמתים שלו.
9. רב גרף: במולטיגרף, לפחות לזוג צמתים יש יותר מקצה אחד המחבר ביניהם. במולטיגרפים, אין לולאות עצמיות.
10. גרף שלם: גרף שלם הוא גרף שבו כל צומת מתחבר לכל צומת אחר בגרף. זה ידוע גם בתור א גרף מלא.
11. גרף פסאודו: גרף שיש לו לולאה עצמית מלבד קצוות גרפים אחרים נקרא פסאודו גרף.
12. גרף רגיל: גרף רגיל הוא גרף שבו לכל הצמתים יש מעלות שוות; כלומר לכל צומת יש אותו מספר של שכנים.
13. גרף מחובר: גרף מחובר הוא פשוט כל גרף שבו כל שני צמתים מתחברים; כלומר גרף עם נתיב אחד לפחות בין כל שני צמתים של הגרף.
14. גרף מנותק: גרף מנותק הוא ההיפך הישיר מגרף מחובר. בגרף מנותק, אין קצוות המקשרים בין הצמתים של הגרף, כגון ב-a ריק גרָף.
15. גרף מחזורי: גרף מחזורי הוא גרף המכיל לפחות מחזור גרף אחד (נתיב שמסתיים במקום בו התחיל).
16. גרף אציקלי: גרף אציקלי הוא גרף ללא מחזורים כלל. זה יכול להיות מכוון או לא מכוון.
17. תת-גרף: תת-גרף הוא גרף נגזר. זהו גרף שנוצר מצמתים וקצוות שהם תת-קבוצות של גרף אחר.

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

אלגוריתמי מעבר גרפים

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

1. Breadth-First Search (BFS): חיפוש רוחב ראשון הוא אלגוריתם חציית גרפים המבקר בצומת גרף וחוקר את שכניו לפני שהוא ממשיך לכל אחד מצמתי הצאצא שלו. למרות שאתה יכול להתחיל לחצות גרף מכל צומת שנבחר, ה צומת שורש היא בדרך כלל נקודת ההתחלה המועדפת.
2. חיפוש עומק ראשון (DFS): זהו אלגוריתם חציית הגרפים העיקרי השני. הוא מבקר בצומת גרף וחוקר את הצמתים הצאצאים או הענפים שלו לפני שהוא ממשיך לצומת הבא - כלומר, הולך קודם עמוק לפני שהוא מתרחב.

חיפוש רוחב ראשון הוא האלגוריתם המומלץ למצוא נתיבים בין שני צמתים במהירות האפשרית, במיוחד הנתיב הקצר ביותר.

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

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

היתרון של חיפוש רוחב-ראשון הוא שהוא שומר על קרבה לצומת הנוכחי עד כמה שניתן לפני מעבר לצומת הבא. זה ימצא את הקשר בין איקס ו י תוך זמן קצר מבלי לחקור את כל הארץ.

הבדל עיקרי נוסף בין שני האלגוריתמים הללו הוא באופן הטמעתם בקוד. חיפוש רוחב ראשון הוא אלגוריתם איטרטיבי ועושה שימוש בא תוֹר, בעוד שחיפוש עומק ראשון מיושם בדרך כלל כ-a אלגוריתם רקורסיבי שממנף את לַעֲרוֹם.

להלן כמה פסאודוקוד המדגים את היישום של שני האלגוריתמים.

חיפוש רוחב ראשון

bfs (גרף G, שורש GraphNode) {
תן q להיות חָדָשׁ תוֹר
// סמן את השורש כמבקר
 root.visited = נָכוֹן
// הוסף שורש לתור
ש.enqueue(שורש)
בזמן (q לא ריק) {
תן current be q.dequeue() // הסר אלמנט קדמי בתור
 עבור (שכנים n של זרם ב-G) {
אם (נ הואלֹא עדיין ביקר) {
// הוסף לתור - כדי שתוכל לחקור גם את השכנים שלו
ש.enqueue(נ)
 n.visited = נָכוֹן
 }
 }
 }
}

חיפוש עומק-ראשון

dfs (גרף G, שורש GraphNode) {
// מקרה יסוד
אם (השורש הוא ריק) לַחֲזוֹר
// סמן את השורש כמבקר
 root.visited = נָכוֹן
עבור (שכנים n של שורש ב-G)
אם (נ הואלֹא עדיין ביקר)
 dfs (G, n) // שיחה רקורסיבית
}

כמה אלגוריתמים אחרים למעבר גרפים נובעים מחיפושים של רוחב-ראשון ו-pep-first. הפופולריים שבהם הם:

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

שאלות נפוצות לראיון המבוססות על גרפים

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

אלו הן רק כמה מבעיות הראיונות הפופולריות הרבות המבוססות על גרפים. אתה יכול לנסות אותם LeetCode, HackerRank, או GeeksforGeeks.

הבנת מבני נתונים ואלגוריתמים של גרפים

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

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