C++ Boost Graph

إنشاء رسم بياني غير موجه باستخدام C++ Boost والتصفح عبره بترتيب البحث العميق أولاً

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

مقدمة للمشكلة

إنشاء العمل مع الرسوم البيانية قد يكون مرعبًا، لكن مع Boost، يصبح الأمر أكثر سهولة. البحث العميق أولاً (DFS) هو خوارزمية أساسية تستخدم لاستكشاف الرؤوس والحواف في رسم بياني. سواء كنت تبحث عن مسارات، أو تتحقق من الاتصال، أو تحل الألغاز، فإن DFS تعتبر وسيلة فعالة للتنقل عبر الرسوم البيانية.

في هذه المقالة، سنستعرض مثالًا ملموسًا لإعداد رسم بياني غير موجه وتنفيذ عملية DFS.

نظرة عامة على الحل

سنغطي الخطوات التالية:

  1. تضمين رؤوس Boost الضرورية.
  2. تعريف هيكل الرسم البياني.
  3. إنشاء فصل زائر للتعامل مع اكتشاف الرأس.
  4. إعداد الوظيفة الأساسية لإنشاء الرسم البياني وتنفيذ DFS.

الخطوة 1: تضمين رؤوس Boost الضرورية

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

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>

الخطوة 2: تعريف هيكل الرسم البياني

نقوم بتعريف رسمنا البياني غير الموجه باستخدام boost::adjacency_list. إليك كيف يمكنك تعريفه:

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> MyGraph;
typedef boost::graph_traits<MyGraph>::vertex_descriptor MyVertex;
  • في الكود أعلاه:
    • listS تشير إلى أن الرسم البياني سيستخدم قائمة من الحواف.
    • vecS تعني أننا سنستخدم مصفوفة لتخزين الرؤوس.
    • undirectedS يحدد أن الرسم البياني غير موجه.

الخطوة 3: إنشاء فصل الزائر

فصل الزائر أمر حيوي لتحديد ما يحدث عندما يتم اكتشاف رأس أثناء DFS. إليك مثالًا على فصل زائر بسيط:

class MyVisitor : public boost::default_dfs_visitor {
public:
  void discover_vertex(MyVertex v, const MyGraph& g) const {
    std::cerr << v << std::endl; // طباعة رقم الرأس
    return;
  }
};

الخطوة 4: إعداد الوظيفة الأساسية

أخيرًا، نحتاج إلى إنشاء الرسم البياني، وإضافة الحواف، واستدعاء خوارزمية DFS.

int main() {
  MyGraph g;
  boost::add_edge(0, 1, g); // ربط الرأس 0 والرأس 1
  boost::add_edge(0, 2, g); // ربط الرأس 0 والرأس 2
  boost::add_edge(1, 2, g); // ربط الرأس 1 والرأس 2
  boost::add_edge(1, 3, g); // ربط الرأس 1 والرأس 3

  MyVisitor vis;
  boost::depth_first_search(g, boost::visitor(vis)); // تنفيذ عمليات البحث العميق أولاً

  return 0;
}

شرح الكود

  • إنشاء الرسم البياني: ننشئ مثيلًا من MyGraph يسمى g. ثم نضيف الحواف التي تحدد الاتصالات بين الرؤوس.
  • تنفيذ DFS: من خلال إنشاء مثيل من MyVisitor، نمرره كزائر إلى depth_first_search، الذي يتصفح الرسم البياني ويدعو discover_vertex لكل رأس.

الخاتمة

يمكن لاستخدام مكتبة Boost لإنشاء وتصفح رسم بياني تحسين المهام المعقدة بشكل كبير في C++. من خلال اتباع الخطوات الموضحة أعلاه، يمكنك تنفيذ البحث العميق أولاً (DFS) بنجاح على رسم بياني غير موجه.

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