Question

spanning_tree
spring17_a
mst

נתונים גרף לא מכוון וקשיר G=(V,E)G = (V,E) ופונקציית משקל על הקשתות w:ERw:E \to \mathbb{R}. כמו כן, נתון ש-E=V+99|E| = |V| + 99 הציעו אלגוריתם המוצא עץ פורש מינימום לגרף GG.

2

Answers

נראה שניתן לפתור בזמן לינארי על ידי 99 הפעלות של הכלל האדום.

האלגוריתם:

  1. מצא עץ פורש של GG (על ידי שימוש ב-BFS), TT.
  2. לכל קשת eETe \in E \setminus T בצע:
  • הוסף את ee ל-TT ומחק (כלל אדום) את הקשת הכבדה במעגל שנוצר.

נכונות:

נובעת מהשימוש בכלל האדום.

סיבוכיות:

  1. מציאת עץ פורש - O(n+m)=O(n)O(n + m) = O(n)
  2. הוספה ומחיקה בודדת של קשת ממעגל - O(n+m)=O(n)O(n + m) = O(n) ובסך הכל 99 כאלו - O(n+m)=O(n)O(n + m) = O(n)

סך הכל - O(n+m)=O(n)O(n + m) = O(n)

3
Feedback