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

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

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

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