גרף לעומת עץ
גרף ועץ משמשים במבני נתונים. בהחלט יש כמה הבדלים בין גרף לעץ. קבוצה של קודקודים בעלי יחס בינארי נקראת גרף ואילו עץ הוא מבנה נתונים שיש לו קבוצה של צמתים המקושרים זה לזה.
גרף
גרף הוא קבוצה של פריטים המחוברים בקצוות וכל פריט ידוע כצומת או קודקוד. במילים אחרות, ניתן להגדיר גרף כקבוצת הקודקודים ויש יחס בינארי בין הקודקודים הללו.
ביישום של גרף, הצמתים מיושמים כאובייקטים או מבנים. ניתן לייצג את הקצוות בדרכים שונות.אחת הדרכים היא שניתן לשייך כל צומת למערך קצוות אירועים. אם המידע אמור להיות מאוחסן בצמתים ולא בקצוות אז המערכים פועלים כמצביעים לצמתים וגם מייצגים קצוות. אחד היתרונות של גישה זו הוא שניתן להוסיף צמתים נוספים לגרף. ניתן לחבר צמתים קיימים על ידי הוספת אלמנטים למערכים. אבל יש חסרון אחד מכיוון שנדרש זמן כדי לקבוע אם יש קצה בין הצמתים.
דרך אחרת לעשות זאת היא לשמור על מערך דו מימדי או מטריצה M שיש להם ערכים בוליאניים. קיומו של קצה מצומת i עד j מצוין על ידי הערך Mij. אחד היתרונות של שיטה זו הוא לגלות אם יש איזשהו קצה בין שני צמתים.
עץ
עץ הוא גם מבנה נתונים המשמש במדעי המחשב. הוא דומה למבנה העץ ויש לו קבוצה של צמתים המקושרים זה לזה.
צומת של עץ עשוי להכיל תנאי או ערך.זה יכול להיות גם עץ משלו או שהוא יכול לייצג מבנה נתונים נפרד. אפס צמתים או יותר קיימים במבנה נתוני עץ. אם לצומת יש ילד אז הוא נקרא צומת אב של אותו ילד. יכול להיות הורה אחד לכל היותר של צומת. הנתיב הארוך ביותר כלפי מטה מהצומת לעלה הוא גובה הצומת. עומק הצומת מיוצג על ידי הנתיב לשורש שלו.
בעץ, הצומת העליון נקרא צומת שורש. לצומת השורש אין הורים מכיוון שהוא העליון ביותר. מהצומת הזה, כל פעולות העץ מתחילות. באמצעות קישורים או קצוות, ניתן להגיע לצמתים אחרים מצומת השורש. הצמתים ברמה התחתונה ביותר נקראים צמתים עלים ואין להם ילדים. הצומת שיש לו מספר צמתים צאצאים נקרא צומת פנימי או צומת פנימי.
הבדל בין גרף לעץ:
• ניתן לתאר עץ כמקרה מיוחד של גרף ללא לולאות ומעגלים עצמיים.
• אין לולאות בעץ ואילו לגרף יכולות להיות לולאות.
• ישנן שלוש קבוצות בגרף כלומר קצוות, קודקודים וקבוצה המייצגת את היחס ביניהם בעוד שעץ מורכב מצמתים המחוברים זה לזה. חיבורים אלה מכונים קצוות.
• בעץ ישנם כללים רבים המפרטים כיצד חיבורים של צמתים יכולים להתרחש בעוד שלגרף אין כללים המכתיבים את החיבור בין הצמתים.
