עמוד 1 מתוך 1

קיץ 2004

הודעהפורסם: 20:48 15/07/2010
על ידי Brk
בשאלה 3:
נתון אלגוריתם חדש למציאת עץ פורש מינימלי בגרף ממושקל { V,E,W} = G:
מאתחלים עץ ריק T
ממיינים את הקשתות מ-E לתור Q.
כל עוד העץ אינו מכיל N-1 צלעות,
מוציאים את הצלע e המינימלית ב Q.
אם e לא סוגרת מעגל עם הקשתות שכבר בתוך העץ T,
מוסיפים אותה לעץ T.
מחזירים את T כעץ פורש מינימלי.

ג) (7 נק') אם כל המשקולות בגרף היו שלמים חיוביים בין 1 ל 5, האם היה ניתן לשפר את זמן הריצה? נמקו את תשובתכם.
רעיונות לג'? :shock: