الجسور ونقاط المفصل
العثور على الحواف والعقد التي تفصل الرسم البياني
الجسور ونقاط المفصل درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
المواضع الهشة في الرسم البياني
توجد أجزاء حرجة في بعض الرسوم البيانية غير الموجّهة: إذا أزلتها، انقسم الرسم إلى أجزاء. ويكشف العثور عليها عن نقاط الضعف.
ما هو الجسر
الـجسر ضلع تؤدي إزالته إلى زيادة عدد المكوّنات المتصلة. وهو المسار الوحيد بين منطقتين.
ما هي نقطة الفصل
نقطة الفصل عقدة تؤدي إزالتها إلى فصل الرسم البياني. وتُعد الشبكات هذه النقاط المفردة مواضع فشل حرجة.
أشجار DFS مرة أخرى
تعتمد كلتاهما على عملية DFS واحدة، مع تتبّع وقت الاكتشاف وقيمة low، بطريقة تشبه Tarjan إلى حد كبير، لكن على رسم بياني غير موجّه.
disc = [-1] * n
low = [-1] * nتعني low أبعد وصول
قيمة low للعقدة هي أقدم معرّف اكتشاف يمكن الوصول إليه من شجرتها الفرعية في DFS، وربما عبر ضلع راجع واحد إلى الأعلى.
هيّئ القيم عند الدخول
عندما تدخل DFS إلى عقدة، سجّل disc و low بقيمة المؤقت الحالية، ثم تابع إلى جيرانها.
disc[u] = low[u] = timer
timer += 1شرط الجسر
بعد تنفيذ التكرار داخل الابن v، إذا كان low[v] > disc[u]، فلا يوجد ضلع راجع يتجاوز u، ولذلك يكون الضلع u-v جسرًا.
if low[v] > disc[u]:
bridges.append((u, v))شرط نقطة الفصل
تكون u غير الجذر نقطة فصل عندما يحقق أحد الأبناء v الشرط low[v] >= disc[u]، إذ لا تستطيع شجرة v الفرعية تجاوز u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)الحالة الخاصة بالجذر
يكون جذر DFS نقطة فصل فقط إذا كان له ابنان أو أكثر في شجرة DFS، لذا احسب عددهم.
if parent[u] == -1 and children > 1:
art.add(u)تجاوز ضلع الأب
عند تحديث low انطلاقًا من ضلع راجع، لا تعد عبر الضلع إلى الأب، وإلا أخطأت في تحديد الجسور.
if v != parent[u]:
low[u] = min(low[u], disc[v])إجابة واحدة لكليهما في مرور واحد
تجد عملية DFS واحدة كل جسر وكل نقطة فصل معًا بتعقيد O(V + E). ولا حاجة إلى اجتياز إضافي.
تحقق سريع
بعد تنفيذ التكرار داخل الابن v انطلاقًا من u، وجدت أن low[v] > disc[u]. ماذا وجدت؟
مراجعة: الأضلاع والعقد الحرجة
تجد عملية DFS واحدة باستخدام disc و low كل شيء: يشير low[v] > disc[u] إلى جسر، ويشير low[v] >= disc[u] إلى نقطة فصل. 🌉
الأسئلة الشائعة
هل درس «الجسور ونقاط المفصل» مجاني؟
نعم — نص درس «الجسور ونقاط المفصل» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «الجسور ونقاط المفصل»؟
العثور على الحواف والعقد التي تفصل الرسم البياني تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «الجسور ونقاط المفصل»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- الترتيب الطوبولوجي بخوارزمية Kahn
- اكتشاف الدورات في الرسوم البيانية الموجّهة
- المكوّنات شديدة الاتصال
- الجسور ونقاط المفصل