1 of 31

רקורסיות

צביקה ברגר

מבני נתונים 12

Union Find

צביקה ברגר

בס"ד

2 of 31

Union find

בס"ד

3 of 31

דוגמא שימוש

  • דוגמא לשימוש ב-union find היא חישוב רכיבי קשירות תחת הוספת קשתות לגרף.

הגרף מתחיל בלי קשתות (וכל קדקוד הוא רכיב קשירות).

בכל פעם שמוסיפים קשת ייתכן ששני רכיבי קשירות יתמזגו ונרצה לאחד אותם.

​

בס"ד

4 of 31

עצים

בס"ד

5 of 31

מימוש עם רשימות מקושרות

בס"ד

6 of 31

ייעול 1

בס"ד

7 of 31

ייעול 1

בס"ד

8 of 31

ייעול 2

בס"ד

9 of 31

ייעול 2

בס"ד

10 of 31

ייעול 2

בס"ד

11 of 31

עצים

בס"ד

12 of 31

מימוש על ידי יער

בס"ד

13 of 31

כיווץ מסלולים

בס"ד

14 of 31

כיווץ מסלולים

בס"ד

15 of 31

Question 1

בס"ד

16 of 31

בעיה

בס"ד

17 of 31

פתרון - רשימות

בס"ד

18 of 31

פתרון - רשימות

בס"ד

19 of 31

פתרון - רשימות יעיל

בס"ד

20 of 31

פתרון - יער של עצים הפוכים

בס"ד

21 of 31

Question 2

בס"ד

22 of 31

בעיה

בס"ד

23 of 31

פתרון

בס"ד

24 of 31

Question 3

בס"ד

25 of 31

בעיה

בס"ד

26 of 31

פתרון

בס"ד

27 of 31

פתרון

בס"ד

28 of 31

Question 4

בס"ד

29 of 31

בעיה

בס"ד

30 of 31

פתרון

בס"ד

31 of 31

שאלות?

בס"ד