Find if Path Exists in Graph

Q: מהי סיבוכיות הזמן של בדיקה אם קיים מסלול בגרף?

בעזרת BFS או DFS, הזמן והזיכרון הם O(n + m) , עבור n צמתים ו- m קשתות: מבקרים בכל צומת פעם אחת ובודקים כל קשת משני קצותיה. Union-find עם איחוד לפי גודל וחציית מסלול עולה O(n + m·α(n)) זמן ו- O(n) זיכרון, כאשר α גדלה באיטיות כה רבה, שבפועל היא קבוע קטן.

Q: למה BFS זקוקה למערך visited?

בלעדיו, מחזור כמו 0 → 1 → 2 → 0 יגרום לחיפוש להימשך לנצח, וגם ללא מחזורים צומת עם כמה שכנים יוכנס לתור פעם אחת עבור כל שכן. סימון כל צומת ברגע שמכניסים אותו לתור מבטיח שהוא יעובד פעם אחת, וכך העבודה מוגבלת ל־ O(n + m) .

Q: מה עושים כיווץ מסלולים ואיחוד לפי גודל במבנה union-find?

הם שומרים על העצים רדודים כדי ש- find יישאר מהיר. איחוד לפי גודל תולה את העץ הקטן יותר מתחת לגדול יותר, כך שעומק של צומת גדל רק כשהקבוצה שלו לפחות מכפילה את גודלה, מה שמגביל את העומק ל- log n . דחיסת נתיבים, או חציית הנתיב שבה משתמשים כאן, מקצרת את הדרך לשורש בכל פעם שעוברים בה. יחד הם מורידים את העלות של כל פעולה ל- α(n) .

קלגרפים איחוד קבוצות

+10

לגרף לא מכוון יש n צמתים, שממוספרים מ־0 עד n-1. כל איבר [u, v] של edges מחבר את הצמתים u ו־v, ואפשר לעבור לאורך קשת בשני הכיוונים. החזר true אם אפשר להגיע מ־source אל destination לאורך הקשתות, ו־false אחרת. צומת תמיד יכול להגיע אל עצמו.

פונקציה

validPath(n: integer, edges: integer-2d-array, source: integer, destination: integer) → boolean

ninteger: מספר הצמתים
edgesinteger-2d-array: הקשתות, שכל אחת מהן היא זוג [u, v] של צמתים מחוברים
sourceinteger: הצומת שממנו מתחילים
destinationinteger: הצומת שאליו רוצים להגיע
מחזירהboolean: האם נתיב כלשהו מחבר בין המקור ליעד

אילוצים

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] כאשר 0 ≤ u, v ≤ n-1 וגם u ≠ v
אף צלע אינה מופיעה פעמיים, באף אחד מהכיוונים.
0 ≤ source, destination ≤ n-1

דוגמאות

קלט: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
פלט: true
הסבר: המסלול 0 → 1 → 2 → 3 משתמש בשלוש קשתות, ולכן ניתן להגיע לצומת 3. צמתים 4 ו-5 יוצרים חלק נפרד שהמסלול לא צריך לעבור בו לעולם.

קלט: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
פלט: false
הסבר: מצומת 2 מגיעים ל-0 ואז ל-1, ולא לשום דבר אחר. צומת 4 מחובר רק לצומת 3, ואין קשת שמחברת בין {0, 1, 2} ל-{3, 4}, ולכן התשובה היא false.

+16 בדיקות נסתרות בשליחה

שאלת המשך

נניח שהקשתות חד־כיווניות: [u, v] מאפשר לך לעבור מ־u ל־v בלבד. אילו משלוש הגישות עדיין עובדות, ומה משנים בהן?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

השאלה היא האם source ו־destination נמצאים באותו רכיב קשיר של הגרף. הדרך האיטית סורקת מחדש את רשימת הקשתות עד שלא מגיעים לשום דבר חדש. חיפוש לרוחב על פני רשימת שכנויות עובר על כל צומת וקשת פעם אחת, ו־union-find מגיע לאותה תשובה על ידי איחוד קבוצות תוך כדי קריאת הקשתות, ללא רשימות שכנים כלל.

טאטאו את הקצוות עד ששום דבר לא משתנה

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

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

הדבר נכון: צומת שנמצא במסלול באורך k מ־source יסומן לכל המאוחר במעבר ה־k, וצומת מסומן רק כשקשת מובילה אליו מצומת מסומן. בדוגמה הראשונה, מעבר אחד לפי סדר הרשימה מסמן את 1, את 2 ואת 3 בזה אחר זה, וזהו.

