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

נחזור שוב לאלגוריתם בשאלה סדר הדפסת הצמתים וזמן הריצה, אך כעת נניח שיש מסלול מ$\displaystyle s$ רק ל$\displaystyle |V|^{\alpha }$ מהצמתים, כאשר $\displaystyle \alpha <1$ הוא קבוע כלשהו.

1. האם זמן הריצה הוא בהכרח $\displaystyle \Theta (|V|+|E|)$?
2. האם ייתכן שזמן הריצה הוא $\displaystyle \Theta (|V|+|E|)$?