ההבדל בין גרף לעץ

גרף לעומת עץ

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

גרף

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

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

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

עץ

עץ הוא גם מבנה נתונים המשמשים במדעי המחשב. זה דומה למבנה של העץ יש קבוצה של צמתים המקושרים זה לזה.

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

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

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