מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/גרפים וייצוגיהם/תרגילים/חישוב דרגות כניסה ויציאה/תשובה
מציאת דרגת היציאה
עריכהנזכר שבמערך Vertexes
, כל איבר הוא רשימה מקושרת. נמצא את הרשימה המקושרת, ונחזיר את גודלה.
Out-Degrees(G, v)
1 lst = Vertexes[v]
2 return Size(lst)
קל לראות שהסיבוכיות היא .
מציאת דרגת הכניסה
עריכהנעבור כעת על כל הצמתים . עבור כל צומת , נמצא האם יש קשת מ לצומת אותו אנו מחפשים.
In-Degrees(G, v)
1 count = 0
2 for u in Vertexes
3 lst = Vertexes[u]
4 lnk = lst.front
5 while lnk != Nil
6 if lnk.value == (u, v)
7 ++count
8 return count
הסיבוכיות היא . הלולאה החיצונית 2-7 עוברת על כל איבר המתאים לצומת. הלולאה הפנימית 2-7 עוברת בסופו של דבר על כל קשת.