העלות תלויה בסדר הקשתות. אם המסלול רשום מהקצה הרחוק בחזרה, כל מעבר מסמן רק צומת נוסף אחד. מסלול דרך 5001 צמתים ידרוש אז 5000 מעברים על פני 5000 קשתות, כלומר 2.5 × 10^7 בדיקות קשת, בעוד שמעבר אחד על רשימת שכנים יעשה זאת.

אלגוריתם

צרו את reached וסמנו רק את source.
עברו על כל קשת [u, v]. אם בדיוק קצה אחד מסומן, סמנו את הקצה השני ותעדו שמשהו השתנה.
חזרו על המעבר כל עוד משהו השתנה ו-destination עדיין לא מסומן.
החזירו אם destination מסומן.

def validPath(n, edges, source, destination):
    reached = [False] * n
    reached[source] = True
    changed = True
    while changed and not reached[destination]:
        changed = False
        for u, v in edges:
            # An edge with exactly one reached end pulls the other end in.
            if reached[u] != reached[v]:
                reached[u] = reached[v] = True
                changed = True
    return reached[destination]

חיפוש לרוחב

האינטואיציה

הסריקה מבזבזת זמן בקריאה חוזרת של קשתות שהקצוות שלהן כבר הוכרעו מזמן. במקום זאת, רשמו לכל צומת את הצמתים שהוא מחובר אליהם. כל קשת [u, v] נכנסת לשתי הרשימות, כי אפשר לעבור בה בשני הכיוונים. לאחר מכן חקרו החוצה מ־source: הוציאו צומת מהתור והכניסו אליו כל שכן שעדיין לא ראיתם.

סמנו צומת ככזה שנראה כשאתם מכניסים אותו לתור, ולא כשאתם מוציאים אותו ממנו. כך אף צומת לא נכנס לתור פעמיים, והחיפוש מסתיים גם כשהגרף מכיל מעגלים, כמו 0 → 1 → 2 → 0. אם destination יוצא מהתור אי פעם, קיים מסלול. אם התור מתרוקן קודם, ראיתם את כל הצמתים שאליהם source יכול להגיע, ו־destination לא היה ביניהם.

כל צומת נכנס לתור לכל היותר פעם אחת, וכל קשת נבדקת פעמיים, פעם אחת מכל קצה, ולכן זמן הריצה הוא O(n + m) עבור m קשתות. רשימות השכנים דורשות O(n + m) מקום. שימוש בתור במקום ברקורסיה מונע ממסלול בן 5000 צמתים לחרוג מגודל מחסנית הקריאות.

אלגוריתם

בנה רשימת שכנויות: עבור כל קשת [u, v], הוסף את v לרשימה של u ואת u לרשימה של v.
סמן את source ככבר נראה והכנס אותו לתור.
הוצא צומת מתחילת התור. אם הוא destination, החזר true.
סמן והכנס לתור כל שכן שעדיין לא נראה.
כשהתור ריק, החזר false.

from collections import deque


def validPath(n, edges, source, destination):
    # Each edge goes both ways, so list it under both of its ends.
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen = [False] * n
    seen[source] = True
    queue = deque([source])
    while queue:
        node = queue.popleft()
        if node == destination:
            return True
        for nxt in graph[node]:
            if not seen[nxt]:
                # Mark on push, so no node enters the queue twice.
                seen[nxt] = True
                queue.append(nxt)
    return False

איחוד-חיפוש

האינטואיציה

לא צריך את המסלול, אלא רק לדעת אם קיים כזה. לכן נתייחס לגרף כאל קבוצות של צמתים מחוברים. בתחילה כל צומת הוא קבוצה בפני עצמו. קשת [u, v] אומרת ש-u ו-v שייכים לאותה קבוצה, ולכן נאחד את הקבוצות שלהם. אחרי שעוברים על כל הקשתות, source ו-destination מחוברים אם ורק אם הם באותה קבוצה.

נשמור כל קבוצה כעץ עם קישורי parent; השורש מציין את הקבוצה. find(x) עולה במעלה העץ עד לשורש. כדי לאחד קבוצות, נתלה שורש אחד מתחת לשני. בדוגמה השנייה, [0, 1] ו-[0, 2] בונים את הקבוצה {0, 1, 2}, ו-[3, 4] בונה את הקבוצה {3, 4}; find(2) ו-find(4) מחזירות שורשים שונים, ולכן התשובה היא false.

