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

נתון טיפוס אבסטרקטי "שק" בעל הממשק הבא:

#Makes a new sack.
Make-Sack()

# Inserts an element (v) to a sack (ks).
Insert(k, v)

# Returns whether the sack is empty.
Empty(k)

# Deletes *some* element from a (non-empty) sack (k) and returns the value of 
#	the deleted element.
Delete(k)

זהו מבנה נתונים דומה לתור, אלא שהפעולה Insert מכניסה איבר, והפעולה Delete שולפת (ומחזירה) איבר כלשהו, לאו דווקא האיבר הראשון שהוכנס.

להלן ווריאציה אפשרית של אלגוריתם החיפוש הרוחבי, אך כעת עם שק במקום תור:

Sack-Search(G, s)
1	k = Make-Sack()

2	Visited = Make-Array( |V| )

3	for u in V
4		Visited[u] = False

5	Print s
6	Visited[s] = True
7	Insert(k, s)

8	while not Empty(q)
9		u = Delete(k)
	
10		For every neighbor v of u
11			if Visited[v] == False
12				Print v
13				Visited[v] = True
14				Insert(k, v)

נניח שהגרף קשיר מ$\displaystyle s$ (יש מסלול מ$\displaystyle s$ לכל צומת).

1. האם Sack-Search בהכרח ידפיס כל צומת בדיוק פעם יחידה?
2. האם סדר ההדפסות בהכרח יהיה לפי מרחק הצמתים מ$\displaystyle s$?