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