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

تمثّل الأشجار علاقات «واحد إلى متعدد»، بينما تتمتع الرسوم البيانية بدرجة حرية أعلى ويمكنها تمثيل أي علاقات «متعدد إلى متعدد». لذلك يمكننا النظر إلى الأشجار على أنها حالة خاصة من الرسوم البيانية. ومن الواضح أن عمليات اجتياز الأشجار هي أيضاً حالة خاصة من عمليات اجتياز الرسوم البيانية.

تشترط كل من الرسوم البيانية والأشجار تطبيق خوارزميات البحث لتنفيذ عمليات الاجتياز. ويمكن أيضاً تقسيم طرق اجتياز الرسم البياني إلى نوعين: الاجتياز بالعرض أولاً والاجتياز بالعمق أولاً.

البحث بالعرض أولاً

يتقدّم البحث بالعرض أولاً من القريب إلى البعيد: بدءاً من عقدة معينة، يزور دائماً أقرب الرؤوس أولاً ويتوسّع نحو الخارج طبقة بعد طبقة. وكما هو موضح في الشكل أدناه، بدءاً من الرأس العلوي الأيسر، اجتز أولاً جميع الرؤوس المجاورة لذلك الرأس، ثم اجتز جميع الرؤوس المجاورة للرأس التالي، وهكذا، حتى تُزار جميع الرؤوس.

تنفيذ الخوارزمية

يُنفَّذ البحث بالعرض أولاً عادةً بمساعدة طابور، كما هو موضح في الشيفرة أدناه. ويتمتع الطابور بخاصية «أول ما يدخل يخرج أولاً»، وهو ما يتوافق مع فكرة البحث بالعرض أولاً القائمة على «من القريب إلى البعيد».

1. أضف رأس البداية startVet إلى الطابور وابدأ الحلقة.
2. في كل تكرار من الحلقة، أخرِج الرأس الموجود في مقدمة الطابور وسجّله كمزار، ثم أضف جميع الرؤوس المجاورة لذلك الرأس إلى مؤخرة الطابور.
3. كرّر الخطوة 2. حتى تُزار جميع الرؤوس.

لمنع إعادة زيارة الرؤوس، نستخدم مجموعة تجزئة visited لتسجيل العقد التي زُيرت.

الشيفرة مجرّدة نسبياً؛ ويُوصى بالرجوع إلى الشكل أدناه لتعميق الفهم.

تحليل التعقيد

التعقيد الزمني: ستُدخَل جميع الرؤوس إلى الطابور وتُخرَج منه مرة واحدة، باستخدام زمن $O(|V|)$؛ وفي أثناء اجتياز الرؤوس المجاورة، وبما أن الرسم البياني غير موجّه، ستُزار جميع الأضلاع مرتين، باستخدام زمن $O(2|E|)$؛ وبشكل إجمالي زمن $O(|V| + |E|)$.

التعقيد المكاني: يمكن أن تحتوي القائمة res ومجموعة التجزئة visited والطابور que على $|V|$ من الرؤوس على الأكثر، باستخدام مساحة $O(|V|)$.

البحث بالعمق أولاً

البحث بالعمق أولاً طريقة اجتياز تعطي الأولوية للمضي إلى أبعد حد ممكن، ثم تتراجع عند انعدام المسار. وكما هو موضح في الشكل أدناه، بدءاً من الرأس العلوي الأيسر، زُر رأساً مجاوراً للرأس الحالي، واستمر حتى تصل إلى طريق مسدود، ثم عُد وواصل المضي إلى أبعد حد ممكن قبل أن تعود مجدداً، وهكذا، حتى تُجتاز جميع الرؤوس.

تنفيذ الخوارزمية

يُنفَّذ هذا النموذج الخوارزمي القائم على «المضي إلى أبعد حد ممكن ثم العودة» عادةً باستخدام التعاود. وكما في البحث بالعرض أولاً، نحتاج في البحث بالعمق أولاً أيضاً إلى مجموعة تجزئة visited لتسجيل الرؤوس المزارة وتجنّب إعادة زيارتها.

يوضح الشكل أدناه سير خوارزمية البحث بالعمق أولاً.

• تمثّل الخطوط المتقطعة المستقيمة التعاود النازل، ما يشير إلى بدء دالة تعاودية جديدة لزيارة رأس جديد.
• تمثّل الخطوط المتقطعة المنحنية التراجع الصاعد، ما يشير إلى أن هذا الاستدعاء التعاودي عاد إلى النقطة التي استُدعي منها.

لتعميق الفهم، يُوصى بالجمع بين الشكل أدناه والشيفرة لمحاكاة عملية البحث بالعمق أولاً بأكملها ذهنياً (أو رسمها)، بما في ذلك وقت بدء كل استدعاء تعاودي ووقت عودته.

تحليل التعقيد

التعقيد الزمني: ستُزار جميع الرؤوس مرة واحدة، باستخدام زمن $O(|V|)$؛ وستُزار جميع الأضلاع مرتين، باستخدام زمن $O(2|E|)$؛ وبشكل إجمالي زمن $O(|V| + |E|)$.

التعقيد المكاني: يمكن أن تحتوي القائمة res ومجموعة التجزئة visited على $|V|$ من الرؤوس على الأكثر، وعمق التعاود الأقصى هو $|V|$، ومن ثمّ باستخدام مساحة $O(|V|)$.