המדריך למבנה נתונים Union-Find

Disjoint Set Union - DSU

יש לך גרף המכיל יותר מרכיב אחד, ואתה צריך למצוא מכמה רכיבים הוא בנוי. דרך אחת, סורקת כל אחד מהצמתים בגישה של brute force אבל היא איטית מדי. גישה נוספת היא סריקה של גרפים באמצעות BFS או DFS היעילה בהרבה. אבל הגישה שאותה נציג במדריך Union-Find היא יעילה הרבה יותר ומציעה סיבוכיות זמן כמעט לינארית O(N). הכי יעיל שאפשר.

1. הרעיון

מבנה הנתונים Union-Find מטפל בסטים מפורקים disjoint sets באמצעות 2 פונקציות עיקריות:

• Union - למיזוג 2 קבוצות.
• Find - לקביעת הקבוצה אליה שייך פריט.

אפשר לחשוב על זה באופן הבא:

• Union - שתי קבוצות כדורגל המתמזגות לקבוצה אחת.
• Find - בודק מי הקפטן של הקבוצה אליה כל שחקן שייך.

במדריך זה נבין את האלגוריתם בשלושה צעדים:

1. יישום נאיבי
2. שיפור באמצעות Path Compression
3. אופטימיזציה באמצעות Union by Rank

2. יישום נאיבי של Union-Find

הגדרה

נייצג כל פריט באמצעות מצביע להורה parent pointer. שזה כמו להגיד את שמו של קפטן הקבוצה שלך כששואלים אותך לאיזו קבוצה אתה שייך.

כאשר אם ההורה של פריט מסויים (x) הוא אותו x אנחנו יודעים שהגענו לקפטן הקבוצה המכונה root (=שורש הקבוצה).

If parent[x] == x # x is the root of its group.

בהנתן מספר פריטים n נגדיר מערך parent באורך n כך שכל פריט במערך הוא ההורה של עצמו.

באופן מעשי, כל פריט יוגדר כפריט במערך parent:

parent = [i for i in range(n)]  # each node is its own parent

• כל פריט הוא ה-root של עצמו.
• כל פריט הוא שורש של עץ נתונים-tree.

הפונקציה find()

כדי למצוא את ה-root של פרמטר x, הפונקציה find() עוקבת אחר המצביעים במעלה העץ עד שהיא מגיעה ל-root של העץ:

def find(parent, x):
    while parent[x] != x:   # If not root keep searching up the tree recursively
        x = parent[x]
    return x                      # If x == parent[x] than found the root parent, return it

• פריט הזהה להורה שלו הוא ה-root, ומטרת הפונקציה היא להחזירו.

הפונקציה union()

כדי למזג 2 קבוצות, הפונקציה union מוצאת את ה-root של כל אחת ואז מחברת ביניהם:

def union(parent, x, y):
    root_x, root_y = find(parent, x), find(parent, y)
    if root_x != root_y:
        parent[root_x] = root_y  # attach x’s root under y’s root
        return True
    return False

• אם ה-root של שני הפריטים שונה אז הפונקציה תמזג את שני הסטים לסט אחד, ותחזיר True.
• אך אם שווה, תחזיר False כי לא עשתה את העבודה שלה שהיא למזג בין שני הסטים.

התוצאה היא tree הנוצר תחת כל פריט במערך parent.

סיבוכיות

• find(): O(h), כאשר h הוא גובה העץ.
• union(): O(h) על פי מספר הפעמים שהפונקציה רצה לצורך הרכבת סט מפריטים.
• במקרה הגרוע ביותר אורך העץ יהיה O(n) כמספר הפריטים.

3. Path Compression

כדי להאיץ את הפונקציה find נשטח את העץ על ידי path compression.

לצורך כך, הפונקציה find, תגרום לכך שכל אחד מהרכיבים יצביע ישירות על ה-root במקום על ההורה המיידי שלו. הדבר דומה לכך שבמקום שעובד יפנה לדרגי הביניים הוא פונה ישר לבוס הגדול.

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # recursion compresses path
    return parent[x]

עכשיו:

• קריאות לפונקציה find() לאחר הדחיסה יעשו כמעט בזמן קבוע.
• סיבוכיות הזמן היא amortized O(α(n)) קטנה מ-4 (לא נכנס להוכחה). שזה כמעט זמן קבוע. למה קוראים לזה יעילות amortized (מופחתת) כי מודד את הזמן הממוצע לביצוע הפעולה על פני מספר גדול של פעולות בעוד שלרוב מחפשים את המקרה הגרוע ביותר.

4. Union by Rank

אפילו אם משתמשים ב-path compression, הפונקציה union() עלולה ליצור עצים לא מאוזנים כי האיחוד במסגרת הפונקציה נעשה באופן אקראי. הפתרון הוא שיוך rank דרגה לכל פריט, ואז חיבור עץ מדרג נמוך תחת עץ מדרג גבוה. כאשר ה-rank הוא בקירוב גובה העץ h תחת הפריט. למה בקירוב? כי בעוד שה-rank גדל רק בתנאים מסוימים, פעולת דחיסת הנתיב (Path Compression) יכולה לשנות את מבנה העץ בפועל, ולכן ה-rank הוא הערכה של הגובה ולא הגובה המדויק.

ניתן לקוד לדבר בעד עצמו:

def union(parent, rank, x, y):
    root_x, root_y = find(parent, x), find(parent, y)
    if root_x == root_y:
        return False

    if rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    elif rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    else:
        parent[root_y] = root_x
        rank[root_x] += 1
    return True

