المكوّنات شديدة الاتصال باستخدام Kosaraju
نفّذ DFS على الرسم البياني الأصلي للحصول على ترتيب الانتهاء، ثم اعكس الرسم البياني ونفّذ DFS مرة أخرى بترتيب الانتهاء العكسي لتحديد المكوّنات شديدة الاتصال.
المكوّنات شديدة الاتصال باستخدام Kosaraju درس مجاني في DSA Interview Prep على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في DSA Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
تعريف المكوّنات شديدة الاتصال
يُعد المكوّن شديد الاتصال (SCC) في الرسم البياني الموجّه مجموعة قصوى من العقد، بحيث يوجد مسار من كل عقدة إلى كل عقدة أخرى داخل المجموعة. على سبيل المثال، إذا شكّلت العقد A وB وC دورة (A→B→C→A)، فإنها تنتمي جميعًا إلى SCC واحد. أما العقدة المفردة التي لا تحتوي على حلقة ذاتية فهي SCC مستقلة بحد ذاتها. تكشف SCCs البنية الدورية للرسم البياني الموجّه.
خوارزمية Kosaraju: مروران باستخدام DFS
تكتشف خوارزمية Kosaraju جميع SCCs ضمن O(V + E) باستخدام مرورين من DFS. المرور الأول: شغّلوا DFS على الرسم البياني الأصلي وادفعوا العقد إلى مكدس وفق ترتيب الانتهاء، أي الترتيب اللاحق. المرور الثاني: شغّلوا DFS على الرسم البياني المنقول (المعكوس)، مع معالجة العقد بترتيب الانتهاء المعكوس، أي بإخراجها من المكدس. تمثل كل شجرة DFS في المرور الثاني SCC واحدة.
سبب نجاح خوارزمية Kosaraju
في المرور الأول، يكون مكوّن SCC الذي تنتهي شجرة DFS الخاصة به أخيرًا هو المكوّن الذي لا يملك حواف خارجة إلى مكوّنات SCC أخرى، أي مكوّن «مصبّ» في DAG التكثيف. وفي الرسم البياني المنقول، لا يملك هذا المكوّن حواف داخلة من مكوّنات SCC أخرى، لذلك تبقى DFS التي تبدأ منه في المرور الثاني محصورة داخل ذلك المكوّن. وتبقى كل DFS لاحقة في المرور الثاني داخل مكوّن SCC الخاص بها، لأن جميع الحواف بين المكوّنات عُكست وأصبحت تتجه إلى مكوّنات سبق الوصول إليها.
المرور الأول: بناء ترتيب الانتهاء
شغّلوا DFS على الرسم البياني الأصلي وادفعوا كل عقدة إلى مكدس بعد انتهائها، أي وفق الترتيب اللاحق. لا نهتم بالمكوّنات في هذا المرور، بل بترتيب الانتهاء فقط. ستكون العقدة الأخيرة انتهاءً ضمن مكوّن SCC «مصدر» في DAG التكثيف.
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u) # reversed edges
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs1(nxt)
finish_stack.append(node) # push after all neighbours done
for i in range(n):
if i not in visited:
dfs1(i)
return finish_stack, rev_graphالمرور الثاني: DFS على الرسم البياني المنقول
أخرجوا العقد من مكدس الانتهاء، بدءًا من العقدة ذات أكبر زمن انتهاء، وشغّلوا DFS على الرسم البياني المنقول. تكتشف كل DFS تبدأ من عقدة غير مُزارة SCC واحدة بالضبط. علّموا جميع العقد التي تصل إليها هذه DFS على أنها تنتمي إلى المكوّن نفسه.
from collections import defaultdict
def kosaraju_full(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited: dfs1(nxt)
finish_stack.append(node)
for i in range(n):
if i not in visited: dfs1(i)
visited.clear()
sccs = []
def dfs2(node, component):
visited.add(node)
component.append(node)
for nxt in rev_graph[node]:
if nxt not in visited: dfs2(nxt, component)
while finish_stack:
node = finish_stack.pop()
if node not in visited:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges)) # [[3], [0,2,1]] or similarنقل الرسم البياني
يعكس الرسم البياني المنقول كل حافة: إذا احتوى الرسم الأصلي على u → v، فسيحتوي الرسم المنقول على v → u. يحافظ النقل على SCCs، فإذا كانت A وB في SCC واحد في الرسم الأصلي، فستبقيان في SCC واحد في الرسم المنقول أيضًا، لأن جميع المسارات تنعكس لكنها تظل تصل بينهما. إن بناء الرسم المنقول أثناء تحليل المدخلات، كما هو موضح أعلاه، يلغي الحاجة إلى خطوة نقل منفصلة.
النسخة التكرارية للرسوم البيانية الكبيرة
في الرسوم البيانية الكبيرة، استبدل DFS العودي بـ DFS التكراري باستخدام مكدس صريح لتجنب حد الاستدعاء التكراري في Python. تدفع النسخة التكرارية العقد إلى المكدس، وتعالجها، وتحافظ على علامة 'return' منفصلة لمحاكاة الترتيب اللاحق.
def dfs1_iterative(start, graph, visited, finish_stack):
stack = [(start, iter(graph[start]))]
visited.add(start)
while stack:
node, neighbours = stack[-1]
try:
nxt = next(neighbours)
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, iter(graph[nxt])))
except StopIteration:
stack.pop()
finish_stack.append(node)
print('Iterative DFS for large graphs avoids recursion limit')خوارزمية Tarjan: بديل لـ SCC
تكتشف خوارزمية Tarjan مكونات SCC في تمريرة DFS واحدة، مقارنة بتمريرتي Kosaraju. وتحافظ على مكدس من العقد، وتعيّن لكل عقدة زمن اكتشاف وقيمة ارتباط منخفض. عندما يساوي زمن اكتشاف العقدة قيمة ارتباطها المنخفض، تكون هذه العقدة جذر مكوّن SCC. تنفيذ Tarjan أكثر تعقيدًا قليلًا، لكنه يتجنب إنشاء الرسم البياني المنقول. وكلاهما يعمل بالتعقيد O(V + E).
تطبيقات مكونات SCC
تُستخدم مكونات SCC في: (1) تحسين المترجم — تحديد الدوال ذات الاستدعاء التكراري المتبادل. (2) تحليل الشبكات الاجتماعية — العثور على المجتمعات شديدة الترابط. (3) مسألة 2-SAT — تحديد قابلية إشباع العبارات المكوّنة من literalين. (4) زحف الويب — تحديد مجموعات الصفحات ذات الروابط المتبادلة الكثيفة. (5) رسم DAG للتكثيف — بعد العثور على مكونات SCC، يكون تكثيف الرسم البياني عبارة عن DAG، ما يتيح التحليل الطوبولوجي للرسوم البيانية الدورية.
رسم DAG للتكثيف
يضمّ تكثيف الرسم البياني الموجّه كل مكوّن SCC في عقدة واحدة، ويضيف حافة بين عقدتين فائقتين إذا وُجدت حافة بين مكوّني SCC المكوّنين لهما. تكون النتيجة دائمًا DAG، لذا يمكن إجراء الفرز الطوبولوجي عليها. يتيح ذلك تطبيق الخوارزميات التي تعمل على DAG فقط، مثل DP، على الرسوم البيانية الموجّهة العامة من خلال العمل على تكثيفها.
def build_condensation(n, edges, sccs):
# Assign each node to its SCC index
scc_id = [0] * n
for idx, component in enumerate(sccs):
for node in component:
scc_id[node] = idx
# Build condensation edges
condensation_edges = set()
for u, v in edges:
su, sv = scc_id[u], scc_id[v]
if su != sv:
condensation_edges.add((su, sv))
return list(condensation_edges)
edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs)) # [(0,1)] or [(1,0)]عدد مكونات SCC وخصائص الرسم البياني
يكشف عدد مكونات SCC في الرسم البياني الموجّه عن بنيته الدورية. يحتوي DAG على n من مكونات SCC، إذ تكون كل عقدة مكوّنًا مستقلًا. ويحتوي الرسم البياني شديد الاتصال على مكوّن SCC واحد بالضبط. عمومًا، تشكّل مكونات SCC رسم DAG عند تكثيفها، ويُسمّى الناتج التكثيف. إذا كان لرسم DAG الخاص بالتكثيف مصدر وحيد، أي عقدة بدرجة دخول تساوي 0، ومصب وحيد، أي عقدة بدرجة خروج تساوي 0، فإن بعض خصائص الاتصال تتحقق. تُختبر هذه الخصائص في المسائل المتعلقة بإمكانية الوصول بعد إضافة الحد الأدنى من الحواف.
تحقق سريع
اختبر مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep الواردة في هذا الدرس.
مراجعة الدرس
في هذا الدرس تعلّمتم: أن مكونات SCC هي مجموعات قصوى يمكن الوصول فيها من كل عقدة إلى كل عقدة أخرى، وأن Kosaraju يستخدم تمريرتين من DFS — الأولى على الرسم البياني الأصلي لتحديد ترتيب الانتهاء، ثم على الرسم البياني المنقول، وأن تكثيف أي رسم بياني موجّه هو DAG يمكن استخدامه لمزيد من التحليل. بعد ذلك سنبني هياكل بيانات TrieNode لإجراء عمليات الإدراج والبحث والبادئات.
الأسئلة الشائعة
هل درس «المكوّنات شديدة الاتصال باستخدام Kosaraju» مجاني؟
نعم — نص درس «المكوّنات شديدة الاتصال باستخدام Kosaraju» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة DSA Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «المكوّنات شديدة الاتصال باستخدام Kosaraju»؟
نفّذ DFS على الرسم البياني الأصلي للحصول على ترتيب الانتهاء، ثم اعكس الرسم البياني ونفّذ DFS مرة أخرى بترتيب الانتهاء العكسي لتحديد المكوّنات شديدة الاتصال. تتمرن على DSA Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ DSA Interview Prep؟
لا تُشترط خبرة سابقة. DSA Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «المكوّنات شديدة الاتصال باستخدام Kosaraju»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس DSA Interview Prep هذا؟
نعم. كل درس في DSA Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- خوارزمية Kahn: الترتيب الطوبولوجي باستخدام BFS
- الترتيب الطوبولوجي باستخدام DFS بترتيب ما بعد الزيارة
- جدول المقررات I وII
- المكوّنات شديدة الاتصال باستخدام Kosaraju