الترتيب الطوبولوجي باستخدام DFS بترتيب ما بعد الزيارة
نفّذ DFS وادفع كل عقدة إلى مكدس بعد استكشاف جيرانها بالكامل، ثم أخرج العقد من المكدس للحصول على ترتيب طوبولوجي صالح.
الترتيب الطوبولوجي باستخدام DFS بترتيب ما بعد الزيارة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
فكرة الفرز الطوبولوجي القائم على DFS
تستخدم خوارزمية الفرز الطوبولوجي الكلاسيكية الثانية DFS مع المعالجة اللاحقة. بعد استكشاف جميع جيران العقدة وأحفادهم بالكامل، ادفعوا العقدة إلى مكدس. بعد معالجة جميع العقد، أخرجوا العقد من المكدس لقراءة الترتيب الطوبولوجي. العقدة التي تُدفَع إلى المكدس بعد استكشاف جميع تبعياتها تأتي أولًا في الترتيب، ولذلك يكون الترتيب اللاحق المعكوس هو الفرز الطوبولوجي.
الفكرة وراء الترتيب اللاحق
لنفترضوا وجود رسم بياني للتبعيات، حيث يتطلب المقرر A اجتياز المقرر B. عندما تزور DFS العقدة A، فإنها تستدعي نفسها تكراريًا على العقدة B أولًا. لا توجد متطلبات سابقة للمقرر B، لذلك ينتهي استكشافه أولًا ويُدفَع إلى المكدس أولًا. بعد ذلك ينتهي استكشاف A وتُدفَع إلى المكدس. يؤدي إخراج العناصر من المكدس إلى الحصول على A قبل B في الناتج، لكننا نعكس الترتيب في النهاية، فنحصل على B قبل A: ابدؤوا بـ B ثم A. يدفع الترتيب اللاحق التبعيات قبل العناصر التابعة لها، لذا يكون المكدس المعكوس ترتيبًا طوبولوجيًا صالحًا.
اكتشاف الدورات باستخدام DFS ذي الألوان الثلاثة
استخدموا ثلاث حالات للزيارة: WHITE (0) = غير مُزارة، وGREY (1) = قيد المعالجة حاليًا (في مكدس استدعاءات DFS)، وBLACK (2) = عولجت بالكامل. تشير الحافة الخلفية، أي الحافة المتجهة إلى عقدة GREY، إلى وجود دورة. أما الحواف المتجهة إلى عقد BLACK فهي آمنة، إذ جرى استكشافها بالكامل من قبل. يكتشف هذا المخطط ذو الألوان الثلاثة جميع الدورات في الرسوم البيانية الموجّهة على نحو صحيح.
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)التنفيذ الكامل للفرز الطوبولوجي باستخدام DFS
استخدموا DFS تكرارية تلوّن العقد، وتدفعها إلى مكدس وفق الترتيب اللاحق، وتُرجع False عند اكتشاف دورة. بعد زيارة جميع العقد، يعطي المكدس المعكوس الترتيب الطوبولوجي.
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))DFS تكرارية لتجنب تجاوز سعة المكدس
يمثل حد التكرار في Python، وقيمته الافتراضية 1000، مصدر قلق عند التعامل مع الرسوم البيانية الكبيرة. تتجنب DFS التكرارية ذلك باستخدام مكدس صريح. تكمن الحيلة في دفع (node, False) مبدئيًا؛ فعند إخراجها مع القيمة False، ادفعوا (node, True)، بمعنى «سأعود إلى هنا بعد الاستكشاف»، ثم ادفعوا جميع الجيران غير المُزارين مع القيمة False. وعند إخراجها مع القيمة True، لوّنوا العقدة باللون BLACK وادفعوها إلى مكدس النتائج.
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]مقارنة بين DFS وخوارزمية Kahn
تعمل كلتا الخوارزميتين ضمن التعقيد O(V + E). تتمثل الفروقات الأساسية في أن خوارزمية Kahn (BFS) تنتج طبيعيًا العقد بترتيب يبدأ بالتبعيات الأبكر، كما أن اكتشاف الدورات فيها أبسط، إذ يعتمد على فحص الطول. أما الترتيب اللاحق باستخدام DFS فيعمل بصورة تكرارية ويكتشف الحواف الخلفية صراحةً. تُفضَّل خوارزمية Kahn عندما تريدون الحصول على الناتج بالترتيب الأمامي من دون عكسه. وتُفضَّل DFS عندما تحتاجون إلى الترتيب اللاحق الكامل لأغراض أخرى، مثل اكتشاف SCC. كلتا الطريقتين مقبولتان في المقابلات.
الترتيب اللاحق في شجرة مقابل DAG
في الشجرة، يزور الترتيب اللاحق الشجرة الفرعية اليسرى ثم الشجرة الفرعية اليمنى ثم الجذر. أما في DAG، فتزور DFS بالترتيب اللاحق جميع تبعيات العقدة قبل معالجة العقدة نفسها، وهي الفكرة ذاتها بعد تعميمها على عدة أسلاف وبنية رسم بياني عامة. يُدفَع جذر شجرة DFS، أي العقدة التي بدأنا منها، أخيرًا بين أحفاده، ولذلك يظهر أولًا في المكدس المعكوس، وهو الموضع الطوبولوجي الصحيح لعقدة لا أسلاف لها.
Alien Dictionary (LeetCode 269)
Alien Dictionary: بالنظر إلى قائمة مرتبة من الكلمات في لغة فضائية، استنتجوا ترتيب الأحرف. قارنوا الكلمات المتجاورة حرفًا حرفًا للعثور على أول اختلاف، فهذا يعطي حافة c1 → c2 بمعنى أن c1 يأتي قبل c2. اجمعوا جميع هذه الحواف ثم شغّلوا الفرز الطوبولوجي لإنتاج ترتيب أحرف اللغة الفضائية. إذا وُجدت دورة، يكون الترتيب غير صالح.
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'الفرز الطوبولوجي مع القيود
تطلب بعض المسائل فرزًا طوبولوجيًا يستوفي قيودًا إضافية، مثل الحفاظ على الترتيب النسبي للعناصر في القائمة الأصلية. ادمجوا خوارزمية Kahn مع طابور أولوية مخصّص أو مع الفرز المسبق، وحافظوا على الترتيب النسبي الأصلي للعناصر باستخدام فرز مستقر لمحتويات الطابور في كل خطوة. تختبر هذه الصيغ المقيّدة فهمًا أعمق لمرونة الخوارزمية.
التعرّف على مسائل الفرز الطوبولوجي
تتضمن العبارات الدالة في مسائل المقابلات التي تشير إلى الفرز الطوبولوجي: «تبعيات معطاة»، و«متطلبات سابقة»، و«ترتيب المهام»، و«ترتيب البناء»، و«هل يمكن إكمال جميع المهام؟»، و«العثور على تسلسل صالح». إذا تضمنت المسألة ترتيب عناصر يجب أن يسبق بعضها بعضًا، فابنوا رسمًا بيانيًا موجّهًا وطبّقوا فرز Kahn الطوبولوجي أو الفرز الطوبولوجي باستخدام DFS. وغالبًا ما يكون اكتشاف الدورات متطلبًا إضافيًا في المسألة نفسها.
مقارنة ناتج DFS بناتج خوارزمية Kahn
قد تنتج DFS وخوارزمية Kahn ترتيبين طوبولوجيين صالحين مختلفين للرسم البياني نفسه. كلاهما صحيح، إذ يمكن أن يكون لـ DAG عدة ترتيبات طوبولوجية صالحة. للتحقق من صحة الناتج، تأكدوا من أن كل حافة u → v في الرسم البياني تحقق ظهور u قبل v في ترتيب الناتج. أما في مسائل المقابلات التي تتطلب ترتيبًا محددًا، مثل الترتيب المعجمي الأصغر، فاستخدموا خوارزمية Kahn مع كومة دنيا، إذ لا ينتج الترتيب اللاحق لـ DFS الترتيب المعجمي الأصغر بصورة طبيعية.
اختبار سريع
اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep الواردة في هذا الدرس.
مراجعة الدرس
تعلمتم في هذا الدرس أن الفرز الطوبولوجي بالترتيب اللاحق باستخدام DFS يدفع العقد بعد استكشاف جميع تبعياتها، وأن الوسم بالألوان الثلاثة (WHITE/GREY/BLACK) يكتشف الدورات عبر الحواف الخلفية المتجهة إلى عقد GREY، وأن عكس مكدس الترتيب اللاحق يعطي ترتيبًا طوبولوجيًا صالحًا. في الجزء التالي سنطبّق الفرز الطوبولوجي مباشرةً على مسألتي Course Schedule I وII.
الأسئلة الشائعة
هل درس «الترتيب الطوبولوجي باستخدام DFS بترتيب ما بعد الزيارة» مجاني؟
نعم — نص درس «الترتيب الطوبولوجي باستخدام DFS بترتيب ما بعد الزيارة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «الترتيب الطوبولوجي باستخدام DFS بترتيب ما بعد الزيارة»؟
نفّذ DFS وادفع كل عقدة إلى مكدس بعد استكشاف جيرانها بالكامل، ثم أخرج العقد من المكدس للحصول على ترتيب طوبولوجي صالح. تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «الترتيب الطوبولوجي باستخدام DFS بترتيب ما بعد الزيارة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- خوارزمية Kahn: الترتيب الطوبولوجي باستخدام BFS
- الترتيب الطوبولوجي باستخدام DFS بترتيب ما بعد الزيارة
- جدول المقررات I وII
- المكوّنات شديدة الاتصال باستخدام Kosaraju