נסביר:

במסגרת מבנה נתונים Union-Find הערך rank הוא קירוב של גובה העץ h, כאשר:

• כל סט מיוצג באמצעות עץ.
• ה-root מייצג את הסט.
• באמצעות rank[root] קובעים איזה root יהיה ההורה כשממזגים שני סטים. עושים זאת על ידי חיבור העץ שיש לו את ה-rank הנמוך תחת העץ שיש לו את ה-rank הגבוה במטרה לשמור על עץ נמוך ככל הניתן מה שמקנה לעץ יעילות גבוהה.
• מדוע מגדילים את ה-rank רק כאשר לשני ההורים אותו rank? כי מיזוג שני עצים שוני גובה אינו משנה את הגובה של הגבוה מביניהם (לדוגמה: חיבור עץ בגובה 2 תחת עץ בגובה 3 משאיר את הגובה של הגבוה על 3). לעומת זאת, מיזוג של עצים שווי גובה גורם לעץ הממוזג להיות גבוה יותר בהכרח.

סיבוכיות זמן

סיבוכיות הזמן תוך שימוש בשני הטריקים path compression + rank הינה:

• Find: O(α(n)) ≈ constant.
• Union: O(α(n)) ≈ constant.

זו יעילות מופחתת amortized הנותנת סה"כ תוצאה הקרובה ל- O(1).

5. בעיה לדוגמה: מציאת מספר הרכיבים בגרף לא מכוון

נתון גרף המורכב מ-n צמתים ומרשימה של קשתות edges לא מכוונות.

צריכים לחשב את מספר הרכיבים בגרף.

פתרון נאיבי, ללא שימוש ב-path compression וב-rank הוא הבא:

def count_components_naive(n, edges):
    parent = [i for i in range(n)]

    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x

    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x != root_y:
            parent[root_x] = root_y
            return True
        return False

    count = n
    for u, v in edges:
        if union(u, v):
            count -= 1

    return count


# Test cases
print(count_components_naive(3, [[0,1],[0,2]]))      # 1
print(count_components_naive(6, [[0,1],[1,2],[2,3],[4,5]]))  # 2
print(count_components_naive(2, []))                 # 2
print(count_components_naive(0, []))                 # 0

פתרון יעיל משמעותית משתמש בשני הטריקים שלמדנו Path Compression + Rank:

def count_components_optimized(n, edges):
    parent = [i for i in range(n)]
    rank = [0] * n

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x == root_y:
            return False
        if rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        elif rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        else:
            parent[root_y] = root_x
            rank[root_x] += 1
        return True

    count = n
    for x, y in edges:
        if union(x, y):
            count -= 1

    return count

6. ניתוח ביצועים

סיבוכיות זמן ריצה

האלגוריתם משתמש ב- Path Compression + Rank, ולפיכך:

1. אתחול
   בניית המערכים parent ו-rank דורשת זמן לינארי O(N).

2. עיבוד כל הקשתות
   כאשר לכל קשת x, y יש צורך:

   • לבצע find(x) ו- find(y). דבר הדורש זמן ביצוע O(α(n)) כאשר α(n) הוא פונקצית אקרמן הפוכה הדורשת זמן ביצוע נמוך מ-4 עבור כל n.
   • union(x, y) גם הוא דורש זמן ביצוע O(α(n)).

   לפיכך עיבוד הקשתות דורש: O(E × α(n)) כאשר E הוא מספר הקשתות.

בגלל ש-α(n) הוא קבוע, סך כל זמן הביצוע הוא כמעט קבוע: O(n+Eα(n)) ≈ O(n+E)

סיבוכיות מקום

כל אחד מהמערכים parent ו-rank דורש זמן ביצוע לינארי O(N).

הרקורסיה של find() דורש לכל היותר O(log N).

סך כל סיבוכיות המקום היא O(N).

7. בעיות אחרות אותם ניתן לפתור באמצעות Union-Find

משתמשים בUnion-Find לפתרון מגוון בעיות תכנותיות. ביניהם:

• קישוריות רשתות Network connectivity . לדוגמה: האם שני מחשבים מחוברים?
• קישוריות דינמית Dynamic Connectivity - כאשר מוסיפים קישורים בין צמתים ורוצים לחקור את השינוי בזמן אמת.
• האלגוריתם של קרוסקל Kruskal’s Minimum Spanning Tree
• איתור אשכולות פיקסלים במסגרת עיבוד תמונות

נסכם

מבנה הנתונים Union-Find הוא דרך אלגנטית להתמודדות עם סטים מפורקים disjoint sets. במדריך זה, הצענו דרך הבנה שעשויה להועיל למתחילים הכוללת: התחלה נאיבית כדי להבין את הבעיה, אחר כך תוספת path compression להאצת תהליך החיפוש, ואז union by rank במטרה לשמור על עצים נמוכי קומה. מה שיפה הוא ששינויים קטנים בקוד יעבירו אותך מקוד שזמן הביצוע שלו לינארי לזמן ביצוע כמעט קבוע O(α(n)) ≈ constant. הישג מרשים המקנה ל Union-Find מקום של כבוד בין האלגוריתמים להתמודדות עם גרפים.

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

אלגוריתם חיפוש לעומק DFS - מהבנה ליישום

הבנת אלגוריתם חיפוש לרוחב - BFS - סריקה של גרפים ומציאת הנתיב הקצר ביותר

אתגר תכנותי : Graph Valid Tree

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים