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

נוסיף עוד רשימה מקושרת, has-neighbors, המתארת את הצמתים שלהם יש שכנים.

דוגמה: בתרשים הבא, הרשימה המקושרת has-neighbors מכילה חוליות בעלות התוכן 1, 2, 3, ו4, מפני שאלה הצמתים שלהם שכנים. שתי הרשימות המקושרות.

קל לראות שסיבוכיות A(G, u) וV(G) אינן מושפעות מהוספת הרשימה המקושרת (הן אינן משתמשות בו). להלן הפסוודו-קוד החדש של E(G):

Count-Num-Edges(G)
1	count = 0
		
2	lnk = G.has-neighbors.front
	
3	while lnk != Nil
4		u = lnk.value
			
5		count = count + Size( G.Vertexes[u] )
	
6		lnk = lnk.next
	
7	return count
	
	
# Returns an array of the edges of a graph (G).
E(G)
1	Edges = Make-Array( Count-Num-Edges(G) )
			
2	i = 0
	
3	lnk = G.has-neighbors.front
		
4	while lnk != Nil
5		u = lnk.value
			
6		for v in A(G, u)		
7			Edges[i++] = (u, v)
	
8		lnk = lnk.next
				
9	return Edges

פונציית-העזר Count-Num-Edges סופרת את מספר הצמתים. שורה 1 מאתחלת משתנה הסופר את מספר הצמתים ל0, ושורה 7 מחזירה אותו. הלולאה 3-6 (יחד עם 2) עוברת על כל חוליות has-neighbors. עבור כל חוליה, 4 מוצאת את מספר הצומת, ו$\displaystyle 5$ מוצאת את מספר שכניו. הפונקציה E מייצרת את המערך Edges ב1, ומחזירה אותו ב9. הלולאה 4-8 (יחד עם 3) עוברת על כל חוליות has-neighbors. עבור כל חוליה, 5 מוצאת את מספר הצומת, ו$\displaystyle 6-7$ רצות על שכניו. לכל שכן, קשת מתאימה מיתוספת לEdges.