שאלה
נתון גרף ממושקל וקשיר G שבו משקל כל קשת הוא 1 או 2.
צריך לכתוב אלגוריתם שמוצא עץ פורש מינימלי של G בזמן (O(V+E.
עושה רושם שקרוסקל/פרים/סולין לא רלוונטיים כאן בגלל הזמן ריצה.
אפשר אולי במקום למיין (שזה השלב הראשון שקרוסקל עושה), פשוט לבצע 2 לולאות (לא מקוננות, אלא 2 לולאות נפרדות אחת אחרי השנייה), שהראשונה עוברת על הצלעות שמשקלן 1, והשנייה עוברת על הצלעות שמשקלן 2, באופן הבא:
(Kruskal'(G,w
A <- empty set
for each v in V
(do Make Set(v
for each (u,v) in E such that w(u,v) = 1
(do if Find Set(u) is not equal to Find Set(v
{(then A <-- AU{(u,v
(Union (u,v
for each (u,v) in E such that w(u,v) = 2
(do if Find Set(u) is not equal to Find Set(v
{(then A<---AU{(u,v
(Union(u,v
return A
יכול להיות שזה נכון? אם כן, אני לא ממש יודע להוכיח למה זה נכון.
ולמה הזמן פה הוא V + E?
אודה על עזרתכם.
נתון גרף ממושקל וקשיר G שבו משקל כל קשת הוא 1 או 2.
צריך לכתוב אלגוריתם שמוצא עץ פורש מינימלי של G בזמן (O(V+E.
עושה רושם שקרוסקל/פרים/סולין לא רלוונטיים כאן בגלל הזמן ריצה.
אפשר אולי במקום למיין (שזה השלב הראשון שקרוסקל עושה), פשוט לבצע 2 לולאות (לא מקוננות, אלא 2 לולאות נפרדות אחת אחרי השנייה), שהראשונה עוברת על הצלעות שמשקלן 1, והשנייה עוברת על הצלעות שמשקלן 2, באופן הבא:
(Kruskal'(G,w
A <- empty set
for each v in V
(do Make Set(v
for each (u,v) in E such that w(u,v) = 1
(do if Find Set(u) is not equal to Find Set(v
{(then A <-- AU{(u,v
(Union (u,v
for each (u,v) in E such that w(u,v) = 2
(do if Find Set(u) is not equal to Find Set(v
{(then A<---AU{(u,v
(Union(u,v
return A
יכול להיות שזה נכון? אם כן, אני לא ממש יודע להוכיח למה זה נכון.
ולמה הזמן פה הוא V + E?
אודה על עזרתכם.