Description

תאריך הגשה: 24.01 בשעה 23:00 (בזוגות)
יש לקרוא היטב לפני תחילת העבודה!
מבוא:
במעבדה הנוכחית נממש גרף.
תיאור:
גרף הוא מבנה נתונים המשמש לשמירת נתונים וקשרים בין זוגות נתונים. דוגמאות:- מפתכבישים בין ערים, מבנה של קשרי חברות ברשת חברתית וכו’, מבנה של ויקיפדיה
מבנה של גרף
גרף (𝐺 = (𝑉, 𝐸 מורכב מ:
● קבוצהV של קודקודים (Nodes אוVertices )
● קבוצהE של קשתות (Edges)
כל קשת מחברת בין שני קודקודים.
קשתe המחברת בין שני קודקודיםu ו-v תסומן בuv .
דוגמא:
V = {A,B,C,D,G,K,L}
E = { AB, AC, AL, BC, BD, BG, CD, CK, CL, GK, KL }

סוגים של גרפים
1. גרף לא מכוון הוא גרף עבורו אין משמעות לסדר הקודקודים בקשתות הגרף, כלומר
.uv=vu
2. גרף מכוון הוא גרף עבורו יש חשיבות לסדר הקודקודים בקשתות הגרף, כלומרuv שונה מ-vu
3. גרף הוא ממושקל אם לכל קשתe שלו מוצמד מספר(𝑤(𝑒 הנקרא משקל הקשת.מימושים אפשריים של גרפים:
בעזרת מטריצת סמיכויות- מתאימה במיוחד לגרפים לא דלילים (עם הרבה קשתות).
בעזרת רשימת סמיכויות/פגיעות- מתאימים במיוחד לגרפים דלילים.
במעבדה הנוכחית נממש גרף לא מכוון בעזרת רשימת סמיכויות.
.java.util.Graph אבל לא בjava.util מותר להשתמש ב
במבנה הזה,
– גרף מורכב מקבוצת צמתים
המלצה: ממשו בעזרת המחלקהjava.util.TreeMap .
– כל צומת מכיל את רשימת הקשתות הפוגעות בו
.java.util.LinkedList המלצה: ממשו בעזרת
– וכל קשת מצביעה לצמתים בשתי הקצוות שלה.
יש לכתוב מחלקה גנרית עם שני פרמטרים המתארת גרף (Graph). הפרמטר הראשוןמציין סוג הצמתים והשני את סוג הקשתות. לדוגמה המחלקה:
Graph<Person,Friendship>מתארת אנשים עם יחס חברות ביניהם. המחלקה
Graph<City,Double>יכולה לתאר ערים עם מרחקים ביניהם.
שימו לב: בנוסף לשתי המחלקות הנ”ל שמהוות את הפרמטרים של המחלקה, יש צורךבמחלקהEdge . כדאי ונכון לממש אותה כמחלקה פנימית שלGraph .
גרף יהיה ממושקל, אם המחלקה השניה המזוהה עם הקשתות של הגרף יורשת מjava.lang.Number או מממשת את הממשקWeighted .
תיאור השיטות נמצא בתוך הפרויקט.
אין לשנות את המחלקות שקיבלתם חוץ מהמחלקהGraph .
עבודה נעימה!!!
סדר העבודה ופרטים טכניים
● שליפת הפרויקטDS-Lab11-Graph מתוךGITHUB בקישור:
https://github.com/ykanizo/DSLab2022-2023Public
○ אם אין לכם גישה לפרויקט שהורדתם מGITHUB במעבדות הקודמות יש לבצע שליפהמחדש.
○ אם יש לכם גישה לפרויקט שהורדתם מGITHUB במעבדה הראשונה אז בצעו:
■ קליק על שם הפרויקט.
■ עכבר ימני
Team–>Pull ■ File–>Import->Git->Projects From Git->Existing Local Repository ■
פורמט קובץ ההגשה ובדיקתו:
בשםZIP פורמט : יש להגיש קובץ43_lab11_123456789_987654321.zip
(כמובן, יש להחליף את המספרים עם מספרי ת.ז. של המגישים).
על הקובץ להכיל את כל קבצי הJAVA שכתבתם כאשר הם נמצאים בתתי תיקיות בתוך התיקייה
il/ac/telhai/ds/על פי המבנה של הפרוייקט הנתון.
כלומר, השורש של קובץ ההגשה יכיל רק תיקייה בשםil , והוא יכיל את כל קבצי -java על פיהתבנית הנתונה בפרוייקט.
להמחשה תמונה של קובץ כזה שנפתח ב -WindowsExplorer

בדיקת קובץ ההגשה: בדקו את הקובץ שיצרתם בתוכנת הבדיקה בקישור:
https://csweb.telhai.ac.il/ראו סרטון הדגמה של השימוש בתוכנת הבדיקה.
חשוב!!!
בדיקת ההגשות תבוצע ברובה ע”י תוכנית הבדיקה האוטומטית הנ”ל. תוצאת הבדיקה תהייהבעיקרון זהה לתוצאת הבדיקה הנ”ל שאתם אמורים לערוך בעצמכם . כלומר, אם ביצעתם אתהבדיקה באתר החוג, לא תקבלו הפתעות בדיעבד. אחרת, ייתכן שתרגיל שעבדתם עליו קשהייפסל בגלל פורמט הגשה שגוי וכו.’ דבר שהיה ניתן לתקנו בקלות אם הייתם מבצעים את הבדיקה.
היות ואין הפתעות בדיעבד, לא תינתן אפשרות של תיקונים, הגשות חוזרות וכד.’הגשה שלא מגיעה לשלב הקומפילציה תקבל ציון 0.
הגשה שלא מתקמפלת תקבל ציון נמוך מ- 40 לפי סוג הבעיה.
הגשה שמתקמפלת תקבל ציון 40 ומעלה בהתאם לתוצאות הריצה, ותוצאת הבדיקה הידנית שלהקוד (חוץ ממקרה של העתקה).
תכנית הבדיקה האוטומטית מכילה תוכנה חכמה המגלה העתקות. מקרים של העתקות יטופלובחומרה