يحتاج المبرمج الفعال إلى فهم قوي لهياكل البيانات والخوارزميات. غالبًا ما تختبر المقابلات الفنية مهاراتك في حل المشكلات والتفكير النقدي.
الرسوم البيانية هي واحدة من العديد من هياكل البيانات المهمة في البرمجة. في معظم الحالات ، لا يكون فهم الرسوم البيانية وحل المشكلات القائمة على الرسوم أمرًا سهلاً.
ما هو الرسم البياني وماذا تريد أن تعرف عنه؟
ما هو الرسم البياني؟
الرسم البياني هو بنية بيانات غير خطية تحتوي على عقد (أو رؤوس) ذات حواف تربطها. جميع الأشجار هي أنواع فرعية من الرسوم البيانية ، ولكن ليست كل الرسوم البيانية عبارة عن أشجار ، والرسم البياني هو بنية البيانات التي نشأت منها الأشجار.
على الرغم من أنك تستطيع بناء هياكل البيانات في جافا سكريبت ولغات أخرى ، يمكنك تنفيذ رسم بياني بعدة طرق. الأساليب الأكثر شيوعًا هي قوائم الحافة, القوائم المجاورة، و المصفوفات المجاورة.
ال دليل أكاديمية خان لتمثيل الرسوم البيانية هو مصدر رائع للتعرف على كيفية تمثيل الرسم البياني.
هناك أنواع مختلفة من الرسوم البيانية. أحد الفروق المشتركة بين توجه و غير موجه الرسوم البيانية. تأتي هذه كثيرًا في تحديات الترميز والاستخدامات الواقعية.
أنواع الرسوم البيانية
- مخطط موجه: رسم بياني لكل الحواف اتجاه ، يشار إليه أيضًا باسم ديجراف.
- رسم بياني غير موجه: يُعرف الرسم البياني غير المباشر أيضًا بالرسم البياني ثنائي الاتجاه. في الرسوم البيانية غير الموجهة ، لا يهم اتجاه الحواف ، ويمكن أن يسير الاجتياز في أي اتجاه.
- الرسم البياني المرجح: الرسم البياني الموزون هو رسم بياني له قيمة مرتبطة بالعقد والحواف. في معظم الحالات ، تمثل هذه القيمة تكلفة استكشاف تلك العقدة أو الحافة.
- رسم بياني محدد: رسم بياني يحتوي على عدد محدود من العقد والحواف.
- رسم بياني لانهائي: رسم بياني يحتوي على عدد لا نهائي من العقد والحواف.
- رسم تافه: رسم بياني يحتوي على عقدة واحدة فقط وليس له حافة.
- رسم بياني بسيط: عندما تقوم حافة واحدة فقط بتوصيل كل زوج من عقد الرسم البياني ، فإن هذا يسمى الرسم البياني البسيط.
- رسم بياني فارغ: الرسم البياني الفارغ هو رسم بياني ليس له حواف تربط عقده.
- مالتيجراف: في الرسم البياني المتعدد ، يوجد على الأقل زوج من العقد أكثر من حافة تربطها. في الرسوم المتعددة ، لا توجد حلقات ذاتية.
- الرسم البياني الكامل: الرسم البياني الكامل هو رسم بياني تتصل فيه كل عقدة بكل عقدة أخرى في الرسم البياني. ومن المعروف أيضا باسم الرسم البياني الكامل.
- الرسم البياني الزائف: يسمى الرسم البياني الذي يحتوي على حلقة ذاتية بخلاف حواف الرسم البياني الأخرى بالرسم البياني الزائف.
- رسم بياني منتظم: الرسم البياني العادي هو رسم بياني حيث تكون جميع العقد متساوية في الدرجات ؛ أي أن كل عقدة لها نفس عدد الجيران.
- الرسم البياني المتصل: الرسم البياني المتصل هو ببساطة أي رسم بياني تتصل فيه أي عقدتين ؛ أي رسم بياني به مسار واحد على الأقل بين كل عقدتين في الرسم البياني.
- رسم بياني غير متصل: الرسم البياني غير المتصل هو العكس المباشر للرسم البياني المتصل. في الرسم البياني غير المتصل ، لا توجد حواف تربط عقد الرسم البياني ، كما هو الحال في ملف لا شيء رسم بياني.
- الرسم البياني الدوري: الرسم البياني الدوري هو رسم بياني يحتوي على دورة رسم بياني واحدة على الأقل (مسار ينتهي من حيث بدأ).
- الرسم البياني غير الدوري: الرسم البياني غير الدوري هو رسم بياني بدون دورات على الإطلاق. يمكن إما أن يكون موجهاً أو غير موجه.
- الرسم البياني الفرعي: الرسم البياني الفرعي هو رسم بياني مشتق. إنه رسم بياني يتكون من عقد وحواف تشكل مجموعات فرعية من رسم بياني آخر.
أ عقدة في الرسم البياني هو حافة تبدأ من عقدة وتنتهي عند نفس العقدة. لذلك ، أ حلقة ذاتية عبارة عن حلقة فوق عقدة رسم بياني واحدة فقط ، كما يظهر في الرسم البياني الزائف.
خوارزميات اجتياز الرسم البياني
كونه نوعًا من هياكل البيانات غير الخطية ، فإن اجتياز الرسم البياني أمر صعب للغاية. يعني اجتياز الرسم البياني المرور واستكشاف كل عقدة نظرًا لوجود مسار صالح عبر الحواف. تتكون خوارزميات اجتياز الرسم البياني بشكل أساسي من نوعين.
- بحث النطاق الأول (BFS): بحث Breadth-first هو خوارزمية اجتياز الرسم البياني التي تزور عقدة الرسم البياني وتستكشف جيرانها قبل الانتقال إلى أي من العقد الفرعية الخاصة بها. على الرغم من أنه يمكنك البدء في اجتياز الرسم البياني من أي عقدة محددة ، فإن ملف عقدة الجذر هي عادة نقطة البداية المفضلة.
- بحث العمق الأول (DFS): هذه هي ثاني خوارزمية اجتياز الرسم البياني الرئيسية. يزور عقدة الرسم البياني ويستكشف العقد الفرعية أو الفروع قبل الانتقال إلى العقدة التالية - أي التعمق أولاً قبل الانتقال إلى نطاق واسع.
البحث ذو النطاق الأول هو الخوارزمية الموصى بها للعثور على المسارات بين عقدتين في أسرع وقت ممكن ، وخاصة أقصر مسار.
يوصى غالبًا ببحث العمق أولاً عندما تريد زيارة كل عقدة في الرسم البياني. تعمل كلتا خوارزميات الاجتياز بشكل جيد في أي حال ، ولكن قد تكون إحداهما أبسط وأكثر تحسينًا من الأخرى في السيناريوهات المحددة.
يمكن أن يساعد التوضيح البسيط في فهم الخوارزميتين بشكل أفضل. فكر في ولايات بلد ما كرسم بياني وحاول التحقق مما إذا كانت هناك دولتان ، X و ص، متصلة. قد يتم إجراء بحث متعمق أولاً في مسار حول البلاد تقريبًا دون أن يدرك ذلك مبكرًا بما فيه الكفاية ص على بعد دولتين فقط من X.
تتمثل ميزة البحث ذي العرض الأول في أنه يحافظ على القرب من العقدة الحالية قدر الإمكان قبل الانتقال إلى العقدة التالية. سيجد العلاقة بين X و ص في وقت قصير دون الحاجة إلى استكشاف البلد بأكمله.
هناك اختلاف رئيسي آخر بين هاتين الخوارزميتين في طريقة تنفيذها في الكود. اتساع البحث الأول هو خوارزمية تكرارية ويستفيد من أ طابور، بينما عادةً ما يتم تنفيذ بحث العمق أولاً كملف خوارزمية متكررة التي تستفيد من كومة.
يوجد أدناه بعض الكود الكاذب الذي يوضح تنفيذ كلتا الخوارزميتين.
اتساع البحث الأول
bfs (الرسم البياني G ، جذر GraphNode) {
يترك ف كن الجديد طابور// قم بتمييز الجذر على أنه تمت زيارته
الجذر.زيارة = حقيقي// إضافة جذر إلى قائمة الانتظار
ف.enqueue(جذر)
في حين (ف ليست كذلك فارغة) {
يترك يكون الحالي q.dequeue () // إزالة العنصر الأمامي في قائمة الانتظار
لـ (جيران n للتيار في G) {
إذا (ن هوليس تمت زيارته بعد) {
// أضف إلى قائمة الانتظار - حتى تتمكن من استكشاف جيرانها أيضًا
ف.enqueue(ن)
ن زيارة = حقيقي
}
}
}
}
عمق البحث الأول
dfs (الرسم البياني G ، جذر GraphNode) {
// الحالة الأساسية
إذا (الجذر لا شيء) إرجاع// قم بتمييز الجذر على أنه تمت زيارته
الجذر.زيارة = حقيقي
لـ (جيران n من الجذر في G)
إذا (ن هوليس بعد الزيارة)
dfs (G ، n) // نداء متكرر
}
تُشتق بعض خوارزميات اجتياز الرسم البياني الأخرى من عمليات البحث ذات العرض أولاً والعمق أولاً. الأكثر شيوعًا هي:
- بحث ثنائي الاتجاه: هذه الخوارزمية هي طريقة محسّنة للعثور على أقصر مسار بين عقدتين. يستخدم عمليتي بحث عرض أولًا يتصادمان إذا كان هناك مسار.
- الفرز الطوبولوجي: يستخدم هذا في الرسوم البيانية الموجهة لفرز العقد بالترتيب المطلوب. لا يمكنك تطبيق فرز طوبولوجي على الرسوم البيانية غير الموجهة أو الرسوم البيانية ذات الدورات.
- خوارزمية ديكسترا: هذا أيضًا نوع من BFS. يتم استخدامه أيضًا للعثور على أقصر مسار بين عقدتين في ملف مرجح الرسم البياني الموجه، والتي قد تكون لها دورات أم لا.
أسئلة المقابلة العامة على أساس الرسوم البيانية
الرسوم البيانية هي من بين الأمور المهمة هياكل البيانات التي يجب أن يعرفها كل مبرمج. غالبًا ما تُطرح أسئلة حول هذا الموضوع في المقابلات الفنية ، وقد تواجه بعض المشكلات الكلاسيكية المتعلقة بالموضوع. وتشمل هذه أشياء مثل مشاكل "قاضي المدينة" و "عدد الجزر" و "البائع المتجول".
هذه ليست سوى عدد قليل من العديد من مشاكل المقابلة القائمة على الرسم البياني الشائعة. يمكنك تجربتهم على LeetCode, هاكر رانك، أو GeeksforGeeks.
فهم هياكل وخوارزميات بيانات الرسم البياني
الرسوم البيانية ليست مفيدة فقط للمقابلات الفنية. لديهم حالات استخدام في العالم الحقيقي أيضًا ، مثل في الشبكات والخرائط و أنظمة الطيران لإيجاد الطرق. كما أنها تستخدم في المنطق الأساسي لأنظمة الكمبيوتر.
الرسوم البيانية ممتازة لتنظيم البيانات ولمساعدتنا على تصور المشاكل المعقدة. يجب استخدام الرسوم البيانية فقط عند الضرورة القصوى ، على الرغم من ذلك ، لمنع تعقيد المساحة أو مشاكل الذاكرة.