שני הרגלים שומרים על עצים שטוחים. תולים את הקבוצה הקטנה יותר מתחת לגדולה יותר, ובמהלך find מקצרים את המסלול בחצי על ידי הפניית כל צומת לסבא שלו. יחד, הם גורמים לכל פעולה לעלות α(n), פונקציית אקרמן ההפוכה, שנותרת קטנה מ-5 לכל קלט שתיתקלו בו אי פעם. קוראים את הקשתות פעם אחת ושומרים רק את parent ואת size: זיכרון O(n), ואין צורך לבנות רשימות שכנים.

אלגוריתם

הגדר parent[x] = x ואת size[x] = 1 עבור כל צומת.
עבור כל קשת [u, v], מצא את השורשים a ו-b של שני הקצוות.
אם הם שונים, חבר את השורש של הקבוצה הקטנה יותר מתחת לשורש השני וחבר את הגדלים.
החזר האם find(source) שווה ל-find(destination).

def validPath(n, edges, source, destination):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the group's root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        if a != b:
            # Hang the smaller group under the larger one.
            if size[a] < size[b]:
                a, b = b, a
            parent[b] = a
            size[a] += size[b]
    return find(source) == find(destination)

מלכודות ומקרי קצה

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

הוספת כל קשת בכיוון אחד בלבד. הגרף אינו מכוון, לכן [1, 0] חייבת לאפשר לך לעבור גם מ־0 ל־1. רשימת שכנויות חד־כיוונית מפספסת מסלולים שמשתמשים בקשת בכיוון ההפוך.
סימון צמתים ככאלה שכבר נראו כשמוציאים אותם מהתור, במקום כשמכניסים אותם אליו. כך צומת נכנס לתור פעם אחת עבור כל שכן שעובד לפניו, ולכן התור יכול להכיל עד 2m רשומות, במקום לכל היותר n.
שכחה ש־source יכול להיות שווה ל־destination. התשובה היא true גם אם אין לצומת הזה קשתות כלל.
שימוש ב־DFS רקורסיבי במסלול ארוך. מסלול שעובר דרך 5000 צמתים כולל 5000 קריאות מקוננות, מעבר למגבלת ברירת המחדל של Python, שהיא 1000. השתמש בתור או במחסנית מפורשת.
השוואה בין parent[source] ל־parent[destination] במבנה union-find. רק השורשים מציינים קבוצה; השווה תמיד בין find(source) ל־find(destination).
שכחה של ההיסט ב־Lua וב־R, שבהן המערכים מתחילים ב־1: הצומת x נמצא באינדקס x+1.

שאלות נפוצות4

האם כדאי להשתמש ב-BFS, ב-DFS או ב-union-find כדי לבדוק אם קיים מסלול?

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

מהי סיבוכיות הזמן של בדיקה אם קיים מסלול בגרף?

בעזרת BFS או DFS, הזמן והזיכרון הם O(n + m), עבור n צמתים ו-m קשתות: מבקרים בכל צומת פעם אחת ובודקים כל קשת משני קצותיה. Union-find עם איחוד לפי גודל וחציית מסלול עולה O(n + m·α(n)) זמן ו-O(n) זיכרון, כאשר α גדלה באיטיות כה רבה, שבפועל היא קבוע קטן.

למה BFS זקוקה למערך visited?

בלעדיו, מחזור כמו 0 → 1 → 2 → 0 יגרום לחיפוש להימשך לנצח, וגם ללא מחזורים צומת עם כמה שכנים יוכנס לתור פעם אחת עבור כל שכן. סימון כל צומת ברגע שמכניסים אותו לתור מבטיח שהוא יעובד פעם אחת, וכך העבודה מוגבלת ל־O(n + m).

מה עושים כיווץ מסלולים ואיחוד לפי גודל במבנה union-find?

הם שומרים על העצים רדודים כדי ש-find יישאר מהיר. איחוד לפי גודל תולה את העץ הקטן יותר מתחת לגדול יותר, כך שעומק של צומת גדל רק כשהקבוצה שלו לפחות מכפילה את גודלה, מה שמגביל את העומק ל-log n. דחיסת נתיבים, או חציית הנתיב שבה משתמשים כאן, מקצרת את הדרך לשורש בכל פעם שעוברים בה. יחד הם מורידים את העלות של כל פעולה ל-α(n).

Python

def validPath(n, edges, source, destination):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

קלט

n = 6
edges = [[0, 1], [1, 2], [2, 3], [4, 5]]
source = 0
destination = 3

צפוי

true

Find if Path Exists in Graph

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

טאטאו את הקצוות עד ששום דבר לא משתנה

חיפוש לרוחב

איחוד-חיפוש

מלכודות ומקרי קצה

שאלות נפוצות4

בעיות דומות