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

מציאת דרגת היציאה

נזכר שבמערך Vertexes, כל איבר הוא רשימה מקושרת. נמצא את הרשימה המקושרת, ונחזיר את גודלה.

Out-Degrees(G, v)
1	lst = Vertexes[v]

2 	return Size(lst)

קל לראות שהסיבוכיות היא $\displaystyle O(1)$.

מציאת דרגת הכניסה

נעבור כעת על כל הצמתים $\displaystyle u$. עבור כל צומת $\displaystyle u$, נמצא האם יש קשת מ$\displaystyle u$ לצומת אותו אנו מחפשים.

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

הסיבוכיות היא $\displaystyle \Theta (|V|+|E|)$. הלולאה החיצונית 2-7 עוברת על כל איבר המתאים לצומת. הלולאה הפנימית 2-7 עוברת בסופו של דבר על כל קשת.