מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/גרפים וייצוגיהם/תרגילים/מימוש לפונקציית המעבר על הקשתות/שאלה

נתון גרף $G=(V,E)$. הגרף דליל, ולכן רוצים להשתמש בייצוג רשימה. עם זאת, סיבוכיות מימוש הפונקציה E(G) שראינו בכיתה, דהיינו $\mathrm{\Theta }(|E|+|V|)$, גבוהה מדי לטעמנו.

אנא הסבר כיצד לשנות את המימוש כך שסיבוכיות הפונקציה תרד ל$\mathrm{\Theta }(|E|)$, מבלי להגדיל את סיבוכיות הפונקציות האחרות. אנא הסבר בקצרה (רצוי בתרשים) את השינויים הנדרשים, וכתוב את הפסוודו-קוד לפונקציה E(G).

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