المكوّنات شديدة الاتصال
تجميع العقد القابلة للوصول المتبادل باستخدام Tarjan
المكوّنات شديدة الاتصال درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ما هو المكوّن شديد الاتصال
إن المكوّن شديد الاتصال مجموعة قصوى من العقد، بحيث تستطيع كل عقدة الوصول إلى كل عقدة أخرى باتباع الأضلاع الموجّهة.
لماذا نهتم بذلك
يؤدي دمج كل مكوّن شديد الاتصال في عقدة فائقة واحدة إلى تحويل أي رسم بياني موجّه إلى DAG. وهذا يسهّل فهم التبعيات المتبادلة.
خوارزمية Tarjan في مرور واحد
تجد خوارزمية Tarjan كل المكوّنات شديدة الاتصال في عملية DFS واحدة. وتعمل بتعقيد O(V + E)، أي بالتكلفة نفسها لعملية اجتياز عادية واحدة.
أرقام الاكتشاف
امنح كل عقدة وقت اكتشاف وفق ترتيب زيارتها الأولى بواسطة DFS. تتيح لك هذه المعرّفات مقارنة العقدة التي شوهدت أولًا.
disc = [-1] * n
timer = 0قيمة الارتباط المنخفض
تمثل قيمة low-link لكل عقدة أصغر معرّف اكتشاف يمكن الوصول إليه منها، بما في ذلك الوصول عبر الأضلاع الراجعة. وهي تحدد أساس المكوّن.
low = [-1] * nأضف العقدة إلى المكدس
عندما تدخل DFS إلى عقدة، اضبط disc و low الخاصين بها، ثم أضفها إلى مكدس العقد التي قد تشترك معها في المكوّن.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = Trueحدّث low انطلاقًا من الأبناء
بعد تنفيذ التكرار داخل ابن لم تتم زيارته، ارفع قيمة low الخاصة به: تصبح low[u] أصغر قيمة بين قيمتها الحالية وlow الابن.
dfs(v)
low[u] = min(low[u], low[v])تعامل مع الأضلاع الراجعة
إذا كان أحد الجيران موجودًا بالفعل في المكدس، فهو سلف ضمن هذا المكوّن شديد الاتصال. استخدم disc الخاص به لخفض low[u].
elif on_stack[v]:
low[u] = min(low[u], disc[v])حدّد جذر المكوّن
عندما تتساوى low[u] مع disc[u]، تكون العقدة u جذرًا لمكوّن شديد الاتصال. وتنتمي كل العقد الموجودة فوقها في المكدس إلى المكوّن نفسه.
أخرج المكوّن من المكدس
عند الوصول إلى جذر، أخرج العقد من المكدس حتى تزيل u. وتشكل المجموعة المُخرجة مكوّنًا شديد الاتصال واحدًا بالضبط.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju كبديل
هل تفضّل المرورين؟ تنفّذ خوارزمية Kosaraju DFS، ثم تعكس كل ضلع، ثم تنفّذ DFS مرة أخرى وفق ترتيب الانتهاء لاستخراج المكوّنات شديدة الاتصال.
تحقق سريع
أثناء DFS في خوارزمية Tarjan، تحقق للعقدة u أن low[u] == disc[u]. ماذا يخبرك ذلك؟
مراجعة: المكوّنات شديدة الاتصال مع Tarjan
تتبّع disc و low في عملية DFS واحدة، وضع العقد النشطة في المكدس، وأخرج مكوّنًا كلما تساوت low مع disc. المكوّنات شديدة الاتصال بتعقيد O(V+E). 🧩
الأسئلة الشائعة
هل درس «المكوّنات شديدة الاتصال» مجاني؟
نعم — نص درس «المكوّنات شديدة الاتصال» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «المكوّنات شديدة الاتصال»؟
تجميع العقد القابلة للوصول المتبادل باستخدام Tarjan تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «المكوّنات شديدة الاتصال»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- الترتيب الطوبولوجي بخوارزمية Kahn
- اكتشاف الدورات في الرسوم البيانية الموجّهة
- المكوّنات شديدة الاتصال
- الجسور ونقاط المفصل