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

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

עריכה

נזכר שבמערך 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 עוברת בסופו של דבר על כל קשת.