Find if Path Exists in Graph

Q: ما هو التعقيد الزمني للتحقق من وجود مسار في رسم بياني؟

باستخدام BFS أو DFS، يكون الزمن والمساحة O(n + m) ، لعقد عددها n وحواف عددها m : تتم زيارة كل عقدة مرة واحدة، ويُتحقَّق من كل حافة من كلا طرفيها. وتبلغ تكلفة بنية Union-find مع الدمج حسب الحجم وتقسيم المسار إلى النصف O(n + m·α(n)) من الزمن و O(n) من المساحة، حيث تنمو α ببطء شديد يجعلها ثابتًا صغيرًا عمليًا.

Q: لماذا تحتاج خوارزمية BFS إلى مصفوفة للعُقد التي تمت زيارتها؟

بدونه، تؤدي دورة مثل 0 → 1 → 2 → 0 إلى استمرار البحث بلا نهاية، وحتى من دون دورات، ستُضاف العقدة التي لها عدة جيران إلى قائمة الانتظار مرةً لكل جار. يضمن وضع علامة على كل عقدة لحظة إضافتها إلى قائمة الانتظار معالجتها مرة واحدة، وهذا ما يجعل حجم العمل محدودًا بـ O(n + m) .

Q: ما وظيفة ضغط المسار والاتحاد حسب الحجم في بنية الاتحاد-والبحث؟

تحافظ هذه الطرق على الأشجار قليلة العمق لكي تظل 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 يقعان في الجزء المتصل نفسه من الرسم البياني. تعيد الطريقة البطيئة فحص قائمة الحواف حتى لا يعود بالإمكان الوصول إلى أي شيء جديد. يستكشف البحث بعرض الشجرة كل عقدة وحافة مرة واحدة باستخدام قائمة المجاورة، وتصل بنية الاتحاد والبحث إلى الإجابة نفسها بدمج المجموعات أثناء قراءة الحواف، دون الحاجة إلى قوائم المجاورين إطلاقًا.

امسح الحواف حتى لا يتغير شيء

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

ضع علامة على كل عقدة تعرف أنك تستطيع الوصول إليها، بدءًا من 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 استدعاء متداخل، متجاوزًا الحد الافتراضي البالغ 1000 في Python. استخدم قائمة انتظار أو مكدسًا صريحًا.
مقارنة parent[source] بـ parent[destination] في بنية الاتحاد-والبحث. الجذور وحدها هي التي تحدد المجموعة؛ قارن دائمًا بين find(source) وfind(destination).
نسيان الإزاحة في Lua وR، حيث تبدأ المصفوفات عند 1: توجد العقدة x عند الفهرس x+1.

أسئلة شائعة4

هل أستخدم BFS أم DFS أم union-find للتحقق مما إذا كان هناك مسار؟

الثلاثة جميعها خطية أو قريبة من ذلك. يمكن لـBFS وDFS التوقف بمجرد وصولهما إلى الوجهة، ويمكنهما إرجاع المسار نفسه. لا تحتاج بنية الاتحاد والبحث إلى قائمة مجاورة، وتقرأ كل حافة مرة واحدة، وتبرز كفاءتها عندما تُطرح أسئلة كثيرة عن الاتصال في الرسم البياني نفسه، لأن كل سؤال بعد عمليات الدمج يتطلب استدعاءين لـfind.

ما هو التعقيد الزمني للتحقق من وجود مسار في رسم بياني؟

باستخدام BFS أو DFS، يكون الزمن والمساحة O(n + m)، لعقد عددها n وحواف عددها m: تتم زيارة كل عقدة مرة واحدة، ويُتحقَّق من كل حافة من كلا طرفيها. وتبلغ تكلفة بنية Union-find مع الدمج حسب الحجم وتقسيم المسار إلى النصف O(n + m·α(n)) من الزمن وO(n) من المساحة، حيث تنمو α ببطء شديد يجعلها ثابتًا صغيرًا عمليًا.

لماذا تحتاج خوارزمية BFS إلى مصفوفة للعُقد التي تمت زيارتها؟

بدونه، تؤدي دورة مثل 0 → 1 → 2 → 0 إلى استمرار البحث بلا نهاية، وحتى من دون دورات، ستُضاف العقدة التي لها عدة جيران إلى قائمة الانتظار مرةً لكل جار. يضمن وضع علامة على كل عقدة لحظة إضافتها إلى قائمة الانتظار معالجتها مرة واحدة، وهذا ما يجعل حجم العمل محدودًا بـ O(n + m).

ما وظيفة ضغط المسار والاتحاد حسب الحجم في بنية الاتحاد-والبحث؟

تحافظ هذه الطرق على الأشجار قليلة العمق لكي تظل 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

مسائل مشابهة