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

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

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





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



איפור של סרטון היום

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





מה זה גרף?

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

ייצוג חזותי של גרף

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



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

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



סוגי גרפים

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