اجتياز الرسوم البيانية

يقوم اجتياز الرسوم البيانية بزيارة رؤوس وحواف الرسم البياني بشكل منهجي؛ يستكشف البحث الأول بالاتساع مستوى تلو الآخر بينما يستكشف البحث الأول بالعمق أعمق ما يمكن قبل التراجع، ويشكلان معًا أساس معظم خوارزميات الرسوم البيانية.

Definition

اجتياز الرسم البياني هو عملية زيارة كل رأس (وفحص كل حافة) في الرسم البياني بترتيب منهجي؛ يزور البحث الأول بالاتساع الرؤوس بترتيب المسافة من المصدر، ويتبع البحث الأول بالعمق كل مسار حتى نهايته قبل التراجع.

Scope

يغطي هذا الموضوع استراتيجيتي البحث الأساسيتين في الرسوم البيانية، وهما البحث الأول بالاتساع (BFS) والبحث الأول بالعمق (DFS)، وتطبيقاتهما القائمة على قائمة الانتظار والمكدس، والمعلومات الهيكلية التي تكشفان عنها — إمكانية الوصول، والمكونات المتصلة، وأقصر المسارات في الرسوم البيانية غير الموزونة، والترتيب الطوبولوجي، واكتشاف الدورات، والمكونات المتصلة بقوة. يستثنى من ذلك أقصر المسارات الموزونة ومشاكل التدفق، والتي تعتمد على الاجتياز ولكن يتم تناولها بشكل منفصل.

Core questions

• كيف يختلف BFS و DFS في ترتيب زيارتهما للرؤوس، وماذا يكشف كل منهما؟
• كيف يحسب BFS أقصر المسارات في رسم بياني غير موزون؟
• كيف يمكّن DFS الفرز الطوبولوجي، واكتشاف الدورات، وتحليل المكونات؟
• لماذا تعمل كلتا عمليتي الاجتياز في زمن خطي بالنسبة لعدد الرؤوس بالإضافة إلى الحواف؟
• كيف تُستخدم علامات الزيارة وهياكل الحدود لتجنب إعادة زيارة الرؤوس؟

Key concepts

• البحث الأول بالاتساع (BFS)
• البحث الأول بالعمق (DFS)
• مجموعة الرؤوس التي تمت زيارتها
• قوائم الانتظار والمكدسات الحدودية
• المكونات المتصلة
• الفرز الطوبولوجي
• اكتشاف الدورات
• المكونات المتصلة بقوة

Key theories

البحث الأول بالاتساع وأقصر المسارات غير الموزونة

يزور BFS الرؤوس بترتيب غير تنازلي للمسافة من المصدر باستخدام قائمة انتظار، وبالتالي يحسب الحد الأدنى لعدد الحواف من المصدر إلى كل رأس يمكن الوصول إليه في زمن خطي.

البحث الأول بالعمق وخوارزميات الرسم البياني الخطية

ينتج DFS، مع أوقات الاكتشاف والانتهاء وتصنيف الحواف، خوارزميات زمنية خطية للفرز الطوبولوجي، واكتشاف الدورات، وإيجاد المكونات المتصلة بقوة، كما تم منهجه بواسطة تارغان.

Clinical relevance

خوارزميات الاجتياز موجودة في كل مكان: يجد البحث الأول بالاتساع أقصر عدد من القفزات في الشبكات غير الموزونة ويشكل أساس زواحف الويب والبث من نظير إلى نظير؛ يدفع البحث الأول بالعمق حل التبعيات وأنظمة البناء عبر الفرز الطوبولوجي، واكتشاف الجمود، وحل المتاهات والألغاز، وتحليل المكونات في الشبكات الاجتماعية والبيولوجية.

History

يعود تاريخ البحث الأول بالاتساع إلى عمل مور عام 1959 حول توجيه المتاهات والجهود المستقلة ذات الصلة. وُضع البحث الأول بالعمق على أساس خوارزمي صارم بواسطة روبرت تارغان في عام 1972، حيث أظهرت خوارزمياته ذات الزمن الخطي للمكونات المتصلة بقوة والاتصال الثنائي أن البحث الأول بالعمق أداة عامة قوية.

Key figures

• Robert Tarjan
• Edward F. Moore
• John Hopcroft

Seminal works

• tarjan1972
• cormen2009

Frequently asked questions

متى يجب أن أستخدم BFS بدلاً من DFS؟

استخدم BFS عندما تحتاج إلى أقصر مسار من حيث عدد الحواف أو ترغب في استكشاف الرسم البياني بترتيب المسافة من المصدر. استخدم DFS للمشاكل المتعلقة بالهيكل — الترتيب الطوبولوجي، اكتشاف الدورات، المكونات المتصلة أو المتصلة بقوة — حيث يكون الاستكشاف العميق والتراجع أمرًا طبيعيًا.

لماذا يكون BFS و DFS كلاهما زمنيًا خطيًا؟

يتم تمييز كل رأس على أنه تمت زيارته ومعالجته مرة واحدة، ويتم فحص كل حافة عددًا ثابتًا من المرات، لذا فإن العمل الكلي يتناسب مع عدد الرؤوس بالإضافة إلى عدد الحواف، ويُكتب O(V + E).