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

להלן גרסה של אלגוריתם החיפוש הרוחבי:

BFS(G, s)
1	q = Make-Queue()

2	Visited = Make-Array( |V| )

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

5	Print s
6	Visited[s] = True
7	Enqueue(q, s)

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

גרסה זו עוברת על כל הצמתים ברכיב הקשירות של $\displaystyle s$ ומדפיסה אותם לפי סדר ההגעה מ$\displaystyle s$.

להלן גרף $\displaystyle G$ שבו צומת המוצא הוא $\displaystyle s$.

בעיית החיפוש הרוחבי.

הנח שבשורה 10, אם לצומת $\displaystyle u$ יש יותר משכן יחיד, סדר הצמתים הוא כסדרם המספרי.

1. באיזה סדר יודפסו האיברים?
2. נניח ש $\displaystyle G=(V,E)$ קשיר מ$\displaystyle s$ (יש מסלול מ$\displaystyle s$ לכל צומת). אנא הוכח שהאלגוריתם יעבוד בזמן $\displaystyle \Theta (|V|+|E|)$.